Bit Manipulation Example: Counting Set Bits by Clearing the Lowest One

x & (x − 1) switches off the lowest set bit, so a loop that applies it until zero runs once per set bit.

The trick x & (x - 1) switches off the lowest bit of x that is on, so applying it until x is 0 runs once per set bit, a bit that is 1. Subtracting 1 turns the lowest set bit to 0 and every 0 below it to 1, and AND with the original keeps none of those changed bits. On 44, which is 101100, three steps reach 0.

Clearing the lowest set bit of 44 until nothing is left

Inputx = 44

Start, x = 44
1. 0
2. 0
3. 1
4. 0
5. 1
6. 1
7. 0
8. 0
44 is 101100: the bits worth 32, 8 and 4 are on
Step 1, x = 40
1. 0
2. 0
3. 1
4. 0
5. 1
6. 0cleared
7. 0
8. 0
44 − 1 is 101011, and AND with 44 keeps 101000: the bit worth 4 is cleared
Step 2, x = 32
1. 0
2. 0
3. 1
4. 0
5. 0cleared
6. 0
7. 0
8. 0
40 − 1 is 100111, and AND with 40 keeps 100000: the bit worth 8 is cleared
Step 3, x = 0
1. 0
2. 0
3. 0cleared
4. 0
5. 0
6. 0
7. 0
8. 0
32 − 1 is 011111, and AND with 32 keeps nothing: the bit worth 32 is cleared

ResultThree steps, so 44 has three set bits.

A power of two has exactly one set bit, so the trick reaches 0 in one step: x is a power of two when x > 0 and x & (x - 1) is 0. The test x > 0 matters, because 0 also gives 0 and is not a power of two. Its partner x & -x keeps only the lowest set bit, because −x in two's complement is ~x + 1, which flips every bit above the lowest set one. The listing runs all three.

count_set_bits.pypy

def count_set_bits(x: int) -> int:
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count


def is_power_of_two(x: int) -> bool:
    return x > 0 and (x & (x - 1)) == 0


print("set bits in 44:", count_set_bits(44))
print("set bits in 64:", count_set_bits(64))
print("64 is a power of two:", is_power_of_two(64))
print("44 is a power of two:", is_power_of_two(44))
print("lowest set bit of 44:", 44 & -44)
print("int.bit_count on 44:", (44).bit_count())

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

set bits in 44: 3
set bits in 64: 1
64 is a power of two: True
44 is a power of two: False
lowest set bit of 44: 4
int.bit_count on 44: 3

44 has three set bits and 64 has one, so 64 is a power of two and 44 is not, and the lowest set bit of 44 is worth 4. The loop is O(k) for k set bits, at most 32 for a Java int, where checking every bit one by one always takes the full width. Python's int.bit_count, from version 3.10, gives the same 3, and TypeScript, which has no built-in count, uses the loop.

Algorithms

← → move through sections and cards