Getting position of a set bit in an integer

Question

I'm using the following trick to iterate through the bits set of an int:

    while (b != 0)
    {
        c = b & (0 - b);
        //Do something...
        b = b ^ c;
    }

Taking as an example the number 4128 (binary 0001000000100000) this works fine because c's values are 32 and 4096.

However, instead of the actual values I would like the positions of those values, these being 5 and 12.

Is there an extra line of code that can be inserted into the loop that will return the position?

Answer 1

You can use Integer.numberOfTrailingZeros to get the bit-index, like this:

while (b != 0)
{
    c = b & (0 - b);
    int index = Integer.numberOfTrailingZeros(c);
    //Do something...
    b = b ^ c;
}

Answer 2

Not an efficient answer, but to honour the trick you are using. I changed it to b &= (b - 1).

int bitCount(int b) {
    int bits = 0;
    while (b != 0) {
        int nextb = b & (b - 1); // Remove the rightmost bit 1

        int power2ofBitIx = b ^ nextb; // Get the lost bit   10..0
        int bitIx = bitCount(power2ofBitIx - 1); // And count 1..1
        // Do something with bitIx

        b = nextb;
        ++bits;
    }
    return bits;
}

Answer 3

Read Jerry Coffin's answer.

You can get positions of set bits of an int using an mask and AND-ing each bit:

int c = 4128;
int two_32 = pow(2, 32);
for (int mask = 1, iter = 1; mask < two_32; mask <<= 1, iter++)
    if (c & mask)
        printf("Flag: %d set\n", iter);

This should print:

Flag: 0 set 
Flag: 5 set

Answer 4

If you're going to make a bitboard game you shouldn't be needing the positions of the bits but the values.

I never saw your while loop before, nice one. Personally I like this one:

int tst = 255;

for(int looper = tst, i = Integer.highestOneBit(looper); looper != 0; looper &= ~i, i = Integer.highestOneBit(looper))
{
    System.out.println(i);
}   

Answer 5

public boolean isBitSet(int position) {

    int value = Integer.parseInt("0000000000000000000000000000000", 2);
    BigInteger b = new BigInteger(String.valueOf(value));
    b = b.setBit(4);
    return b.testBit(4);

}