How to find the first zero bit in a byte?

Question

Algorithms

Hello.
There is a byte, the numbering of bits starts to the RIGHT of ZERO.
Can you please tell me how to find the position of the first zero bit without using a loop?
UPD:
You need to find the rightmost zero bit.

Answer 1

First invert the number (bit not). Now we need to find the rightmost single bit.
You can subtract from the number 1, then all the bits up to this one you are looking for will change. So the xor of the original number and its minus 1 will give us as many single bits at the end as the number of the desired bit was.
Next, you need to calculate the number of unit bits for this number - this is also a well-known task. Let's first imagine that each bit stores how many 1 bits are in that bit. Then we transform it so that each pair of consecutive bits stores a binary number - how many single bits there were in this segment. Then every four bits and at the end all 8 bits. The transition from one level to the next can be done through a sum with a shift. Here is the code:

// пусть x = 00001011b
x = ~x;  // 11110100b
x = x ^ (x-1);  // 11110100 xor 11110011 = 00000111
x = ((x >> 1) & 01010101b)+(x & 01010101b);  // 00 00 01 10
x = ((x >> 2) & 00110011b)+(x & 00110011b);  // 0000 0011
x = ((x >> 4) & 00001111b)+(x & 00001111b);  // 00000011 = 2
x -= 1; // индексация с 0

Separately, you need to check if the original number was 255 - in this case, there is no desired bit, but this code will return 7.
You can do it for more bits, you just need to add more operations and expand the masks. For 32-bit numbers, you will need to add 2 more operations.
Another option with assembler in x86 is the operation popcnt .