位黑客生成具有给定数量的 1 的所有整数

Question

我忘记了一点技巧来生成具有给定数量的 1 的所有整数。有人记得它吗(并且可能也可以解释它)？

Answer 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";
    }
}

打印

00001001
00001010
00001100
00010001
00010010
00010100
00011000
00100001
00100010
00100100
00101000
00110000
01000001
01000010
01000100
01001000
01010000
01100000
10000001
10000010
10000100
10001000
10010000
10100000
11000000

按字典顺序计算下一位排列

假设我们有一个整数中 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 编译器内部函数返回尾随零的数量。如果您使用的是 Microsoft x86 编译器，则内在函数为 _BitScanForward。它们都发出 bsf 指令，但等效指令可能适用于其他架构。如果不是，则考虑使用前面提到的计算连续零位的方法之一。

这是另一个版本，由于它的除法运算符，它往往会变慢，但它不需要计算尾随零。

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

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