我需要一个32位随机数,精确的10位设置为1.但同时,101(5 dec)和11(3 dec)等模式被认为是非法的.
现在MCU是8051(8位),我在Keil uVision中测试了所有这些.我的第一次尝试完成,给出解决方案
0x48891249 1001000100010010001001001001001 // correct,10 bits 1,no 101 or 11
问题是它完成了97秒或1165570706 cpu周期,这是荒谬的！
这是我的代码
// returns 1 if number is not good. ie. contains at leats one 101 bit sequence
bool checkFive(unsigned long num)
{
unsigned char tmp;
do {
tmp = (unsigned char)num;
if(
(tmp & 7) == 5
|| (tmp & 3) == 3
) // illegal pattern 11 or 101
return true; // found
num >>= 1;
}while(num);
return false;
}
void main(void) {
unsigned long v,num; // count the number of bits set in v
unsigned long c; // c accumulates the total bits set in v
do {
num = (unsigned long)rand() << 16 | rand();
v = num;
// count all 1 bits,Kernigen style
for (c = 0; v; c++)
v &= v - 1; // clear the least significant bit set
}while(c != 10 || checkFive(num));
while(1);
}
一个聪明的头脑的大问题:)
可以做得更快吗？似乎我的方法很天真.
先感谢您,
哇,我印象深刻,感谢大家的建议.但是,在接受之前,我需要对它们进行测试.
现在有了第一个选项(查找)它是不现实的,将完成吹我整个8051微控制器的4K RAM :)正如你在图像波纹管中看到的,我测试了代码块中的所有组合但是有更多的方法300,直到5000指数它还没有完成……
我用来测试的代码
#include <stdio.h> #include <stdint.h> #include <stdlib.h> #include <stdbool.h> //#define bool bit //#define true 1 //#define false 0 // returns 1 if number is not good. ie. contains at leats one 101 bit sequence bool checkFive(uint32_t num) { uint8_t tmp; do { tmp = (unsigned char)num; if( (tmp & 7) == 5 || (tmp & 3) == 3 ) // illegal pattern 11 or 101 return true; // found num >>= 1; }while(num); return false; } void main(void) { uint32_t v,num; // count the number of bits set in v uint32_t c,count=0; // c accumulates the total bits set in v //printf("Program started \n"); num = 0; printf("Program started \n"); for(num=0; num <= 0xFFFFFFFF; num++) { //do { //num = (uint32_t)rand() << 16 | rand(); v = num; // count all 1 bits,Kernigen style for (c = 0; v; c++) v &= v - 1; // clear the least significant bit set //}while(c != 10 || checkFive(num)); if(c != 10 || checkFive(num)) continue; count++; printf("%d: %04X\n",count,num); } printf("Complete \n"); while(1); }
也许我可以重新制定这个问题：
我需要一个数字：
>精确(已知)的1位数量,在我的例子中为10
>没有11或101模式
>剩余的零可以是任何
所以不知何故,只在内部洗牌1位.
解决方法
给定例程r(n)返回从0(包括)到n(不包括)均匀分布的随机整数,问题中描述的值可以通过调用P(10,4)得到均匀分布,其中P是：
static uint32_t P(int a,int b)
{
if (a == 0 && b == 0)
return 0;
else
return r(a+b) < a ? P(a-1,b) << 3 | 1 : P(a,b-1) << 1;
}
static int r(int a)
{
int q;
do
q = rand() / ((RAND_MAX+1u)/a);
while (a <= q);
return q;
}
(除以(RAND_MAX 1u)/ a和do-while循环的目的是将rand的范围调整为a的偶数倍,以便消除由于非多重范围引起的偏差.)
(P中的递归可以转换为迭代.这是省略的,因为没有必要说明算法.)
讨论
如果该数字不能包含连续的比特11或101,那么最接近的两个1比特可以是三比特,如在1001中.在32比特中拟合十个1比特然后需要至少28比特,如在1001001001001001001001001中.因此,到满足没有11或101的约束,并且正好有10个1位,该值必须为1001001001001001001001001001,在某些位置插入四个0位(可能包括开头或结尾).
选择这样的值相当于按顺序放置10个001实例和4个0实例.1有14个！订购14件商品的方式,但10件中的任何一件！重新排列10 001实例的方法是相同的,4个中的任何一个！重新排列0个实例的方法是相同的,所以不同选择的数量是14！ / 10！ / 4！,也称为从14中选择10件事的组合数.这是1,001.
要使用均匀分布执行此类选择,我们可以使用递归算法：
>选择概率分布等于可能排序中选项比例的第一个选项.
>递归选择剩余的选项.
当订购一个对象的实例和第二个对象的b时,潜在排序的/(a b)将从第一个对象开始,b /(a b)将从第二个对象开始.因此,P例程的设计是：
>如果没有要按顺序放置的对象,则返回空位串.
>在[0,a b)中选择一个随机整数.如果它小于a(具有概率a /(a b)),则插入位串001然后递归以选择001的实例和b的0实例的顺序.
>否则,插入位串0然后递归以选择001和b-1实例为0的实例的顺序.
(因为,一旦a为零,只生成0个实例,如果P中的(a == 0& b == 0)可以改为if(a == 0).我把它保留为前一个形式因为这表示在涉及其他字符串的情况下解决方案的一般形式.)
奖金
这是一个列出所有值的程序(尽管不是按升序排列).
#include <stdint.h> #include <stdio.h> static void P(uint32_t x,int a,int b) { if (a == 0 && b == 0) printf("0x%x\n",x); else { if (0 < a) P(x << 3 | 1,a-1,b); if (0 < b) P(x << 1,a,b-1); } } int main(void) { P(0,10,4); }
脚注
1这个公式意味着我们最终会得到一个字符串,它起始于001 …而不是1 ……,但结果值(解释为二进制)是等效的,即使在它之前插入0的实例也是如此.所以10 001和4 0的字符串与字符串一一对应,4 0插入1001001001001001001001001.
