# Counting Ones

Okay, this one is a short one. Really, it’s mostly on here solely so that I can find it later, and because I can’t a concise explanation on the web anywhere.

So, say you have a bitstring, `11010110`

, and you want to count how many
ones are in it. Trivially, you can perform the below logic to count it, running in `O(n_bits)`

time.

```
int n = 0b11010110; // Yes, C++ 14 introduced binary literals! Yippie!
int count = 0;
while(n > 0)
{
if (n & 1)
count ++;
n >>= 1;
}
```

`O(64)`

isn’t too bad, but it feels like there’s got to be
a better solution (and of course, it’s one of those ones that leaves you
marveling at how simple it is).

Prismoskills
(apparently a skills/interview prep site) highlights that the below logic will
operate in `O(n_ones)`

time. It operates with a bit of bitwise logic that’s
tricky to understand at first but actually quite intuitive.

```
int n = 0b11010110; // Yes, C++ 14 introduced binary literals! Yippie!
int count=0;
while (n!=0)
{
n = n & (n-1);
count++;
}
```

Let us look at the values in `n`

, `n-1`

, and `n & (n-1)`

for each iteration, to get a sense for this magic.

n | n-1 | n&(n-1) | count++ |
---|---|---|---|

1101 0111 |
1101 0110 |
1101 0110 | 1 |

1101 0110 |
1101 0101 |
1101 0100 | 2 |

1101 0100 |
1101 0011 |
1101 0000 | 3 |

1101 0000 |
1100 1111 |
1100 0000 | 4 |

1100 0000 |
1011 1111 |
1000 0000 | 5 |

1000 0000 |
0111 1111 |
0000 0000 | 6 |

So, what looked like a strange abuse of bitwise operations is actually quite elegant. The algorithm generates a bitmask by performing `n-1`

that masks out the lowest one in `n`

at that iteration. This operation knocks a one off of `n`

on each iteration, therefore running in `O(n_bits)`

time.

# Counting Zeros

Suppose you wanted to instead count how many zeros are in a bitstring. Either inverting the bits with `~`

(a bitwise not) and putting the result through the one-counting algorithm or subtracting the
number of ones from `sizeof(type)`

(C/C++) will give you the number of zeros.

Both approaches should run in near-identical runtime, with the invert-and-count-ones approach being marginally faster due to not having to load the literal `sizeof(int)`

into a register from constant memory.

# Hamming Distance

For the curious, this came from a coding challenge on leetcode to calculate the “Hamming Distance” between two numbers, the count of locations in them where their bits differ.

The hamming distance between `0001`

and `0100`

would be 2, since two locations differ. Performing an `XOR`

on the two numbers then counting the ones gives the hamming distance between two values.