So today I was working with Vulkan and needed to somehow stringify the state of a `VkDebugReportFlagsEXT`

. I was too lazy to concatenate strings so I decided to only take into account the first bit, and ignore the rest (this is for internal debugging purposes so… meh). So I needed a way to find the lowest set bit in an unsigned integer. Here’s what I came up with:

```
uint find_lowest_set_bit(uint n)
{
return (~(n - 1)) & n;
}
```

Now for a step-by-step explanation of what’s going on, with `A = 01001100`

. First we subtract 1 which sets the right-trailing zeros to 1 and the first set bit (which we are looking for) to 0. Essentially subtracting 1 inverts the lowest bits up to and including the first set bit. This comes up pretty often in bit twiddling.

```
01001100
- 00000001
----------
01001011 = B
```

Since the only bits that changed are the one we are interested in and the ones below it, we look for the bit that was 1 and is now 0, the bits we don’t care about went from 0 to 1. This means we can invert the previous result and `AND`

it with the original number.

If the reasons for this are a bit obscure to you, just imagine two boolean flags representing previous and current states. We need to find when previous was `true`

and current `false`

. This translates in most programming languages to `previous && !current`

. The booleans `&&`

and `!`

operators correspond to the `&`

and `~`

bits operators, so in our case it translates to `A & (~B)`

. **I like to think of bits operators as boolean SIMD instructions**. :)

```
~ 01001011
----------
10110100
& 01001100
----------
00000100
```

And there we go. We can verify that this still works on edge-cases :

```
11111111 00000000
- 00000001 - 00000001
---------- ----------
~ 11111110 ~ 11111111
---------- ----------
00000001 00000000
& 11111111 & 00000000
---------- ----------
00000001 00000000
```

For reference, this compiles to 3 instructions: (with clang)

```
mov rax, rdi
neg rax
and rax, rdi
```

I’m probably not the first one to come up with this, but I like figuring stuff out by myself and sharing it. Also I want to start posting on this blog.

Bonus: this is the first version I came up with : `(((n - 1) ^ n) + 1) >> 1`

, which compiles in one more instruction.

```
lea rax, [rdi - 1]
xor rax, rdi
inc rax
shr rax
```