Bit Shifting from Scratch

01Why bits

Your input code needs to know which of a dozen buttons are held this frame. You could keep twelve bools. Or you could keep one integer and give each button one bit of it: say bit 3 for jump, bit 2 for crouch, and so on. Checking a button is then a single AND instruction, and copying, comparing or clearing the whole set is a single integer operation.

That works because an integer in a register is just 32 or 64 bits, each a 0 or a 1, and the CPU has single-cycle instructions that act on those bits directly. It can shift them sideways, and it can combine two integers bit by bit with AND, OR and XOR. Reading the bits as a number is a convention on top. Bit manipulation works underneath it.

In a game engine this kind of code runs constantly, usually in the hottest loops:

• Flags and layers. Which input buttons are down, which collision layers an object belongs to, which components an entity has. One integer, one bit per option, tested with a single AND.
• Packing. An RGBA color is four bytes shifted into one 32-bit word. A draw-call sort key packs material, depth, and pass into one integer so a single integer sort orders the whole frame^[16].
• Spatial keys. Interleaving the bits of an (x, y, z) coordinate produces a Morton code, the address scheme behind texture swizzling, linear octrees, and GPU bounding-volume builders.
• Cheap math. Multiply and divide by powers of two, fixed-point fractions, fast reciprocal-square-root seeds, and shift-based random number generators.
• Counting. How many bits are set (the population count), and where the lowest set bit is (the count of trailing zeros). These two drive bitset iteration and free-slot search in allocators.

The first half of the page builds the tools: binary, the two kinds of right shift, and the bugs each one invites. The second half spends them on engine work.

02Binary & two's complement

You stop in the debugger and a health counter that should read −1 shows 4,294,967,295. Nothing is corrupted: the debugger is reading the same 32 bits as an unsigned number. To see why, you need two things: how bits make a number, and how the sign is stored.

Binary is ordinary place value in base two. Counting from the right and starting at 0, bit i is worth 2ⁱ: 1, 2, 4, 8, 16 and so on. Long binary strings are hard to read, so you usually write them in hex, where each hex digit stands for exactly four bits (a nibble). Two nibbles make a byte, and four bytes make a 32-bit word.

The right-most bit, worth 1, is the least significant bit (LSB). The left-most is the most significant bit (MSB). In an unsigned 32-bit integer the MSB is just the 2³¹ place. In a signed one it holds the sign.

Two's complement: how the sign is stored

Nearly every machine you'll ship on stores signed integers in two's complement. The idea is simple: the top bit counts as a negative place value. In 8 bits the top bit is worth −128 instead of +128, and every other bit keeps its usual value. So 0b11111111 is −128 + 127 = −1, not 255. To negate a number you flip every bit and add one: -x == ~x + 1.

Three consequences fall out of this, and they drive most of the page:

• There is one more negative value than positive: a 32-bit int runs from −2³¹ to 2³¹−1. The most negative value, INT_MIN, has no positive twin, so -INT_MIN overflows.
• The sign lives entirely in the top bit, so a right shift that copies that bit downward keeps negative numbers negative (§4 calls this an arithmetic shift).
• Shifting a signed 32-bit value right by 31 copies the sign bit into every position. The result is all zeros when x isn't negative and all ones (−1) when it is. That all-or-nothing mask is the starting point for many branchless tricks.

C++20 made two's complement the only legal way to store signed integers, so code can rely on it^[12]; C23 did the same. Before that, the standards still allowed other encodings in principle, even though no mainstream compiler used them.

03Left & right shifts

You have a packed color and want its top byte, or you want the bit that stands for collision layer 5. Both jobs start by moving bits sideways, and that's what a shift does.

A shift slides every bit of a value the same number of places. Left shift (<<) moves bits toward the MSB and feeds zeros in at the bottom. Each place doubles the value, because every bit moves up to the next power of two. Right shift (>>) moves bits toward the LSB and throws away the bits that fall off the bottom. For an unsigned value it feeds zeros in at the top, so each place halves the value, rounding down.

So x << 3 is x × 8 and x >> 3 is roughly x ÷ 8. The "roughly" matters for negative values: a right shift has two modes, covered in the next section, and they only differ when the sign bit is set.

04Signed vs unsigned: SAR and SHR

A save-file loader reads a 32-bit field into a uint32_t and shifts it right to halve it. The field held −8. The result is 2,147,483,644 instead of −4. The shift did what it was told: the variable's type picked the wrong kind of shift.

Left shift has one behavior. Right shift has two, and the operand's type picks between them. A logical right shift always feeds zeros into the top bits (the x86 instruction is SHR). An arithmetic right shift fills the top bits with copies of the sign bit, so a negative number stays negative (the instruction is SAR).

