Bitwise - get position of first bit in a byte

Question

I'm trying to think of an efficient algorithm that can return a bitmask giving the position of the first bit that is a '1', counted left from the input.

For example: 00010101 should give 00010000 and 11111111 should give 10000000

The obvious way I guess would be to do make a loop that checks first bit and shifts bitwise until end of string, but I would like to avoid loops if at all possible.

Anyone who thinks they have a good solution to this, feel free to post!

what language? this might be a good one to post over on codegolf as a challenge :) — ivanivan, Jul 25 '18 at 22:07
Possible duplicate of [Find the highest order bit in C](https://stackoverflow.com/questions/53161/find-the-highest-order-bit-in-c) — phuclv, Jul 26 '18 at 02:02

zx485 · Answer 1 · 2018-07-25T22:29:29.400

The function/OpCode you are looking for has a name: TZCNT: "Count the Number of Trailing Zero Bits". It is available if your CPU supports the BMI1 instruction set extension. In combination with BTS: "Bit Test and Set" you can achieve your goal with two main OpCodes:

xor   eax, eax                ; Clears EAX and breaks dependencies
tzcnt edx, [memoryOperand]    ; Gets the count of trailing 0's in EDX
bts   eax, edx                ; Sets the bit found by TZCNT in EAX

The bit-space in this example is from 0..31.

Bitwise - get position of first bit in a byte

1 Answers1