c - 如何随机化 64 位模式中的最低位

Question

我有兴趣了解更多有关位移位和随机生成位的操作背后的概念。下面是一些打印 20 个随机 64 位模式的代码。 “rand_bits”使用 C 标准 rand() 返回 64 位模式，其中除最低位外全部为零，这些位是随机的。低随机位的数量由函数的唯一参数提供。

   const int LINE_CNT = 20;

    void print_bin(uint64_t num, unsigned int bit_cnt);

    uint64_t rand_bits(unsigned int bit_cnt);

    int main(int argc, char *argv[]) {

        int i;

        srand(time(NULL));
        for(i = 0; i < LINE_CNT; i++) {
            uint64_t val64 = rand_bits(64);
            print_bin(val64, 64);
        }
    return EXIT_SUCCESS;
    }


    void print_bin(uint64_t num, unsigned int bit_cnt) {

        int top_bit_cnt;

        if(bit_cnt <= 0) return;
        if(bit_cnt > 64) bit_cnt = 64;

        top_bit_cnt = 64;
        while(top_bit_cnt > bit_cnt) {
            top_bit_cnt--;
            printf(" ");
        }

        while(bit_cnt > 0) {
            bit_cnt--;
            printf("%d", (num & ((uint64_t)1 << bit_cnt)) != 0);
        }
        printf("\n");

        return;
    }


    /*
     * Name: rand_bits
     * Function: Returns a 64 bit pattern with all zeros except for the
     *           lowest requested bits, which are randomized.  
     * Parameter, "bit_cnt":  How many of the lowest bits, including the
     *           lowest order bit (bit 0) to be randomized
     * Return: A 64 bit pattern with the low bit_cnt bits randomized.
     */
    uint64_t rand_bits(unsigned int bit_cnt) {


        printf("int bit_cnt:", bit_cnt);
        uint64_t result = rand();
        uint64_t result_1 = result>>5;
// uint64_t result_1 = result>>7;

//return result;
        return result_1;

    }

例如，如果使用 24 作为参数值调用该函数，它可能会返回64位模式，如:

0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_​1101_0110_0101_1110_0111_1100

目前，函数 rand_bits 可能会显示来自 rand() 函数的超过 15 个随机位，但这绝不是保证的。

我认为要像示例中那样获得 40 位，我可以右移这些位，但这似乎不是这个概念。这是否需要高阶位的位掩码或随机数生成器上的模计算？

关于如何返回全零且最低位 (bit_cnt) 随机化的位模式有什么建议吗？

更新:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

const int LINE_CNT = 20;

uint64_t rand_bits( unsigned number_of_bits ){

    uint64_t r = 0;
    unsigned i;
    for(i = 0; i <= number_of_bits / 15; i++ ){
         r = (r << 15) | (rand() & 0x7fff ) ;
    }

    return r & ~(~0ull << number_of_bits) ;
}

void print_bin(uint64_t num, unsigned int bit_cnt) {

        int top_bit_cnt;

        if(bit_cnt <= 0) return;
        if(bit_cnt > 64) bit_cnt = 64;

        top_bit_cnt = 64;
        while(top_bit_cnt > bit_cnt) {
            top_bit_cnt--;
            printf(" ");
        }

        while(bit_cnt > 0) {
            bit_cnt--;
            printf("%d", (num & ((uint64_t)1 << bit_cnt)) != 0);
        }
        printf("\n");

        return;
    }


int main(void) {
int i;
/*      for(i = 0; i < 64; i++)
            print_bin(rand_bits(i),64);
        return EXIT_SUCCESS;
*/

        //I want to keep the code like this, but have the output shown in          //the links.
        srand(time(NULL));
        for(i = 0; i < LINE_CNT; i++) {
                uint64_t val64 = rand_bits(64);
                print_bin(val64, 64);
        }
return EXIT_SUCCESS;
}

当我按照原来的方式将代码保留在 main 中时，输出全是 0。有什么建议可以让我的代码保持原来在 main 中的方式并生成 20 行 64 位且最低位随机化吗？

Answer 1

rand() 生成 [0 ...RAND_MAX] 范围内的 int。 RAND_MAX 至少为 32767，并且肯定比 2 的幂小 1。

如此有效地循环几次，直到我们获得 bit_cnt 随机位。此技巧是利用 RAND_MAX 可能大于 32767 的优势来最小化循环计数。

#include <stdlib.h>

// Valid for 0 <= bit_cnt <= uintmax_t bit wdith
uintmax_t randomized_lowest_bits(unsigned bit_cnt) {
  // Create mask, same as maximum return value
  uintmax_t mask = 1;
  if (bit_cnt >= CHAR_BIT * sizeof(uintmax_t)) {
    mask = -1;
  } else {
    mask = (mask << bit_cnt) - 1;
  }
  uintmax_t limit = mask;
  uintmax_t x = 0;

  while (limit) {
    // x *= (RAND_MAX +1)
    // Done as below to prevent numeric overflow of `RAND_MAX + 1u` on rare machines.
    // Let the compiler optimize it, likely into a fixed count left shift
#if RAND_MAX == INT_MAX
    x = x * (RAND_MAX / 2 + 1) * 2;
#else
    x *= RAND_MAX + 1;
#endif

    // Bring in more bits
    x += rand();

    // Carefully divide by RAND_MAX + 1 with overflow safe guards
    // Again, let the compiler optimize the code, likely into a fixed count right shift
#if RAND_MAX == INT_MAX
    limit = (limit / (RAND_MAX / 2 + 1)) / 2;
#else
    limit /= RAND_MAX + 1;
#endif
  }
  return x & mask;
}

void testR(void) {
  for (int i = 0; i <= 64; i++) {
    printf("%jX\n", randomized_lowest_bits(i));
  }
}

输出

0
1
3
...
1192962917E96171
24833D39561F3B29
C3EC4ED846755A5B