Given an unsigned int, what's the fastest way to get the "indexes" of the set bits?

Question

So for e.g. 0110 has bits 1 and 2 set, 1000 has bit 3 set 1111 has bits 0,1,2,3 set

Answer 1

I would shift it down and test the least significant bit in a loop. It might be faster testing with 32 bit masks (or whatever length your unsigned int is).

/Allan

Answer 2

for( int i = 0; variable ; ++i, variable >>= 1 ) {
  if( variable & 1 )
    // store bit index - i
}

Answer 3

Depends on what you mean by fastest.

If you mean "simple to code", in .NET you can use the BitArray class and refer to each bit as a boolean true/false.

BitArray Class

Answer 4

If there are really only 4 bits, then the fastest method would certainly involve a lookup table. There are only 16 different possibilities after all.

Answer 5

@Allan Wind...

The extra bit shifts are not needed. It is more efficient to not do a bit shift, as comparing the least significant bit is just as efficient as comparing the 2nd least significant bit, and so on. Doing a bit shift as well is just doubling the bit operations needed.

firstbit = (x & 0x00000001) 
secondbit = (x & 0x00000002) 
thirdbit = (x & 0x00000004)   //<-- I'm not saying to store these values, just giving an example. 
...

All operations on an x86 system anyway are done with 32-bit registers, so a single bit compare would be just as efficient as a 32-bit compare.

Not to mention the overhead of having the loop itself.

The problem can be done in a constant number of lines of code and whether the code is run on an x86 or an x64, the way I describe is more efficient.

Answer 6

Best reference on the Internet for all those bit hacks - bit twiddling hacks

Answer 7

You can take the hybrid approach of iterating through the bytes of the int, use a lookup table to determine the indexes of the set bits in each byte (broken up into nibbles). Then you would need to add an offset to the indexes to reflect its position in the integer.

i.e. Suppose you started with the MSB of a 32 bit int. The upper nibble indexes I will call upper_idxs, and the lower nibble indexes I will call lower_idxs. Then you need to add 24 to each element of lower_idxs, and add 28 to each element of upper_idxs. The next byte would be similarly processed, except the offsets would be 16 and 20 respectively, since that byte is 8 bits "down".

To me this approach seems reasonable, but I would be happy to proven wrong :-)

Cheers, Steve

Answer 8

If it was .NET and you'd have to use it a lot I would like a nice fluent interface.

I would create the following class (not totally happy with the name BitTools).

[Flags]
public enum Int32Bits
{
    // Lookup table but nicer
    None = 0,
    Bit1 = 1,        Bit2  = 1 << 1,  Bit3  = 1 << 2,  Bit4  = 1 << 3,  Bit5  = 1 << 4,  Bit6  = 1 << 5,  Bit7  = 1 << 6,  Bit8  = 1 << 7,
    Bit9  = 1 << 8,  Bit10 = 1 << 9,  Bit11 = 1 << 10, Bit12 = 1 << 11, Bit13 = 1 << 12, Bit14 = 1 << 13, Bit15 = 1 << 14, Bit16 = 1 << 15,
    Bit17 = 1 << 16, Bit18 = 1 << 17, Bit19 = 1 << 18, Bit20 = 1 << 19, Bit21 = 1 << 20, Bit22 = 1 << 21, Bit23 = 1 << 22, Bit24 = 1 << 23,
    Bit25 = 1 << 24, Bit26 = 1 << 25, Bit27 = 1 << 26, Bit28 = 1 << 27, Bit29 = 1 << 28, Bit30 = 1 << 29, Bit31 = 1 << 30, Bit32 = 1 << 31,
}

public static class BitTools
{
    public static Boolean IsSet(Int32 value, Int32Bits bitToCheck)
    {
        return ((Int32Bits)value & bitToCheck) == bitToCheck;
    }

    public static Boolean IsSet(UInt32 value, Int32Bits bitToCheck)
    {
        return ((Int32Bits)value & bitToCheck) == bitToCheck;
    }

    public static Boolean IsBitSet(this Int32 value, Int32Bits bitToCheck)
    {
        return ((Int32Bits)value & bitToCheck) == bitToCheck;
    }
    public static Boolean IsBitSet(this UInt32 value, Int32Bits bitToCheck)
    {
        return ((Int32Bits)value & bitToCheck) == bitToCheck;
    }
}

And you could use it the following ways:

static void Main(string[] args)
{
    UInt32 testValue =  5557; //1010110110101;

    if (BitTools.IsSet(testValue, Int32Bits.Bit1))
    {
        Console.WriteLine("The first bit is set!");
    }
    if (testValue.IsBitSet(Int32Bits.Bit5))
    {
        Console.WriteLine("The fifth bit is set!");
    }
    if (!testValue.IsBitSet(Int32Bits.Bit2))
    {
        Console.WriteLine("The second bit is NOT set!");
    }
}

For each (U)Int size you could make another Int*Bits enum and the correct overloads of IsSet and IsBitSet.

EDIT: I misread, you're talking about unsigned ints, but it's the same in this case.

Answer 9

Two steps:

Step 1: Extract each set bit with set_bit= x & -x; x&= x - 1;

Step 2: Subtract 1 and count bits set.

MSN

Answer 10

I think it will help

import java.util.*;
public class bitSet {

    public static void main(String[]args) {
        Scanner scnr = new Scanner(System.in);
        int x = scnr.nextInt();
        int i = 0;
        while (i<32) {
            if ( ((x>>i)&1) == 1) {
                System.out.println(i);
            }
            i++;
        }
    }
}