位破解生成给定数为1的所有整数 [英] Bit hack to generate all integers with a given number of 1s

问题描述

我忘了一点技巧来生成给定数为1的所有整数.有没有人记得它(也许也可以解释它)?

I forgot a bit hack to generate all integers with a given number of 1s. Does anybody remember it (and probably can explain it also)?

推荐答案

来自位扭曲的黑客

更新测试程序 在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，依此类推.以下是计算下一个排列的快速方法.

Compute the lexicographically next bit permutation

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

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

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

感谢阿根廷的Dario Sneidermanis，他于2009年11月28日提供了此文件.

Thanks to Dario Sneidermanis of Argentina, who provided this on November 28, 2009.

这篇关于位破解生成给定数为1的所有整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！