Bit-Manipulation

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.

Sizing a buffer or hash table to the next power of two is a classic — and people keep reinventing it with shifts and leading_zeros. The standard library already has it.

You’ve probably seen (or written) the bit-twiddling version, which is easy to get subtly wrong on edge cases like 0 or exact powers:

1
2
3
4
5
6
7
8
9

fn round_up_manual(n: u32) -> u32 {
    let mut v = n - 1;        // underflows when n == 0
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v + 1
}

next_power_of_two does exactly this, correctly, for every unsigned integer type:

1
2
3
4

assert_eq!(5u32.next_power_of_two(), 8);
assert_eq!(8u32.next_power_of_two(), 8);   // already a power of two
assert_eq!(1u32.next_power_of_two(), 1);
assert_eq!(0u32.next_power_of_two(), 1);   // the tricky one, handled

A common use is rounding an allocation up so masking can replace modulo:

1
2
3
4
5
6
7

let requested = 100usize;
let cap = requested.next_power_of_two();   // 128
assert_eq!(cap, 128);

// because cap is a power of two, idx % cap == idx & (cap - 1)
let idx = 1234usize;
assert_eq!(idx % cap, idx & (cap - 1));

The one trap: if the next power of two doesn’t fit in the type, next_power_of_two panics in debug and wraps to 0 in release. When the input is untrusted, reach for checked_next_power_of_two, which hands you an Option instead:

1
2
3

assert_eq!(200u8.next_power_of_two(), 0);          // wraps in release — bug waiting to happen
assert_eq!(200u8.checked_next_power_of_two(), None); // explicit, safe
assert_eq!(100u8.checked_next_power_of_two(), Some(128));