0

我知道我们可以使用逻辑 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 位

什么是有效、快速和最短的方法来做到这一点？

想到的快速解决方案是遍历所有位并检查它们的顺序，如果设置记录并显示位的顺序。

但是有没有其他有效的方法来做到这一点？

4

4 回答 4

1

您应该检查此内置函数声明，您可以使用函数 __builtin_popcount (unsigned int x) 返回 x 中 1 位的数量。

于 2013-10-01T13:13:53.900 回答
0

修改自上述@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++;
}

给出总数和位置。

于 2013-10-01T01:24:09.543 回答
0

这是两种算法的组合，它迭代的次数与设置的位数一样多：

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 <stdio.h>
#include <stdlib.h>

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;
}
于 2013-10-01T13:44:59.237 回答
0

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

但是必须通过循环找到位置。（它在其他人的答案中。）

于 2013-10-01T12:54:43.853 回答