In C and C++, >> on an unsigned type is logical. On a negative signed value it's implementation-defined in C (still, as of C23) and was in C++ until C++20. That's standardese for "every mainstream compiler copies the sign bit, but the standard won't promise it." C++20 requires the arithmetic shift for signed types^[12]. On x86, compilers emit SAR for signed and SHR for unsigned^[10]; ARM's equivalents are ASR and LSR. The listing below also uses the all-ones mask from the worked example for a branchless absolute value: XOR with the mask flips every bit of a negative x, and subtracting the mask (−1) adds the one, which is exactly "flip and add one".

int32_t  signedVal   = -8;          // 0xFFFFFFF8
uint32_t unsignedVal = 0xFFFFFFF8u; // same 32 bits, read as unsigned

// Signed >> is arithmetic (SAR): the sign bit copies down.
signedVal   >> 1;   // -4   (0xFFFFFFFC)  divide-by-two stays correct

// Unsigned >> is logical (SHR): zeros come in at the top.
unsignedVal >> 1;   // 0x7FFFFFFC = 2147483644, not -4

// The sign-broadcast trick: -1 if negative, 0 if not.
int32_t signMask = signedVal >> 31;   // 0xFFFFFFFF (all ones)

// Branchless absolute value, from Hacker's Delight.
int32_t mask = x >> 31;             // 0 or -1
int32_t absX = (x ^ mask) - mask;   // flip-and-add-one only when negative
                                    // (overflows for INT_MIN, like abs())

let signed_val: i32 = -8;            // 0xFFFFFFF8
let unsigned_val: u32 = 0xFFFFFFF8;  // same bits, unsigned type

// In Rust the TYPE decides, just like C, but it is guaranteed:
signed_val   >> 1;   // -4            arithmetic, sign copies down
unsigned_val >> 1;   // 0x7FFFFFFC    logical, zero-filled

// Sign broadcast. Rust has no UB here; the semantics are defined.
let sign_mask: i32 = signed_val >> 31;   // -1 (all ones)

// Branchless abs (std has i32::abs; this shows the bit trick).
let mask = x >> 31;                  // 0 or -1
let abs_x = (x ^ mask) - mask;       // panics in debug for i32::MIN, like i32::abs

05Multiply, divide & the "shift is faster" myth

A reviewer asks you to change index * 8 to index << 3 "for speed". On early microprocessors with slow or missing multipliers that was good advice. On the CPUs games ship on today it changes nothing, because the compiler already emits the shift (or an equivalent lea) for you.

Swapping an expensive operation for a cheaper one that gives the same answer is called strength reduction, and optimizing compilers have done it for decades. Two facts retire the myth. First, a modern CPU shifts with a barrel shifter, a circuit that shifts by any distance in one step, so shifting by 1 and by 31 cost the same. Second, on a modern x86 core an integer multiply takes about 3 cycles before its result is ready, and the core can start a new one every cycle; a shift takes 1 cycle^[11]. That gap is real in a long chain of multiplies that each wait for the last, but closing it is the compiler's job, and the disassembly below shows it doing so.

So when should you write a shift? When the value is a bit pattern, not a number. color >> 24 says "pull out the alpha byte." 1u << layer says "the bit for this layer." Writing those as color / 16777216 or pow(2, layer) would be obfuscation. Use the shift to signal bit work; use * and / for arithmetic and trust the compiler to reduce it.

06The signed-division trap

A gameplay programmer writes offset >> 4 to divide a signed offset by 16. The tests pass, but QA reports a one-unit error that only happens west of the origin, where the offset is negative. For unsigned values, x / 16 and x >> 4 are identical. For signed values they aren't, and the bug survives review because the two expressions look interchangeable.

The difference is which way each one rounds. An arithmetic right shift rounds toward negative infinity: it floors. C and C++ integer division rounds toward zero: it truncates. For positive numbers both just drop the fraction, so they agree. For a negative number that doesn't divide evenly, flooring goes one further from zero than truncating does.

Sometimes the floor is what you want. If a tile map finds a pixel's 16-pixel tile with x >> 4, pixel −1 lands in tile −1, which is correct, while x / 16 would put it in tile 0 alongside pixels 0 to 15. The bug is swapping one for the other without noticing that the rounding changed.

The compiler knows this, which is why signed x / 8 in the widget above wasn't a single sar. Before shifting a negative number right by n, it adds a bias of 2ⁿ−1, which nudges the floor back up to the truncated answer^[5][17]. It picks the bias without a branch, using the all-ones sign mask from §4 or a conditional move.

07Undefined behavior & the count-masking footgun

