Most efficient way to find the index of the only '1' bit in a char variable (in C)

Question

This is an interview question:
You are given a char variable named ch, when you know that it represents a number that in its binary form, only one of its eight bits will be equal to '1'. I.E. , the only possible values for ch are: 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80.
Given the variable ch, I need to write the most efficient code to get the index of that '1' bit. For example: if ch == 0x1 -> result is 0. if ch == 0x4 -> result is 2.

The obvious way is to use switch-case, but I need something more efficient.
Is there any bit manipulation you can do here for efficient implementation?

Answer 1

An unsigned char variable is supposedly only 8 bit wide. In order to encode the position of the bit we need only 3 bits. That means that we can build a 24-bit "table" that contains all 8 of possible 3-bit answers in their natural order

111 110 101 100 011 010 001 000 =

0xFAC688

If your variable ch is known to contain only one 1 bit, then it is a power of 2. Dividing something by ch will right-shift the original value by the index of your 1 bit. So, if we divide the above "table" by your ch three times the answer will get shifted to the lowest 3 bits of the result

unsigned position = (0xFAC688 / ch / ch / ch) & 0x7;

End of story. The above could probably be rewritten more efficiently, while preserving the general principle.

---

Note, that this is basically the same principle that's used in the approaches based on De Bruijn sequences. However, the purpose of De Bruijn sequence is to pack the index table in situations when the original "unpacked" table (like my table above) does not fit into an integer. As an "unpleasant" side effect, De Bruijn sequence reorders the index table, breaking the original natural sequence of indices. This requires extra re-mapping efforts to extract the proper result from the De Bruijn sequence.

With only 24 bits we don't have this problem here, which means that there's no need to involve De Bruijn and its accompanying tricks.

On the other hand, a packed table requires a shorter shift, which will simplify (and thus optimize) the calculation of the divisor to achieve the desired shift's length. In case of De Bruijn sequence, there's no need to calculate the divisor at all - your ch is already it. So, De Bruijn sequence might easily end up being more efficient.