Bit Counting Tricks

Bit Counting Tricks

A set bit is a bit whose value is 1. The number of set bits in an integer is commonly called its set-bit count, population count, or Hamming weight.

Consider:

22 = 10110

The binary representation contains three 1s. Therefore, the set-bit count of 22 is:

3

Bit-counting techniques are useful in problems involving:

• Bitmasks and state compression

• Subset representation

• Hamming distance

• Minimum bit flips

• Powers of two

• Parity

• Dynamic programming on bits

• Low-level data processing

Several methods can count set bits. The best choice depends on the integer width, number of set bits, programming language, and whether one number or an entire range must be processed.

Counting Set Bits

Approach 1

Checking Every Bit Position

The direct method examines every position in the integer.

For a W-bit integer:

• Check whether the current least significant bit is set.

• Add it to the count.

• Shift the number right by one position.

• Repeat for all W bit positions.

Alternatively, create a mask for every position and test:

N & (1 << i)

For a fixed 32-bit integer, this method always examines 32 positions, even if only one bit is set.

Algorithm

• Initialize the set-bit count to 0.

• Examine every bit position in the fixed-width representation.

• Increase the count whenever the selected bit is 1.

• Continue until all W positions have been checked.

• Return the final count.

Time Complexity: O(W), where W is the number of bits in the integer type.

Space Complexity: O(1)

Approach 2

Brian Kernighan’s Algorithm

Brian Kernighan’s algorithm processes only the set bits.

It uses the identity:

N & (N - 1)

This operation clears the lowest set bit of N.

The operation is repeated until the number becomes 0. Since exactly one set bit is removed during every iteration, the number of iterations equals the number of set bits.

Why Does N & (N - 1) Clear the Lowest Set Bit?

Consider:

N = 22 = 10110

Subtracting 1 gives:

N - 1 = 21 = 10101

Apply AND:

10110 & 10101 = 10100

The lowest set bit of 10110 has been cleared.

This happens because subtracting 1:

• Changes the lowest set bit from 1 to 0.

• Changes every bit to its right from 0 to 1.

• Leaves every higher bit unchanged.

When N and N - 1 are combined using AND:

• The lowest set bit becomes 0.

• All lower positions remain 0.

• The higher bits keep their original values.

Dry Run: Count Set Bits in 22

Algorithm

• Initialize the count to 0.

• Continue while the current number is non-zero.

• Replace the number with N & (N - 1) to remove its lowest set bit.

• Increase the count because exactly one set bit was removed.

• Return the count when the number becomes 0.

Time Complexity: O(K), where K is the number of set bits.

Space Complexity: O(1)

In the worst case, every one of the W positions is set, so the complexity becomes O(W).

Comparing the Two Set-Bit Counting Methods

Brian Kernighan’s algorithm performs fewer iterations for sparse bit patterns. However, standard library population-count operations may be implemented using optimized compiler intrinsics or processor instructions and are usually preferable in production code.

Minimum Bit Flips to Convert One Number to Another

To convert integer A into integer B, a bit must be flipped wherever their binary representations differ.

XOR identifies exactly those positions:

differentBits = A ^ B

The XOR result contains:

• 0 where the two bits are equal.

• 1 where the two bits are different.

Therefore, the minimum number of required flips equals the number of set bits in:

A ^ B

Example: Convert 10 into 20

Using five-bit representations:

10 = 01010

20 = 10100

Apply XOR:

01010 ^ 10100 = 11110

The XOR result contains four set bits.

Therefore, the minimum number of bit flips is:

4

Algorithm

• XOR the two numbers to identify every position where their bits differ.

• Store the XOR result as the difference mask.

• Count the set bits in this mask using Brian Kernighan’s algorithm or a population-count operation.

• Return the count as the minimum number of required flips.

Time Complexity: O(K) using Brian Kernighan’s algorithm, where K is the number of differing bits.

Space Complexity: O(1)

Counting Set Bits for Every Number from 0 to N

Suppose the set-bit count is required for every number from 0 through N.

Running a complete bit scan for every number takes:

O(N × W)

Applying Brian Kernighan’s algorithm separately to every number is often faster, but it still repeats work already performed for smaller values.

Dynamic programming can reuse previously calculated answers.

Recurrence Using the Right Shift

The number i >> 1 is obtained by removing the least significant bit of i.

Therefore, the set-bit count of i consists of:

• The set-bit count of i >> 1

• Plus the least significant bit of i

The recurrence is:

bits[i] = bits[i >> 1] + (i & 1)

If i is even, its last bit is 0, so no additional set bit is added.

If i is odd, its last bit is 1, so the answer increases by one.

Example

Consider:

i = 6 = 110

Right shift:

6 >> 1 = 3 = 11

The least significant bit is:

6 & 1 = 0

Therefore:

bits[6] = bits[3] + 0

Since 3 = 11 contains two set bits:

bits[6] = 2

For:

i = 7 = 111

7 >> 1 = 3

7 & 1 = 1

Therefore:

bits[7] = bits[3] + 1 = 3

Recurrence Using the Lowest Set Bit

Another recurrence uses Brian Kernighan’s identity:

