223. count_ones — Count Set Bits Without a Loop

Need to count how many bits are set in an integer — flags in a bitmask, a population count, a Hamming weight? Don’t write a shift-and-mask loop. Every integer type has .count_ones(), and it usually lowers to a single CPU instruction.

The hand-rolled version is a loop that masks the low bit and shifts:

1
2
3
4
5
6
7
8

fn count_set_bits(mut n: u32) -> u32 {
    let mut count = 0;
    while n != 0 {
        count += n & 1;
        n >>= 1;
    }
    count
}

It works, but it’s a loop you have to get right, and it’s slower than the hardware can do the same job.

Enter count_ones

1
2

let flags: u32 = 0b1011_0010;
assert_eq!(flags.count_ones(), 4);

One call. It’s available on every integer type (u8..u128, i8..i128), and on most targets it compiles straight to a popcnt instruction.

Where it earns its keep

Hamming distance — XOR two values, then count the bits that differ:

1
2
3

let a: u8 = 0b1100_1010;
let b: u8 = 0b1001_1011;
assert_eq!((a ^ b).count_ones(), 3);

Power-of-two test — a power of two has exactly one bit set:

1
2
3
4
5
6

fn is_power_of_two(n: u32) -> bool {
    n.count_ones() == 1
}

assert!(is_power_of_two(64));
assert!(!is_power_of_two(48));

The rest of the family

count_zeros, leading_zeros, trailing_zeros, leading_ones, and trailing_ones round it out — all single-instruction on modern CPUs. leading_zeros is the trick behind a fast integer log2; trailing_zeros gives you the index of the lowest set bit:

1
2

assert_eq!(0b0010_1000u8.trailing_zeros(), 3); // lowest set bit at index 3
assert_eq!(0b0000_1111u8.count_zeros(), 4);

Next time you reach for a bit-counting loop, reach for count_ones instead. Stable since Rust 1.0.