Problem: A Bit Too Much Counting

In binary notation, we represent numbers using only bits (0 and 1), as opposed to digits (0 through to 9).

If the rightmost bit is 1, this represents a +1. If the second rightmost bit is 1, this represents a +2. In general, if the nth bit from the right is set to 1, it will contribute $2^{n-1}$ to the number we are trying to represent.

For example 1011₂ represents the number $2^0 + 2^1 + 0 + 2^3$ which is 11.

There’s a pretty interesting function commonly known as the popcount (population count) or Hamming weight. Basically, given some positive integer, the popcount will count the number of 1’s in its binary representation.

For example, the popcount of 23 is equal to 4, because $23 = 11101_2$ and there are 4 ones in this.

I first came across this concept when working on a chess engine. I was thinking of ways to represent a chess board so that certain operations such as finding valid moves and counting the number of defending pieces could be done quickly.

An efficient representation is a collection of binary numbers. Each binary number would represent the positions of a certain piece (say the white knight) and the ith bit would be set when there is a white knight on the ith square.

It’s quite convenient that 64 bits is sufficient to encode this information!

Then counting the number of white knights is equivalent to finding the popcount of this 64-bit number. Sure, we could just linearly go through all 64-bits and count them, but there are faster ways.

Your job is to help me do this in as few operations as possible!

So, you have a string of 64 bits and you need to find a fast way to count all of the 1s.

You are allowed to use only arithmetic operations (e.g. addition, subtraction, multiplication, floor division, modulus) and logical operations (e.g. bit shift, AND, OR, NOT, XOR).

You are allowed to store partial calculations, and this is not counted as an operation.

To make this an interesting problem you are not allowed to use:

control flow (if, for, while, do while)
external code / functions
arrays / lookup tables

Hints

Hint 1. If we limit ourselves to only addition, bit shift and AND, can we do it in 128 operations? What about 64? (Think about how we can “extract” each bit.)

Hint 2. It is no coincidence that 64 is a power of 2. If we want to find the popcount of a 64 bit number, can we perform some operations so that we now want to find the popcount of 32 2 bit numbers? We can get to 24 operations.

Hint 3. What about 21 operations? 17? 😮 12? 🤯

What are your ideas and solutions? Even if your ideas don’t work, I would like to hear them in the comments below!

If you’re interested here are some solutions. They have generalised it to work for any size integer, which I think is pretty cool.