bits[i] = bits[i & (i - 1)] + 1

The value:

i & (i - 1)

removes one set bit from i. Therefore, the answer is one more than the already calculated answer for that smaller value.

Both recurrence relations calculate each answer in constant time.

Example: Count Bits from 0 to 8

Algorithm

• Create an answer array of size N + 1.

• Set the answer for 0 to 0 because it contains no set bits.

• Process each number from 1 to N.

• Reuse the answer of a smaller number using either recurrence.

• Store the calculated count for the current number.

• Return the completed answer array.

Time Complexity: O(N) because each number is processed once.

Space Complexity: O(N) because the set-bit count of every number must be stored.

Reversing Bits

Reversing bits means placing the bit at position i into the mirrored position:

W - 1 - i

The width W is part of the problem.

For an eight-bit value:

00001101

The reversed bit pattern is:

10110000

The leading zeros in the original representation become trailing zeros in the result. Therefore, reversing only until the number becomes 0 does not produce a complete fixed-width reversal.

How to Reverse a Fixed-Width Bit Pattern

Maintain:

• The current input number

• A result initially equal to 0

For every one of the W bit positions:

• Shift the result left to make space for the next bit.

• Extract the least significant bit of the input using N & 1.

• Add that bit to the result using OR.

• Shift the input right to expose its next bit.

• Repeat exactly W times.

The core update is:

result = (result << 1) | (N & 1)

Dry Run: Reverse 00001101

Algorithm

• Initialize the reversed value to 0.

• Repeat once for every position in the fixed bit width.

• Shift the reversed value left to create space.

• Extract the input’s least significant bit and place it into that space.

• Shift the input right to expose the next bit.

• Return the reversed value after all positions are processed.

Time Complexity: O(W)

Space Complexity: O(1)

Other Useful Bit-Counting Identities

Check Whether a Number Is a Power of Two

A positive power of two contains exactly one set bit.

Therefore:

N > 0 and (N & (N - 1)) == 0

Examples:

8 = 1000

7 = 0111

1000 & 0111 = 0000

Therefore, 8 is a power of two.

Check Bit Parity

The parity of a bit pattern describes whether it contains an even or odd number of set bits.

• Even set-bit count gives even parity.

• Odd set-bit count gives odd parity.

Parity can be obtained from the set-bit count modulo 2 or by repeatedly XORing groups of bits.

Count Differing Bits

The number of differing positions between two equal-width bit patterns is:

popcount(A ^ B)

This value is also called their Hamming distance.

Complexity Summary

Here, K is the number of set bits being processed.

Fixed-Width and Negative Values

Bit-counting operations on negative numbers require a defined width.

Under a 32-bit two’s-complement representation, a negative value may contain many leading set bits. The count represents its complete 32-bit pattern, not only the visible magnitude.

Language behaviour also differs:

• Unsigned integer types provide a clear fixed-width bit pattern.

• Java provides the zero-filling right shift >>>.

• Signed right shift commonly copies the sign bit.

• Python negative integers behave as though they have infinitely many leading 1s.

• Applying N & (N - 1) directly to a negative Python integer may never reach 0.

When negative inputs are allowed, use the width and masking rules specified by the problem.

Common Mistakes

• Assuming Brian Kernighan’s algorithm does not use a loop.

• Claiming it is always faster without considering built-in population-count operations.

• Modifying the original number when it is needed later.

• Forgetting that N & (N - 1) removes exactly one set bit.

• Applying the algorithm directly to negative arbitrary-precision integers.

• Counting bits without defining the width for negative values.

• Stopping a fixed-width bit reversal when the input becomes 0.

• Forgetting that leading zeros must also be reversed.

• Using signed right shift when a zero-filling shift is required.

• Treating N % 2 as incorrect or always slower than N & 1.

• Using an O(N) answer array when only the total number of set bits from 1 to N is required.

• Confusing set-bit count with the position of the highest set bit.

FAQs

Q1. When is Brian Kernighan’s algorithm better than checking every bit position?

It performs one iteration per set bit, so it is especially effective for sparse bit patterns. For dense values or when a built-in population-count operation is available, the practical performance difference may be smaller.

Q2. How should set bits be counted for negative numbers?

First define a fixed width, such as 32 or 64 bits, and interpret the value using that representation. Unsigned types, zero-filling shifts, or explicit masks prevent sign extension from creating incorrect or non-terminating behaviour.

Q3. Why must bit reversal process exactly W positions?

Leading zeros are part of a fixed-width bit pattern and become trailing zeros after reversal. Stopping when the input becomes zero ignores those positions and changes the intended result.

Q4. Can the total number of set bits from 1 to N be calculated without storing every individual answer?

Yes. At each bit position, set bits follow repeating blocks of zeros and ones. Counting complete blocks and the remaining partial block for every position gives the total in O(log N) time and O(1) auxiliary space.

Q5. Should a built-in population-count function be preferred over a manual algorithm?

Usually yes when the language provides one. It communicates the intention clearly and may use an optimized processor instruction. Brian Kernighan’s algorithm remains important for understanding the underlying identity and for environments without such support.