Bitwise Optimization Techniques for Counting Set Bits in 32‑Bit Integers

In business‑oriented projects developers spend most of their time ensuring logical correctness, but after correctness comes efficiency, especially time efficiency, which is heavily influenced by the choice of algorithm and low‑level implementation.

The article starts with a simple problem: given a pointer to an array of 32‑bit unsigned integers and its length n , return the number of 1‑bits in each element. A naïve linear scan yields an O(n) algorithm that, when compiled without optimisations, takes about 2 seconds (≈ 1989391 µs ) on the author's machine.

First optimisation replaces division by 2 with a right‑shift and uses a bitwise AND with 0x00000001 to test the least‑significant bit. This reduces the average runtime to 1841008 µs , an 8 % improvement.

Second optimisation applies the classic trick x & (x‑1) to clear the lowest set bit repeatedly, turning the loop into a count‑of‑set‑bits operation. The average time drops to 442782 µs , a 3.5× speed‑up (≈ 0.5 seconds ).

Third optimisation uses a divide‑and‑conquer approach: pairs of bits are summed, then groups of 4, 8, 16, and finally 32 bits, effectively performing parallel counting. This brings the average runtime down to 85499 µs , a 22× improvement (≈ 0.08 seconds ).

Fourth optimisation further reduces data dependencies by processing multiple sub‑words in parallel before merging the results, achieving 66926 µs on average – about 30× faster than the original implementation (≈ 0.07 seconds ).

The author notes that even greater gains are possible with assembly‑level tuning, but the main goal is to illustrate how powerful bitwise tricks can be. A collection of useful bitwise patterns follows, including reading, setting, clearing, and flipping bits, branch‑less absolute value and maximum calculations, and techniques for packing and counting bits without extra space.