Counting the number of ones in a binary number

In this article I will show three different ways of getting the number of ones, or set bits of a binary number. To start off, you can see the expected values here:

This is also called the Hamming Weight of a number. This has uses in some algorithms, such as distributed hash tables, chess algorithms, some data structures, and even one algorithm for finding 5 wordle words which use 25 unique letters efficiently!

Iteration

The simplest, naive method and the one that probably comes to mind first would be to iterate over every single bit of the binary number, and check if it is a one, adding to the total if it is. For a number n his takes around log₂(n) steps.

Implemented in JavaScript, this algorithm would look like this: (note: this and all other code snippets use BigInts in order to remain precise even with large numbers. As a result, all functions take and return BigInts)

const countBits = (x) => {
    let numBits = 0n;
    while (x > 0n) {
        numBits += x & 1n;
        x = x >> 1n;
    }
    return numBits;
}

Each iteration it adds the last bit of the binary number to the total, and then shifts the entire number down. This way, we can avoid having to calculate the length of the number in bits.

Decreasing + Iteration

Believe it or not, we can do this in (usually) fewer than log₂n steps! This slightly trickier way of counting comes from an observation that subtracting one from a number flips all the bits coming before the first set bit, as well as the set bit itself.

Combining this with the AND bitwise operation, we can see that (n) & (n-1) will set the last set bit to zero, as taking the AND of a flipped bit and the bit itself will always result in 0. This means that after doing this operation, n will have one fewer set bits. Combining this all together, we can repeatedly take the AND of n and n-1 and set it to n, and simply count how many iterations it takes for the process to result in 0. That gives us the answer we are looking for!

Implemented, this would look like

const countBits = (x) => {
    let num = x;
    let numBits = 0n;
    while (num > 0n) {
        num &= num - 1n;
        numBits += 1n;
    }
    return numBits;
};

Constant time

There is a constant time solution for this. In our case, we will just show it for numbers up to 2³², but it can be easily expanded with to a higher range.

First, lets just start with just a 3 bit number: n = a₂ * 2² + a₁ * 2¹ + a₀ * 2⁰, where a_n is the nth digit of our number. Our task here is to just isolate the coefficients a₂ + a₁ + a₀. If we write out the results of shifting down:

From this, we can see that n - (n>>1) - (n>>2) is a₂ + a₁ + a₀: because for every single digit a_n * 2ⁿ, a_n * 2^n-1 , a_n * 2^{n - 2} ... a_n * 2⁰ is subtracted. Taking a_n out of the parentheses we get a_n(2ⁿ - 2^n-1 - ... - 2⁰) which results in just a_n. This works just as well for 32 bit numbers!

Sidenote: why is this the case? Can we prove that 2ⁿ - (2^n-1 + 2^n-2 + ... + 2⁰) = 1? Well, this can be shown in a clever way! If we look the the binary of the sum of the first n-1 powers of two, each power of two adds one "1" to the binary number, thus the sum is 111...111₂ with n-1 ones. If we add one to this number, we of course get 100..000₂, where the first set bit is the the nth position, which is equal to 2ⁿ! Therefore, 2ⁿ is one more than the sum of the first n-1 powers of two.

In code, this would look like:

const countBits = (x) => {
    let num = x;
    for (let i = 1n; i < 32n; i++) {
        num -= (x >> i)
    }
    return num;
}

This approach can be modified slightly so that the result can be calculated without any loops or conditionals!

const countBits = (x) => {
    return x - (x >> 1n) - (x >> 2n) - (x >> 3n) - (x >> 4n) - (x >> 5n) - (x >> 6n) - (x >> 7n) - (x >> 8n) - (x >> 9n) - (x >> 10n) - (x >> 11n) - (x >> 12n) - (x >> 13n) - (x >> 14n) - (x >> 15n) - (x >> 16n) - (x >> 17n) - (x >> 18n) - (x >> 19n) - (x >> 20n) - (x >> 21n) - (x >> 22n) - (x >> 23n) - (x >> 24n) - (x >> 25n) - (x >> 26n) - (x >> 27n) - (x >> 28n) - (x >> 29n) - (x >> 30n) - (x >> 31n);
}

With just 1MB and minification, you can extend this function to work with numbers below 2⁸⁴²⁵⁷, or number with around 25000 decimal digits. However, using a loop would probably be better!

Conclusion

Thanks for reading! You can find the source code and tests at github.com/Bulmenisaurus/SoME2.