Bit Manipulation Techniques

Home > Docs > Optimizations > Bit Manipulation

Bit manipulation optimizations operate on individual bits or groups of bits within machine words, exploiting the parallel nature of bitwise operations to achieve constant-time or sub-linear complexity.

Overview

Technique	Use Case	Complexity	Speedup
Population Count	Counting set bits	O(1)	10-50x vs naive
CTZ/CLZ	Finding bit positions	O(1)	8-64x vs loop
Broadword Select	Finding k-th set bit	O(1)	3-10x vs linear
Bit Clearing	Iterating set bits	O(k)	~2x vs masking
PDEP/PEXT	Bit scattering/gathering	O(1)	10-100x

Population Count (Popcount)

Problem: Count the number of 1-bits in a word.

Naive approach: O(64) loop checking each bit.

Portable Broadword Algorithm

Uses SWAR (SIMD-Within-A-Register) to count bits in parallel:

fn popcount_word(mut x: u64) -> u32 {
    // Count bits in pairs (2-bit groups)
    x = x - ((x >> 1) & 0x5555_5555_5555_5555);
    // Sum pairs into nibbles (4-bit groups)
    x = (x & 0x3333_3333_3333_3333) + ((x >> 2) & 0x3333_3333_3333_3333);
    // Sum nibbles into bytes (8-bit groups)
    x = (x + (x >> 4)) & 0x0F0F_0F0F_0F0F_0F0F;
    // Multiply by 0x0101... to sum all bytes into top byte
    ((x.wrapping_mul(0x0101_0101_0101_0101)) >> 56) as u32
}

Magic constants:

0x5555... = 01010101... - masks alternating bits
0x3333... = 00110011... - masks alternating pairs
0x0F0F... = 00001111... - masks alternating nibbles
0x0101... = sum all bytes via multiplication

Performance: ~10 instructions, constant time.

Hardware POPCNT

Modern CPUs provide single-cycle popcount:

#[cfg(target_arch = "x86_64")]
use core::arch::x86_64::_popcnt64;

fn popcount_hw(x: u64) -> u32 {
    unsafe { _popcnt64(x as i64) as u32 }
}

