位破解生成给定数为1的所有整数

我忘记了一点技巧，无法生成给定数为1的所有整数。是否有人记得它(也许也可以解释它)？

最佳答案

从Bit Twiddling Hacks

更新测试程序 Live On Coliru

#include <utility>
#include <iostream>
#include <bitset>

using I = uint8_t;

auto dump(I v) { return std::bitset<sizeof(I) * __CHAR_BIT__>(v); }

I bit_twiddle_permute(I v) {
    I 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.
    I w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
    return w;
}

int main() {
    I p = 0b001001;
    std::cout << dump(p) << "\n";
    for (I n = bit_twiddle_permute(p); n>p; p = n, n = bit_twiddle_permute(p)) {
        std::cout << dump(n) << "\n";
    }
}

打印

按字典顺序计算下一个比特排列

假设我们有一个将N位设置为1的整数的模式，并且我们希望在词典学意义上对N 1位进行下一个排列。例如，如果N为3，并且位模式为00010011，则下一个模式将为00010101、00010110、00011001,00011010、00011100、00100011，依此类推。以下是计算下一个排列的快速方法。

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));

x86 CPU固有的__builtin_ctz(v) GNU C编译器返回尾随零的数目。如果您正在使用x86的Microsoft编译器，则内在函数为_BitScanForward。它们都发出bsf指令，但其他架构也可以使用等效指令。如果不是，则考虑使用前面提到的用于计数连续零位的方法之一。

这是另一个版本，由于其除法运算符而趋向于变慢，但它
不需要计算尾随零。

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

感谢阿根廷的Dario Sneidermanis，他于2009年11月28日提供了此信息。

关于位破解生成给定数为1的所有整数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8281951/