检查位的数目对在一个字节？ [英] checking the number of bits ON in a byte?

问题描述

我知道我们可以用逻辑或设置字节的任何位，并且可以通过逻辑清除任何位
喜欢

I know we can set any bit in the byte by using logical OR and can clear any bit by logical AND like to

    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

但我的问题是，我们如何可以检查多少和下令位数是在字节设置。

but my question is how can we check that how many and which ordered number bits are set in the byte.

例如，如果我们有

    val = 0x22;

这意味着第二和第五位在字节设置

it means that 2nd and 5th bit is set in the byte

什么是高效，快速，最简单的办法做到这一点？

what is the efficient, quick and shortest way to do this?

来考虑快速的解决办法是通过所有的位迭代，并检查他们的订单，如果它被设置记录并显示该位的顺序。

The quick solution that came to mind is to iterate through all bits and check their order and if it is set record and display the order of the bit.

但是否有任何其他有效的方式来做到这一点？

But is there any other efficient way to do this?

推荐答案

下面是两种算法，因为有位设置它迭代多次的组合：

Here's a combination of two algorithms, which iterates as many times as there are set bits:

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 ：的答案问题<一href=\"http://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set\">Position最不显著位被设置。

功能 find_bits 然后简单地调用此，提出给定的位位置，结果数组，并使用它使用逐来​​取消该位异或。

Function find_bits then simply calls this, puts given bit position to result array, and uses it to unset this bit using bitwise exclusive-or.

最后，为了方便，一块的丑的code我用来测试这一点：

Finally, for convenience, a piece of ugly code I used to test this:

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

这篇关于检查位的数目对在一个字节？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！