比特黑客生成给定数量为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));  

__builtin_ctz(v)x86 CPU 的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日提供了此服务.

Answer 2

对于有点黑客,我想参考这个页面:Bit Twiddling Hacks.

关于您的具体问题,请阅读标题为计算字典下一位排列的部分.

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

假设我们在整数中有一个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日提供了此服务.