checking the number of bits ON in a byte?

Question

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

and for clearing a 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.

for example if we have

    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?

If you need to know not only the number of set bits, but also the positions of the set bits, then no, there is no better way than iterating through them. — us2012, Oct 01 '13 at 01:16
http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer — chux - Reinstate Monica, Oct 01 '13 at 01:24
GCC has `__builtin_popcount*()`, which can be optimized on platforms that have specialized instructions. Other than that, it looks like a [XY question](http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem). Why do you need to know the positions of the bits? — DanielKO, Oct 01 '13 at 01:56
every bit indicates some flag value, that's why I want to know the position. — Abdul Rehman, Oct 01 '13 at 12:39
It might not be faster but it may be more convenient. Look at std::bitset — Neil Kirk, Oct 01 '13 at 13:05

score 1 · Answer 1 · answered Oct 01 '13 at 13:13

1

You should check this Built-Ins declarations you can use the function __builtin_popcount (unsigned int x) Returns the number of 1-bits in x.

answered Oct 01 '13 at 13:13

MissingNumber

1,142
15
29

ryyker · Answer 2 · 2013-10-01T01:26:40.537

0

Modified From @0x499602D2's answer above:

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

Gives total and position.

edited Oct 01 '13 at 01:26

answered Oct 01 '13 at 01:24

ryyker

22,849
3
43
87

score 0 · Answer 3 · answered Oct 01 '13 at 12:54

The count of on bits may be optimized a bit.

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

But the positions have to be found by a loop. (it is in other's answers.)

score 0 · Answer 4 · edited May 23 '17 at 12:13

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

Reference for more info about count_low_zerobits: an answer of question Position of least significant bit that is set .

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.

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

checking the number of bits ON in a byte?

4 Answers4

Linked