A bitset helper builds a mask of the low n bits with (1u << n) - 1. It passes every test until someone asks for all 32 bits. On x86 the result is then 0 instead of all ones, and a different compiler, or the same compiler at a different optimization level, can give a different answer from the same line.

That's undefined behavior (UB): code the C and C++ standards place no requirements on. The compiler may assume it never happens and optimize on that assumption, so the program can do anything. Shifts carry a surprising amount of it. In both C and C++ a shift is UB when the count is negative, or when it's greater than or equal to the bit width of the left operand (after small types are promoted to int). C adds a rule for signed left shifts: shifting a negative value, or shifting a positive one so far that the result doesn't fit, is also UB. C++ had a similar rule until C++20, which defines signed left shift as wrapping around modulo 2^N[12].

The count rule is the practical landmine, because the hardware disagrees with the language. An x86 shift instruction keeps only the low 5 bits of the count for a 32-bit operand, or the low 6 bits for a 64-bit one, and ignores the rest^[10]. 32-bit ARM's register-count shifts use the bottom 8 bits of the count instead. Leaving the case undefined lets a C compiler emit the bare instruction on each machine without checking the count first^[13]. The result: one line with a variable shift count can produce three different answers.

08Rotates, and why C has no rotate operator

A hash table with 1,024 buckets picks a bucket from the low 10 bits of a key's hash. If the hash is weak and the keys differ only in their high bits (IDs that count up in steps of 65,536, say), every key lands in bucket 0. A good hash mixes high bits down into the low ones without losing any, and a rotate is one of its standard tools for that.

A rotate is a shift that wraps around: bits that fall off one end come back in at the other. Nothing is lost, so the number of set bits never changes. CPUs have had rotate instructions for decades (ROL and ROR on x86). Hash functions, cryptographic code and pseudo-random number generators (PRNGs) all lean on them.

C and C++ have no rotate operator, so for years people wrote the idiom (x << n) | (x >> (32 - n)): shift left, shift the bits that fell off back in from the right, and OR the two halves. That idiom has a bug: when n is 0, the second shift becomes x >> 32, which is the UB from §7. The safe version masks the complement: (x << n) | (x >> ((-n) & 31))^[22]. GCC 14 and Clang 20 compile both forms to a single ROL at -O2; MSVC 19.4x recognizes the naive form but emits two shifts and an OR for the masked one. Since C++20, std::rotl and std::rotr from <bit> end the guesswork: they are defined for every count, including 0 and negative counts^[12].

#include <bit>     // C++20
#include <cstdint>

// The classic idiom. Correct ONLY for 1 <= n <= 31.
uint32_t rotl_naive(uint32_t value, int n) {
    return (value << n) | (value >> (32 - n));   // UB when n == 0
}

// The safe hand-written form: mask the complement so n == 0 works.
uint32_t rotl_safe(uint32_t value, int n) {
    return (value << (n & 31)) | (value >> ((-n) & 31));
}

// The right answer in C++20: defined for every n, compiles to ROL.
uint32_t rotl_std(uint32_t value, int n) {
    return std::rotl(value, n);
}

// Rust has had rotate in the standard library from the start.
// These are defined for every count and lower to ROL / ROR.
let rotated_left  = value.rotate_left(n);    // u32 -> u32
let rotated_right = value.rotate_right(n);

// Writing the shift idiom by hand would panic in debug builds if the
// shift amount reached 32 (Rust checks shift overflow), so use the
// built-ins.

09The mask toolkit

An entity's flags word says it's visible, selectable and on fire. Gameplay code needs to read one of those bits, set another and clear a third without touching the rest. Shifts put a 1 in the right position; masks then act on that position.

A mask is just an integer whose set bits pick the positions you care about. The whole toolkit is four bitwise operators (AND, OR, XOR, NOT) and a couple of idioms, and almost every later trick on this page is built from them^[1]. AND keeps only the bits set in both inputs, OR sets any bit set in either, XOR flips the bits where the mask has a 1, and NOT (~) flips every bit. Knuth catalogs the full collection under "Bitwise Tricks and Techniques"^[4].

The last two deserve a second look because they fall straight out of two's complement. -x is ~x + 1, and the +1 carries back through the flipped trailing zeros. So -x matches x at the lowest set bit and below, and is inverted everywhere above it. x & -x therefore keeps exactly that bit. Subtracting 1 borrows through the trailing zeros up to the lowest set bit, so x & (x - 1) erases it.

Together these let you visit the set bits of a word in as many steps as there are set bits, instead of testing all 32 or 64. That's how a bitset is iterated, which is the next section.

10Flags, bitsets & bitboards

Bullets should hit players, enemies and walls, but fly through each other. Pickups should only react to the player. The most common bit work in a game answers questions like these with one integer per object and one bit per yes/no fact. Sixty-four of those facts fit in a single 64-bit word, which one load brings in and the §9 operators test and combine without a branch.

