c++ - N 位 x 包含 L 个 1

Question

是否有任何快速算法可以存储包含 L 位 1 的所有各种 N 位数字？提供了 N 和 L 参数。它用于在类里面破解密码系统，我注意到通过两次定时攻击我可以找出位长度 (N) 和 1 位的数量 (L)。

与其暴力强制所有值介于下限和上限之间，我宁愿最小化我需要测试的元素。因此，我正在考虑拥有一个包含所有元素的 vector ，它可能适合我从 2 次计时攻击中获得的信息。

任何提示都将不胜感激。

我正在使用 C++。

Answer 1

Bit Twiddling Hacks页面显示了如何使用每个生成的数字的 O(1) 工作来枚举所有精确设置 n 位的二进制数。他们的解决方案转载于此:

Suppose we have a pattern of N bits set to 1 in an integer and we want the next permutation of N 1 bits in a lexicographical sense. For example, if N is 3 and the bit pattern is 00010011, the next patterns would be 00010101, 00010110, 00011001,00011010, 00011100, 00100011, and so forth. The following is a fast way to compute the next permutation.

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1

// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

The __builtin_ctz(v) GNU C compiler intrinsic for x86 CPUs returns the number of trailing zeros. If you are using Microsoft compilers for x86, the intrinsic is _BitScanForward. These both emit a bsf instruction, but equivalents may be available for other architectures. If not, then consider using one of the methods for counting the consecutive zero bits mentioned earlier. Here is another version that tends to be slower because of its division operator, but it does not require counting the trailing zeros.

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

从除最后 L 位全为 1 之外全为 0 的数字开始，您应该能够使用它来枚举您想要的所有数字。

希望这对您有所帮助!