c,获得一个特殊的随机数

Question

我有一个算法问题,我需要加快:)

我需要一个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位.

或者,取一个0x00000000并在随机位置添加10位,除了非法模式.

Answer 1

解

给定一个例程r(n),它返回一个从0(包括)到n(不包括)均匀分布的随机整数,问题中描述的值可以通过调用P(10, 4)where 来生成统一分布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.1在32位中拟合10 位然后需要至少28位,如1001001001001001001001001001.因此,为了满足没有11或者101恰好有10 1位的约束,该值必须在一些位置插入1001001001001001001001001001四位0(包括可能的开头或结尾).

选择这样的值相当于按某种顺序放置10个实例001和4个实例0.¹ 有14个!订购14件商品的方式,但10件中的任何一件!重新安排10个001实例的方法是相同的,4个中的任何一个!将0实例重新排列的方法是相同的,因此不同选择的数量是14!/ 10!/ 4!,也称为从14中选择10件事的组合数.这是1,001.

要使用均匀分布执行此类选择,我们可以使用递归算法:

• 选择概率分布等于可能排序中的选项比例的第一选择.
• 递归选择其余选项.

当订购一个一个对象和实例b的第二对象的,一个 /(一个 + b)的电位的排序将与第一对象开始,和b /(一个 + b)将与所述第二对象开始.因此,P例程的设计是:

• 如果没有要按顺序放置的对象,则返回空位串.
• 在[0,a + b)中选择一个随机整数.如果它小于一个(其具有概率一个 /(一个 + b)),插入比特串001,然后递归以选择的次序一个 -1实例001和b的实例0.
• 否则,插入比特串0,然后递归以选择的次序一个实例001和b -1实例0.

(由于,一旦a为零,仅0实例生成,if (a == 0 && b == 0)在P可以改变为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);
}

脚注

¹这个公式意味着我们最终得到一个字符串001…而不是1…,但结果值被解释为二进制,是相同的,即使在0它之前插入了实例.因此,10 001和4 0的字符串与0插入4的字符串一一对应1001001001001001001001001001.

Answer 2

在有限数量的解决方案中满足您的标准的一种方法是利用000在比特群中不再有四组s 的事实.这也意味着值中可以有一组0000.知道了这一点,你可以用一个单一的种子你的价值1在位27-31,然后继续添加随机位检查每一位加入你的满足3或5限制.

在向您的值添加随机位并满足约束时,总会有组合导致解决方案永远不能满足所有约束.为了防止这些情况,只需保持迭代计数并重置/重新启动值生成,如果迭代超过该值.在这里,如果要找到一个解决方案,它将在不到100次迭代中找到.并且通常在1-8次尝试中找到.对于您生成的每个值的含义,您平均只有不会超过的800迭代次数"97 Seconds or 1165570706 CPU cycles"(我没有计算周期,但返回几乎是瞬时的)

有很多方法可以解决这个问题,这只是一个在合理的时间内工作的方法:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

#define BPOP   10
#define NBITS  32
#define LIMIT 100

/** rand_int for use with shuffle */
static int rand_int (int n)
{
    int limit = RAND_MAX - RAND_MAX % n, rnd;

    rnd = rand();
    for (; rnd >= limit; )
        rnd = rand();

    return rnd % n;
}

int main (void) {

    int pop = 0;
    unsigned v = 0, n = NBITS;
    size_t its = 1;

    srand (time (NULL));

    /* one of first 5 bits must be set */
    v |= 1u << (NBITS - 1 - rand_int (sizeof v + 1));
    pop++;      /* increment pop count */

    while (pop < BPOP) {        /* loop until pop count 10 */
        if (++its >= LIMIT) {   /* check iterations */
#ifdef DEBUG
            fprintf (stderr, "failed solution.\n");
#endif
            pop = its = 1;  /* reset for next iteration */
            v = 0;
            v |= 1u << (NBITS - 1 - rand_int (sizeof v + 1));
        }

        unsigned shift = rand_int (NBITS);  /* get random shift */

        if (v & (1u << shift))   /* if bit already set */
            continue;
        /* protect against 5 (101) */
        if ((shift + 2) < NBITS && v & (1u << (shift + 2)))
            continue;
        if ((int)(shift - 2) >= 0 && v & (1u << (shift - 2)))
            continue;
        /* protect against 3 (11) */
        if ((shift + 1) < NBITS && v & (1u << (shift + 1)))
            continue;
        if ((int)(shift - 1) >= 0 && v & (1u << (shift - 1)))
            continue;

        v |= 1u << shift;   /* add bit at shift */
        pop++;              /* increment pop count */
    }
    printf ("\nv : 0x%08x\n", v);   /* output value */

    while (n--) {   /* output binary confirmation */
        if (n+1 < NBITS && (n+1) % 4 == 0)
            putchar ('-');
        putchar ((v >> n & 1) ? '1' : '0');
    }
    putchar ('\n');
#ifdef DEBUG
    printf ("\nits: %zu\n", its);
#endif

    return 0;
}

(注意:如果你打算在循环中生成多个随机解决方案,你可能会想要一个更好的随机源getrandom()或者读取/dev/urandom- 特别是如果你从shell中调用可执行文件)

我还提供了一个DEBUG定义,您可以通过向-DDEBUG编译器字符串添加选项来启用该定义,以查看失败解决方案的数量和最终的迭代次数.

示例使用/输出

连续8次运行的结果:

$ ./bin/randbits

v : 0x49124889
0100-1001-0001-0010-0100-1000-1000-1001

v : 0x49124492
0100-1001-0001-0010-0100-0100-1001-0010

v : 0x48492449
0100-1000-0100-1001-0010-0100-0100-1001

v : 0x91249092
1001-0001-0010-0100-1001-0000-1001-0010

v : 0x92488921
1001-0010-0100-1000-1000-1001-0010-0001

v : 0x89092489
1000-1001-0000-1001-0010-0100-1000-1001

v : 0x82491249
1000-0010-0100-1001-0001-0010-0100-1001

v : 0x92448922
1001-0010-0100-0100-1000-1001-0010-0010