Collision layers and masks

Physics engines often decide whether two objects can collide with a pair of bitmasks. Each body has a category (one bit: which layer it's on) and a mask (the layers it accepts). Two bodies collide only if each one's category is in the other's mask: (catA & maskB) != 0 && (catB & maskA) != 0. Box2D's manual states the rule in exactly these terms, variable names and all, with one addition: a non-zero group index shared by both shapes overrides the masks^[20]. Unity's layer collision matrix is a grid of checkboxes over the same kind of per-layer masks. Two ANDs replace a lookup table.

Bitsets as component signatures

In an Entity Component System (ECS), an entity is just an ID and its data lives in separate component arrays. Many ECS designs give each entity a bitset "signature": bit k set means the entity has component k. A system that wants everything with Position and Velocity builds a query mask and accepts an entity when (signature & queryMask) == queryMask, meaning every required bit is present. Iterating the components an entity has means walking the set bits with the x & (x - 1) idiom from §9. The same pattern drives free-list allocators (a set bit is a free slot) and dirty-flag tracking.

Bitboards

Board games take this furthest. A bitboard packs an 8×8 board into a 64-bit word, one bit per square. In the common layout used here, squares are numbered row by row from a1 = 0 to h8 = 63. The payoff is that one shift moves every piece at once: shifting the whole board left by 8 slides every piece one rank north, and left by 1 slides it one file east. The catch is wraparound. Shifting east moves a piece on the h-file (the right edge) onto the a-file (the left edge) of the next rank, so you AND with a "not the a-file" mask to delete the wrapped bits^[14]. A count of the set bits gives material; the index of the lowest set bit gives the next occupied square.

11Packing: color & bitfields

A particle system stores a color per particle. Four separate bytes per color work, but it's often handier to keep the color in one 32-bit word, red, green, blue and alpha side by side, so it copies and compares as a single integer. Shifts and masks are how you stuff several small values into one word and pull them back out.

For an 8-bit-per-channel RGBA color, packing shifts each channel into its own byte of the word and ORs them together. Unpacking shifts the wanted byte down to the bottom and ANDs with 0xFF to drop everything above it.

uint32_t pack(uint8_t r, uint8_t g, uint8_t b, uint8_t a) {
    return (uint32_t(r) << 24) | (uint32_t(g) << 16)
         | (uint32_t(b) <<  8) |  uint32_t(a);
}

// Cast to uint32_t BEFORE shifting. (uint8_t(r) << 24) would promote to
// int and, for r >= 128, push a 1 into the sign bit: undefined behavior
// in C and before C++20 (§7).

uint8_t red(uint32_t c)   { return (c >> 24) & 0xFF; }
uint8_t green(uint32_t c) { return (c >> 16) & 0xFF; }
uint8_t blue(uint32_t c)  { return (c >>  8) & 0xFF; }
uint8_t alpha(uint32_t c) { return  c        & 0xFF; }

fn pack(r: u8, g: u8, b: u8, a: u8) -> u32 {
    (r as u32) << 24 | (g as u32) << 16 | (b as u32) << 8 | a as u32
}

// In Rust the `as u32` widens before the shift, so there is no sign-bit
// hazard. Shifting a u32 left into bit 31 is just a value, never UB.

fn red(c: u32)   -> u8 { ((c >> 24) & 0xFF) as u8 }
fn green(c: u32) -> u8 { ((c >> 16) & 0xFF) as u8 }
fn blue(c: u32)  -> u8 { ((c >>  8) & 0xFF) as u8 }
fn alpha(c: u32) -> u8 {  (c        & 0xFF) as u8 }

Squeeze the same color into 16 bits and you get RGB565: 5 bits of red, 6 of green and 5 of blue. It's still used for framebuffers and textures where bandwidth matters more than fidelity^[15]. Packing drops the low bits of each channel (r >> 3, g >> 2, b >> 3), and those bits are gone. A smooth 8-bit gradient collapses to 32 (or 64) levels, which is the banding you see in 16-bit gradients. Unpacking has to invent the low bits back, usually by copying the high bits down into the gap: (r5 << 3) | (r5 >> 2). That maps the top code to 255 exactly (0b11111 becomes 0b11111111) and 0 to 0, so black and full intensity survive the round trip. A plain r5 << 3 tops out at 248. Color Cycling §3 applies these conversions to VGA and Amiga palette entries.

12Morton order & swizzling

A texture is stored row by row, so the texel directly below the one you just read is a whole row away in memory, likely on another cache line. Bilinear filtering reads a 2×2 block every time, so half of every lookup lands far from the other half. You want a memory order where points close together in 2D are also close together in 1D.

Morton order gives you that. Packing puts independent fields side by side; Morton order interleaves the bits of two coordinates instead. The encode is pure shift-and-mask: spread x into the even bit positions, spread y into the odd positions, and OR them together. Guy Morton described it in a 1966 IBM report on ordering the records of a geodetic database^[6].

Walking the indices 0, 1, 2, 3 traces a Z shape, and the Zs repeat at every scale (hence "Z-order curve"). That keeps spatial neighbors mostly near each other in memory. GPUs commonly store textures in tiled or swizzled layouts, Morton order or close relatives of it, so that a 2D sampling neighborhood tends to share cache lines instead of spanning several rows. Linear octrees and quadtrees store nodes sorted by Morton code, computing parent and child relationships with shifts instead of pointer chases (the spatial partitioning tutorial builds those trees). Parallel BVH builders in the LBVH family sort primitives by Morton code as their first step.

For wider coordinates you do not loop bit by bit. The standard trick is a sequence of shift-and-mask steps with "magic" constants that spread the bits in logarithmically few operations, the same lane-by-lane style as the SWAR popcount in §15^[1]. On x86 with BMI2, one PDEP per coordinate deposits its bits into an interleave mask, so a 2D encode is two PDEPs and an OR (§16).

13Fixed-point arithmetic

An RTS sends only player commands over the network, and every machine runs the same simulation from them. If one machine computes a unit's position as 10.000001 and another as 10.000002, the two games start to drift apart, and the gap only grows. One fix is to do the simulation's fractional math with integers, which give bit-identical results everywhere.

Fixed point stores a fraction as an integer with an imaginary binary point at a fixed position. A Q16.16 value is a 32-bit integer whose top 16 bits are the whole part and bottom 16 bits the fraction; the real number it stands for is that integer divided by 2¹⁶ (65,536). Converting an integer n is a shift: n << 16. Addition and subtraction just work, because the points line up. Multiplication is where the shift earns its keep: multiplying two Q16.16 values gives a result scaled by 2³², so you shift the product right by 16 to put the point back, using a 64-bit intermediate so the high bits don't fall off. Division shifts the other way.

using fixed = int32_t;            // Q16.16
constexpr int SHIFT = 16;

// The left shifts here rely on C++20 defining them for negative values.
// In C and older C++ that is UB (§7): multiply by 65536 there instead.
fixed fixed_from_int(int n) { return n << SHIFT; }

fixed fixed_mul(fixed a, fixed b) {
    // 32x32 -> 64 so the top bits survive, then shift the point back.
    int64_t wide = int64_t(a) * int64_t(b);
    return fixed(wide >> SHIFT);
}

fixed fixed_div(fixed a, fixed b) {
    // Pre-scale the dividend so the quotient keeps 16 fraction bits.
    int64_t wide = int64_t(a) << SHIFT;
    return fixed(wide / b);
}

type Fixed = i32;                 // Q16.16
const SHIFT: u32 = 16;

// Rust defines << on negative signed values, so no special case.
fn fixed_from_int(n: i32) -> Fixed { n << SHIFT }

fn fixed_mul(a: Fixed, b: Fixed) -> Fixed {
    // Widen to i64 so the product does not overflow, then re-align.
    let wide = a as i64 * b as i64;
    (wide >> SHIFT) as Fixed
}

fn fixed_div(a: Fixed, b: Fixed) -> Fixed {
    // Pre-scale the dividend so the quotient keeps 16 fraction bits.
    let wide = (a as i64) << SHIFT;
    (wide / b as i64) as Fixed
}

Fixed point survives in 2026 because of that determinism. Floating-point results can differ across compilers, CPUs and optimization flags (a fused multiply-add here, a different rounding there), which quietly desynchronizes a lockstep simulation, where every client runs the same simulation from the same inputs and must get bit-identical results^[18]. Integer math is exactly reproducible by construction, so some RTS netcode and replay systems still use fixed point rather than pin down every floating-point setting. It was also the practical option on consoles without a floating-point unit (FPU): the SNES and the Game Boy Advance did their world math in fixed point.

14Two famous hacks

Two bit tricks earned their fame in games. The first reads a float's bits as an integer and does arithmetic on them; the second builds a random number generator from nothing but shifts and XORs.

The fast inverse square root

Lighting and physics normalize vectors constantly: divide a vector by its length to make it length 1. That's a multiply by 1/√x, where x is the squared length, and on late-1990s CPUs a division and a square root were both slow. The trick made famous by Quake III Arena (shipped 1999, source released 2005) replaces them with a shift, a subtraction and a few multiplies^[19].

It starts by reading the float's 32 bits as an integer. (Quake does it with a pointer cast, which breaks C's strict-aliasing rule; memcpy or C++20's std::bit_cast is the defined way.) A float stored in the IEEE 754 format keeps its power-of-two exponent in the high bits, so that integer is roughly a scaled and offset base-2 logarithm of the float. Shifting it right by one halves it, which halves the logarithm, which takes the square root of the value. Subtracting the result from the constant 0x5f3759df negates the logarithm, turning √x into 1/√x, while the constant puts the offset back where it belongs. Read the bits back as a float and you have a first guess within about 3.4% of the true value. One Newton-Raphson step, a cheap correction that roughly doubles the number of correct digits, sharpens it to within about 0.18%. Chris Lomont worked out in 2003 why the constant is close to the best possible^[8].

Xorshift: a PRNG that is only shifts

A particle emitter wants a few thousand random offsets a frame, and a replay system wants the same "random" loot rolls every time it plays back from the same seed. Both need a random number generator that is fast, tiny and deterministic. George Marsaglia's 2003 xorshift generators produce a stream of pseudo-random numbers from nothing but shifts and XORs^[9]. Three lines, no multiply, no table: XOR the state with a shifted copy of itself, three times, with carefully chosen shift amounts.

With a well-chosen set of shift amounts such as (13, 17, 5), a 32-bit xorshift visits every non-zero 32-bit value, all 4,294,967,295 of them, before it repeats. (Zero is the one state it can't use: zero shifted and XORed with itself stays zero.) It's good enough for particle jitter, loot rolls and procedural placement, though it fails some stringent statistical tests and isn't suitable for cryptography. Scrambled variants like xorshift128+ improved the quality, and Vigna's xoshiro family has since superseded those in turn^[21].

uint32_t x = seed;          // never zero
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;                 // x is the next output

15Counting bits: popcount, clz, ctz

An allocator keeps one bit per memory slot, set when the slot is free, and needs the first free slot now. A hash table needs to round its size up to the next power of two. A bitboard engine needs to count a side's pieces. All three are one-instruction questions about the bits of a word.

Three queries cover them. The population count (popcount) is how many bits are set. Count leading zeros (clz) is how many zero bits sit above the highest set bit. Count trailing zeros (ctz) is how many sit below the lowest set bit, which is that bit's index. Popcount gives the size of a bitset, and the popcount of a ^ b is the number of positions where two words differ (their Hamming distance). Leading zeros give an integer log base two, which sizes hash tables and buddy allocators. Trailing zeros give the index of the lowest set bit, which is how you iterate a bitset or find the first free slot.

Modern hardware does all three in one instruction: AMD shipped POPCNT and LZCNT with Barcelona in 2007^[14], Intel picked up POPCNT with SSE4.2 in 2008, and TZCNT came with the BMI extensions^[10]. There is a sharp edge: the older bit-scan instructions BSR and BSF leave their result undefined when the input is zero, so clz and ctz of zero need care; LZCNT and TZCNT were defined to return the operand width instead. C++20 wraps all of this in <bit>: std::popcount, std::countl_zero, std::countr_zero, and std::bit_width, each lowering to the hardware instruction when present^[12].

When the instruction isn't available, the classic fallback is a SWAR population count ("SIMD within a register"): treat the word as many small lanes and add them in parallel with ordinary integer arithmetic. First add adjacent bits in pairs, giving 16 two-bit counts, then add adjacent pairs of those into nibbles, then bytes, halving the number of lanes each step. Thirty-two bits fall in five such steps, about fifteen instructions, instead of a 32-iteration loop. The technique goes back to HAKMEM, MIT AI Memo 239 from 1972^[3], and is tabulated in Hacker's Delight^[2]. Trailing-zero counts have a software form too: isolate the lowest set bit, multiply it by a de Bruijn constant (a number built so that each power of two times it leaves a different 5-bit pattern in the top bits), and look those top five bits up in a 32-entry table^[7].

16Hardware bit-manip: BMI1 and BMI2

You open a profile of the bitset loop from §10 and the disassembly says blsr where you wrote x & (x - 1). The compiler has replaced your two-step idiom with one instruction from a bit-manipulation extension.

Since 2012–2013, x86 CPUs have shipped two such extension sets, BMI1 and BMI2 (Bit Manipulation Instructions), that turn several of this page's multi-step idioms into single instructions^[10]. Compilers emit them automatically when you target a recent enough CPU (for example with -mbmi2 or -march=haswell on GCC and Clang). Recognizing them in a disassembly tells you what the source was doing.

Two are worth a closer look. The old variable-count shift, shl reg, cl, has to take its count in the CL register. It also leaves the flags register unchanged when the count is 0, so it has to wait for whichever instruction last wrote the flags, a false dependency, even when nothing reads them. SHLX, SHRX and SARX take the count in any register, never touch the flags, and each decodes to a single micro-op, one of the simple internal operations the core actually executes^[11]. And PDEP takes the low bits of a value and deposits them, in order, into the positions where a mask has 1s. With the mask 0x55555555 (every even bit) it spreads x into the even positions in one instruction, so the Morton encode from §12 becomes one PDEP per coordinate and an OR.

17Pitfalls

Use this as a review checklist: each item is a mistake that survives review because the code looks correct.

• Signed division is not a shift. x / 8 and x >> 3 diverge for negative, inexact values. Write the division and let the compiler add the bias.
• Shift count at or above the width is undefined. value << 32 on a 32-bit type is UB in C and C++, even though x86 masks it to a no-op and Java and JavaScript define the mask. Never let a count reach the width.
• Arithmetic versus logical is decided by the operand type. Shifting through an unsigned reinterpretation gives a logical shift even when the bits mean a negative number.
• Left-shifting a negative value, or into the sign bit, is undefined in C. (C++20 defines it; older C++ doesn't.) Cast to unsigned before packing values into the top bit, as in the RGBA pack from §11.
• The rotate idiom is UB at zero. (x << n) | (x >> (32 - n)) breaks when n is 0. Use std::rotl, or mask the complement.
• Shifting for speed is cargo-culting. The compiler strength-reduces multiplies and divides by constants. Hand-written shifts buy clarity about intent, not cycles.
• (1 << n) - 1 is undefined at the width. Building an all-ones mask of n bits is itself a shift, undefined when n equals the type width. Special-case it or use BZHI.
• Endianness is byte order in memory, not bit weight. Shifts are endianness-independent; only serializing the word to bytes involves endianness.
• PEXT/PDEP are slow on pre-Zen-3 AMD. Gate on vendor and family, not just the CPUID feature flag.
• Bit-scan of zero is undefined on the legacy instructions. BSR/BSF leave the result undefined for input 0; prefer LZCNT/TZCNT or guard the zero case.

18What's intentionally missing, and what's next

This page stayed on bit work in single integers. Several neighbors were left out on purpose. SIMD bit operations (operating on 128, 256, or 512 bits at once, including the pshufb byte-shuffle as a parallel lookup) live in the SIMD tutorial. Bit-reversal permutations and the butterfly addressing behind the FFT are an audio and signal-processing topic. Gray codes, where consecutive values differ in one bit, matter for rotary encoders and some error-tolerant schemes. Entropy coders like rANS pack fractional bits for compression. Constant-time bit tricks for cryptography deliberately avoid data-dependent branches and timing, a discipline of its own.

Next in the series, C++ Containers moves from the bits in one word to how whole arrays, lists and maps sit in memory, and why that layout decides their speed. Later pages put these bits to work: the hash tables tutorial turns hashes into slots with Fibonacci hashing (a multiply and a right shift) and the power-of-two mask h & (m - 1); the spatial partitioning tutorial builds the Morton-ordered octrees from §12; and the memory allocators tutorial uses the alignment mask ((p + a - 1) & ~(a - 1)) that rounds a pointer up to a power-of-two boundary.

19Sources

1. Sean Eron Anderson. "Bit Twiddling Hacks." Stanford Graphics Lab, 1997–2005. graphics.stanford.edu/~seander/bithacks.html. The canonical web reference for branchless bit idioms: lowest-set-bit isolation, bit spreading for Morton codes, parallel population counts, and sign tricks. Code is in the public domain.
2. Henry S. Warren Jr. Hacker's Delight, 2nd ed., Addison-Wesley, 2012. The standard book on integer bit manipulation. Source for the branchless absolute value, the rotate idioms, the SWAR population counts, and the division-by-constant derivations.
3. Michael Beeler, R. William Gosper, Rich Schroeppel. "HAKMEM." MIT AI Memo 239, February 1972. dspace.mit.edu. Item 169 gives the parallel (SWAR) population count on the 36-bit PDP-6/10, the ancestor of every fast popcount fallback.
4. Donald E. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, §7.1.3 "Bitwise Tricks and Techniques." Addison-Wesley, 2011. The exhaustive scholarly treatment of bit operations, magic masks, and broadword computing.
5. Torbjörn Granlund, Peter L. Montgomery. "Division by Invariant Integers using Multiplication." Proc. ACM SIGPLAN PLDI, 1994, pp. 61–72. PDF. The algorithm compilers use to turn division by a constant into a reciprocal multiply and shift, including the bias for signed division covered in §6.
6. Guy M. Morton. "A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing." IBM Ltd., Ottawa, 1966. The first description of the Z-order (Morton) curve: interleaving coordinate bits to preserve spatial locality in a 1D key.
7. Charles E. Leiserson, Harald Prokop, Keith H. Randall. "Using de Bruijn Sequences to Index a 1 in a Computer Word." MIT Laboratory for Computer Science, 1998. PDF (MIT, via Internet Archive). The multiply-and-lookup method for count-trailing-zeros without a hardware instruction.
8. Chris Lomont. "Fast Inverse Square Root." Purdue University tech note, 2003. PDF. Derives why 0x5f3759df is near-optimal and searches for a marginally better constant. The reference analysis of the Quake III hack.
9. George Marsaglia. "Xorshift RNGs." Journal of Statistical Software, 8(14):1–6, 2003. jstatsoft.org. The shift-and-xor random number generators, with periods 2^k−1. Later work (Panneton & L'Ecuyer; Vigna) analyzes their statistical weaknesses and the scrambled successors.
10. Intel. Intel 64 and IA-32 Architectures Software Developer's Manual, Vol. 2: Instruction Set Reference. Entries for SAL/SAR/SHL/SHR (count masked to 5 or 6 bits), ROL/ROR, SHLD/SHRD, SARX/SHLX/SHRX, POPCNT, LZCNT/TZCNT, and the BMI1/BMI2 sets. Mirrored at felixcloutier.com/x86.
11. Agner Fog. "Instruction Tables" and "The Microarchitecture of Intel, AMD and VIA CPUs." Technical University of Denmark. agner.org/optimize. Source for shift and multiply latencies and throughputs, the single-micro-op BMI2 shifts, and the microcoded PEXT/PDEP on pre-Zen-3 AMD.
12. ISO C++. <bit> header (P0553 "Bit operations" and P0556), and P1236/P0907 making signed integers two's complement, with arithmetic right shift and wrapping left shift defined. C++20. Reference: cppreference.com/w/cpp/header/bit. Defines rotl, rotr, popcount, countl_zero, countr_zero, bit_width.
13. David Wragg. "Shift Instructions." 2012. david.wragg.org. Shows x86 masking the shift count to 5 bits and 32-bit ARM using the bottom 8 bits, so 1U << 32 differs between them, and notes that only C and C++ define shifts loosely enough for a compiler to use the unadorned machine instruction.
14. Chess Programming Wiki. "Bitboards," "General Setwise Operations," "SSE4," "BMI2." chessprogramming.org. The reference for board-as-64-bit-word representations, the file-mask shift moves, and population-count material evaluation; its SSE4 page records that AMD's K10 (Barcelona) introduced POPCNT and LZCNT as SSE4a's ABM pair.
15. Khronos Group. OpenGL and Vulkan format specifications, packed pixel formats (GL_UNSIGNED_SHORT_5_6_5, VK_FORMAT_R5G6B5, R8G8B8A8). docs.vulkan.org, "Formats". The bit layouts for the color packing in §11: VK_FORMAT_R5G6B5_UNORM_PACK16 has R in bits 11..15, G in 5..10, B in 0..4.
16. Christer Ericson. "Order your graphics draw calls around!" realtimecollisiondetection.net, 2008. realtimecollisiondetection.net. The standard reference for packing a draw call's layer, pass, material and depth into one integer sort key.
17. Randal E. Bryant, David R. O'Hallaron. Computer Systems: A Programmer's Perspective, 3rd ed., Pearson, 2015, ch. 2. The teaching reference for two's complement, the arithmetic-shift division bias, and integer overflow semantics.
18. Glenn Fiedler. "Floating Point Determinism." Gaffer On Games, 2010. gafferongames.com. Why floating-point results vary across compilers, CPUs and build settings, and what it takes to make them match for a deterministic lockstep simulation.
19. id Software. Quake III Arena source release, code/game/q_math.c (Q_rsqrt), GPL, 2005 (code circa 1999). github.com/id-Software. The shipped form of the fast inverse square root, magic constant and all.
20. Erin Catto. Box2D Documentation, Simulation manual, "Filtering." box2d.org/documentation. Gives the category/mask filter rule (catA & maskB) != 0 && (catB & maskA) != 0 used in §10, and the group index that overrides it.
21. Sebastiano Vigna. "xoshiro / xoroshiro generators and the PRNG shootout." prng.di.unimi.it. States that the earlier xorshift-based generators have been "entirely superseded by the new ones, which are faster and better." Supports §14 on xorshift's successors.
22. John Regehr. "Safe, Efficient, and Portable Rotate in C/C++." Embedded in Academia, 2013. blog.regehr.org. Shows the UB in the 32 - n rotate idiom and recommends the masked form (x << n) | (x >> (-n & 31)) used in §8. Its notes on which compilers recognize the idiom date from 2013; §8 states current behavior.