# TIL: x &= (x - 1) deletes the rightmost 1 bit in x

published

last modified

2kb

Why does this happen? The a-ha moment is to see what happens when we add $1$ to $x - 1$ which equals $x$. Say we have the number $10$ in decimal as our $x - 1$, and add one to it, this would look like:

The result would be (11 = x):

The astute observer would notice that in $x - 1$ there is a zero at the first one bit in $x$. This is because, what adding $1$ to $x - 1$ will do is place a $1$ bit into the first open position (the first 0). This means that first zero in $x - 1$ will correspond to the first 1 bit in $x$. So if we bitwise & this with the original number this will drop that bit (the rightmost 1 bit) in $x$.

## Why Does This Even Matter?

Well, with this interesting fact counting bits in an integer becomes *slighly* faster than just right shifting the integer and checking if the bitwise & of 1 and x is equal to 1. The primitive `countbits`

may look like this:

Which will have to right shift for every position in x. But with our new found knowledge we can re-write this as:

This way we don't have to count any of the zeroes in the integer. Awesome! +1 for micro optimisations.

## Contact

If you have any comments or thoughts you can reach me at any of the places below.