# 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.