Determine which single bit in the byte is set

bit-manipulation, bitflags, c, optimization

Solution

Can I do this without iteration?

It is indeed possible.

How do I most efficiently determine the position of the set bit?

You can try this algorithm. It splits the char in half to search for the top bit, shifting to the low half each time:

int getTopSetBit(unsigned char b) {
  int res = 0;
  if(b>15){
    b = b >> 4;
    res = res + 4;
  }
  if(b>3){
    b = b >> 2;
    res = res + 2;
  }

  //thanks @JasonD
  return res + (b>>1);
}

It uses two comparisons (three for `uint16`s, four for `uint32`s...). and it might be faster than your loop. It is definitely not shorter.

Based on the idea by Anton Kovalenko (hashed lookup) and the comment by 6502 (division is slow), I also suggest this implementation (8-bit => 3-bit hash using a de-Bruijn sequence)

int[] lookup = {7, 0, 5, 1, 6, 4, 3, 2};

int getBitPosition(unsigned char b) {
  // return lookup[(b | (b>>1) | (b>>2) | (b>>4)) & 0x7];
  return lookup[((b * 0x1D) >> 4) & 0x7];
}

or (larger LUT, but uses just three terms instead of four)

int[] lookup = {0xFF, 0, 1, 4, 2, 0xFF, 5, 0xFF, 7, 3, 0xFF, 0xFF, 6, 0xFF, 0xFF, 0xFF};

int getBitPosition(unsigned char b) {
  return lookup[(b | (b>>3) | (b>>4)) & 0xF];
}

Problem

I have a `byte` I'm using for bitflags. I know that one and only one bit in the `byte` is set at any give time. Ex: `unsigned char b = 0x20; //(00100000) 6th most bit set` I currently use the following loop to determine which bit is set: ``` int getSetBitLocation(unsigned char b) { int i=0; while( !((b >> i++) & 0x01) ) { ; } return i; } ``` How do I most efficiently determine the position of the set bit? Can I do this without iteration?

Original source

Related problems