检查一个字节中的ON位数?
我知道我们可以通过使用逻辑OR设置字节中的任何位,并且可以通过逻辑AND清除任何位
val |= (1<<order_number_of_bit_to_set); //for setting some specific number of bit
并清理一下
val &= ~(1<<order_number_of_bit_to_clear); // specific bit to clear
但我的问题是我们如何检查在字节中设置了多少和哪些有序数字位。
例如,如果我们有
val = 0x22;
这意味着在字节中设置第2和第5位
什么是高效,快速和最短的方式来做到这一点?
想到的快速解决方案是迭代所有位并检查它们的顺序以及是否设置记录并显示位的顺序。
但有没有其他有效的方法来做到这一点?
您应该检查此内置函数声明,您可以使用函数__builtin_popcount(unsigned int x)返回x中的1位数。
修改自@ 0x499602D2上面的答案:
int pos[sizeof(/* decltype(val) */)]; int bits_on = 0; for (int i = sizeof(/* decltype(val) */) * CHAR_BIT - 1; --i;) { pos[i] = (val >> i) & 1; if(pos[i]) bits_on++; }
给出总数和位置。
可以稍微优化开启位的计数。
int bits_on(int x) { x = (x & 0x55555555) + ((x>>1) & 0x55555555); x = (x & 0x33333333) + ((x>>2) & 0x33333333); x = (x & 0x0F0F0F0F) + ((x>>4) & 0x0F0F0F0F); x = (x & 0x00FF00FF) + ((x>>8) & 0x00FF00FF); x = (x & 0x0000FFFF) + ((x>>16) & 0x0000FFFF); return x; }
但必须通过循环找到位置。 (这是其他人的答案。)
这是两种算法的组合,它们的迭代次数与设置位的次数相同:
unsigned count_low_zerobits(unsigned n) { static const unsigned MultiplyDeBruijnBitPosition[32] = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 }; return MultiplyDeBruijnBitPosition[((n & -n) * 0x077CB531U) >> 27]; } unsigned find_bits(unsigned n, unsigned positions[]) { unsigned c; for (c = 0; n; c++) { unsigned bitnum = count_low_zerobits(n); // get bit number of lowest bit positions[c] = bitnum; // put number to positions array n ^= 1 << bitnum; // use XOR to unset just this one bit } return c; }
有关count_low_zerobits
更多信息的参考:问题的答案 设置的最低有效位的位置 。
函数find_bits
然后简单地调用它,将给定位位置放到结果数组中,并使用它来使用按位异或来取消设置该位。
最后,为方便起见,我用来测试一段丑陋的代码:
#include #include int main(void) { unsigned positions[128] = {0}; int testnumber = 4442344; unsigned count = find_bits(testnumber, positions); // non-standard, leaking one-liner for debug purposes, remove if fails to compile: printf ("Number in binary: %s\n", itoa(testnumber, malloc(129), 2)); printf("%u bits: ", count); for(unsigned i = 0 ; i < count ; ++i) { printf("%u ", positions[i]); } printf("\n"); return 0; }