# Isolate the lowest set bit

If we want to isolate the lowest bit that is 1 in an unsigned integer `x`, we can do this by calculating `x & ~(x - 1)`.

It can be easily to derive. First, suppose x is not 0, it must have a bit that is 1. The lowest set bit is the first bit that is one from least significant bit to most significant bit. Subtracting one from x changes the lowest bit to 0 and sets all the lower bits to 1. All the higher bits remains unchanged. Therefore `x & ~(x - 1)` has a single bit set to 1, namely the lowest set bit. Now, suppose x is 0, subtracting one from x underflows, resulting a word in which all bits are set to one. Again, `x & ~(x - 1)` is 0.

A similar derivation shows that `x & (x - 1)` replaces the lowest bit that is one with zero. For example, if `x = (00101100)`, then `x - 1 = (00101011)`, so `x & (x - 1) = (0010100)`. This fact is very useful.

## Parity calculation

The parity of a binary word is 1 if the number of 1s in the word is odd, otherwise, it is 0.

### Solution #1

We iteratively test the value of each bit while tracking the number of 1s so far seen. Since we only care if the number of 1s is odd or even, we can store the number modulo 2.

```int parity(unsigned int x) {
int res = 0;

while (x) {
result ^= (x & 1);
x >>= 1;
}
return res;
}
```

Above method is a brute-force algorithm, the time complexity is O(n), where n is the word size.

### Solution #2

Use aforementioned `x & (x - 1)` clears the lowest bit that is one, we can improve solution #1, let the time complexity O(k), where k is the number of 1s in word.

```int parity(unsigned int x) {
int res = 0;

while (x) {
result ^= 1;
x &= (x - 1);
}
return res;
}
```