Rust: Use x.count_ones(). It compiles to POPCNT/VPOPCNTDQ (x86) or CNT (ARM) only when the target enables the feature — -C target-cpu=native, or +popcnt on x86; CNT is always available on aarch64 — and falls back to the broadword sequence above otherwise. See SIMD → Popcount Strategies for a measured comparison of count_ones() against explicit SIMD popcount across build modes and array sizes (issue #45).

Prior Art

Wegner (1960): First efficient popcount algorithm
HAKMEM Memo 169 (1972): MIT AI Lab optimizations
Knuth TAOCP Vol 4A: Comprehensive coverage of bitwise tricks

Count Trailing/Leading Zeros (CTZ/CLZ)

Problem: Find position of lowest/highest set bit.

Hardware Instructions

fn ctz(x: u64) -> u32 {
    x.trailing_zeros()  // Compiles to TZCNT/BSF on x86
}

fn clz(x: u64) -> u32 {
    x.leading_zeros()   // Compiles to LZCNT/BSR on x86
}

Usage in succinctly: Finding next set bit for iteration:

// src/util/broadword.rs
fn select_in_word(mut val: u64, mut k: u32) -> u32 {
    loop {
        let t = val.trailing_zeros();
        if k == 0 { return t; }
        k -= 1;
        val &= val - 1;  // Clear lowest set bit
    }
}

Clear Lowest Set Bit

The expression x & (x - 1) clears the lowest set bit:

x     = 0b10110100
x - 1 = 0b10110011
x & (x-1) = 0b10110000

Application: Iterate over set bits efficiently:

while x != 0 {
    let pos = x.trailing_zeros();
    process(pos);
    x &= x - 1;
}

Broadword Select-in-Word

Problem: Find position of the k-th set bit in a word.

CTZ Loop Method

Simple and often fastest on modern CPUs:

fn select_in_word(mut val: u64, mut k: u32) -> u32 {
    loop {
        let t = val.trailing_zeros();
        if k == 0 { return t; }
        k -= 1;
        val &= val - 1;
    }
}

Complexity: O(k) but with single-cycle TZCNT, often faster than broadword.

Vigna's Broadword Select

Constant-time algorithm using parallel operations:

fn select_broadword(x: u64, k: u32) -> u32 {
    // Compute byte popcounts in parallel
    let s = x - ((x >> 1) & 0x5555_5555_5555_5555);
    let s = (s & 0x3333_3333_3333_3333) + ((s >> 2) & 0x3333_3333_3333_3333);
    let s = ((s + (s >> 4)) & 0x0F0F_0F0F_0F0F_0F0F).wrapping_mul(0x0101_0101_0101_0101);

    // Find byte containing k-th bit using parallel comparison
    let b = ((s + 0x0101_0101_0101_0101_u64.wrapping_mul(!k as u64)) >> 7)
        & 0x0101_0101_0101_0101;
    let byte_idx = b.trailing_zeros() / 8;

    // Extract byte and use lookup table
    let byte = (x >> (byte_idx * 8)) as u8;
    let remaining = k - ((s >> ((byte_idx - 1) * 8)) as u32 & 0xFF);
    byte_idx * 8 + SELECT_IN_BYTE_TABLE[(byte as usize) * 8 + remaining as usize]
}

Prior Art

Vigna (2008): "Broadword Implementation of Rank/Select Queries"
Gog & Petri (2014): sdsl-lite library optimizations

PDEP and PEXT (BMI2)

PDEP (Parallel Deposit): Scatter bits to positions marked by mask. PEXT (Parallel Extract): Gather bits from positions marked by mask.

PDEP for Quote Masking

Used in DSV parsing to compute regions inside quotes:

// src/util/simd/x86.rs — the deposit is the only BMI2-specific step
unsafe fn toggle64_bmi2(carry: u64, quote_mask: u64) -> (u64, u64) {
    // Scatter alternating 0/1 pattern to quote positions
    let addend = _pdep_u64(ODDS_MASK << (carry & 1), quote_mask);
    toggle64_from_deposit(carry, quote_mask, addend)
}

// src/util/simd/quote_mask.rs — adder tail, shared with the SVE2 BDEP twin (#182)
fn toggle64_from_deposit(carry: u64, quote_mask: u64, addend: u64) -> (u64, u64) {
    // Use addition with carry propagation to fill between quotes
    let c = carry & 1;
    let result = ((addend << 1) | c).wrapping_add(!quote_mask);

    // Carry for the next chunk is quote-count parity, NOT the adder's
    // overflow: `addend << 1` drops an opener deposited at bit 63 (#149).
    (result, next_carry(carry, quote_mask))
}

Result: 10x faster than prefix_xor, 50-100x faster than scalar — where PDEP is fast. AMD Zen 1/2 implement it in ~18-cycle microcode, so DSV dispatch gates this arm on has_fast_bmi2() and falls back to AVX2 prefix_xor there (#182).

PEXT for Bit Gathering

// Extract bits at positions marked by mask
let result = _pext_u64(data, mask);

Application: Compress sparse bit patterns, extract structural characters.

When NOT to Use PDEP

Failed optimization in succinctly: BMI2 PDEP for BitWriter was 71% slower (3.4x regression).

// DON'T DO THIS - PDEP is slow for consecutive bits
let deposited = _pdep_u64(bits, mask);  // 3-cycle latency
// Simple shift+OR is faster for ranges:
let result = (bits << offset) | existing;  // 2 cycles total

Lesson: PDEP excels at sparse bit operations, not consecutive ranges.

Prior Art

Intel BMI2 (2013): Haswell introduced PDEP/PEXT
Langdale & Lemire (2019): simdjson uses PEXT for JSON parsing

Bit Reversal and Rotation

Bit Reversal

Reverse bits in a word (useful for certain tree encodings):

fn reverse_bits(mut x: u64) -> u64 {
    x = ((x & 0x5555_5555_5555_5555) << 1) | ((x >> 1) & 0x5555_5555_5555_5555);
    x = ((x & 0x3333_3333_3333_3333) << 2) | ((x >> 2) & 0x3333_3333_3333_3333);
    x = ((x & 0x0F0F_0F0F_0F0F_0F0F) << 4) | ((x >> 4) & 0x0F0F_0F0F_0F0F_0F0F);
    x.swap_bytes()
}

Rotation

fn rotate_left(x: u64, n: u32) -> u64 {
    x.rotate_left(n)  // Single instruction on modern CPUs
}

Broadword ASCII Skipping

UTF-8 validation clears runs of ASCII with a single high-bit test rather than inspecting each byte, which is the whole reason text/utf8/broadword.rs exists:

const HI: u64 = 0x8080_8080_8080_8080;

// All eight bytes are ASCII iff no byte has its high bit set.
if u64::from_ne_bytes(chunk) & HI == 0 {
    pos += 8;
}

Two details make it work in practice:

Width matters more than the test. Eight bytes per test beats a byte-at-a-time loop several times over, but four words OR-ed together before one test — 32 bytes — is what closes the gap to core::str::from_utf8, which tests sixteen. On an M4 Pro that step took pure-ASCII throughput from 14.9 to 57.2 GiB/s.

Locating the first non-ASCII byte uses CTZ on the masked word. Memory byte k has its high bit at 8k + 7 on a little-endian host, so (8k + 7) >> 3 == k:

fn first_high_byte_le(hi: u64) -> usize { (hi.trailing_zeros() >> 3) as usize }
fn first_high_byte_be(hi: u64) -> usize { (hi.leading_zeros()  >> 3) as usize }

Guard the load on the current byte already being ASCII. Attempting the skip unconditionally costs a wasted load and test on every sequence of multi-byte-heavy text, which is pure loss on patterns like emoji or CJK where it can never fire.

Even guarded, this kernel is not a strict win: its wide probe pays off on long ASCII runs but loses geometric mean against the scalar validator's own 8-byte ASCII skip (from a separate change, #133) across realistic mixed content — see utf8-validate.md for the measured numbers and why it ships as an opt-in engine rather than the default, alongside why a table-driven DFA lost to whole-sequence validation for the multi-byte step.

Usage in Succinctly

Technique	Location	Purpose
Popcount	`bits/popcount.rs`	Rank queries, index building
CTZ loop	`util/broadword.rs`	Select-in-word
Bit clearing	`util/broadword.rs`	Set bit iteration
PDEP toggle	`util/simd/x86.rs`	Quote region masking (10x faster)
Broadword	`bits/popcount.rs`	Portable popcount fallback
High-bit test	`text/utf8/broadword.rs`	ASCII run skipping (opt-in, ~2x)
CTZ >> 3	`text/utf8/broadword.rs`	First non-ASCII byte in a word

Key Lessons

Hardware beats software: Use count_ones(), trailing_zeros() which compile to single instructions
Profile before optimizing: CTZ loop often beats "optimal" broadword due to branch prediction
Know your instructions: PDEP is for sparse patterns, not consecutive bits
Bit clearing idiom: x &= x - 1 is fundamental for iteration
Shorten the loop-carried chain, not the table: a compact DFA table still serializes one byte per state -> step -> state hop; independent range comparisons retire a whole sequence per iteration and beat the DFA alternative for UTF-8 validation by ~26% in that head-to-head (a ratio unaffected by which scalar baseline was used for either side)

References

Knuth, D. E. "The Art of Computer Programming, Volume 4A: Combinatorial Algorithms"
Warren, H. S. "Hacker's Delight" (2nd ed., 2012)
Anderson, S. "Bit Twiddling Hacks" (Stanford Graphics)
Vigna, S. "Broadword Implementation of Rank/Select Queries" (2008)

Navigation Menu

Repository navigation

bit-manipulation.md

bit-manipulation.md

Bit Manipulation Techniques

Overview

Population Count (Popcount)

Portable Broadword Algorithm

Hardware POPCNT

Prior Art

Count Trailing/Leading Zeros (CTZ/CLZ)

Hardware Instructions

Clear Lowest Set Bit

Broadword Select-in-Word

CTZ Loop Method

Vigna's Broadword Select

Prior Art

PDEP and PEXT (BMI2)

PDEP for Quote Masking

PEXT for Bit Gathering

When NOT to Use PDEP

Prior Art

Bit Reversal and Rotation

Bit Reversal

Rotation

Broadword ASCII Skipping

Usage in Succinctly

Key Lessons

See Also

References

FilesExpand file tree

bit-manipulation.md

Latest commit

History

bit-manipulation.md

File metadata and controls

Bit Manipulation Techniques

Overview

Population Count (Popcount)

Portable Broadword Algorithm

Hardware POPCNT

Prior Art

Count Trailing/Leading Zeros (CTZ/CLZ)

Hardware Instructions

Clear Lowest Set Bit

Broadword Select-in-Word

CTZ Loop Method

Vigna's Broadword Select

Prior Art

PDEP and PEXT (BMI2)

PDEP for Quote Masking

PEXT for Bit Gathering

When NOT to Use PDEP

Prior Art

Bit Reversal and Rotation

Bit Reversal

Rotation

Broadword ASCII Skipping

Usage in Succinctly

Key Lessons

See Also

References