Bit Shifting from Scratch

01Why bits

An integer in a register is 32 or 64 bits, each a 0 or a 1, and the CPU offers a handful of single-cycle operations that act on those bits directly: shift them sideways, AND, OR, and XOR them. Numeric meaning is a convention layered on top, and bit manipulation works underneath it.

In a game engine that happens constantly, usually in the hottest code:

• 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 (population count), where the lowest set bit is (count trailing zeros). The primitives behind bitset iteration and free-list allocation.

02Binary & two's complement

Positional notation in base two: bit i carries the value 2ⁱ. The byte 0b00101101 is 32 + 8 + 4 + 1 = 45. Because long binary strings are unreadable, we group four bits into one hex digit (a nibble): 0x2D is the same 45. Two nibbles make a byte, four bytes make a 32-bit word.

The right-most bit is the LSB; the left-most is the MSB. For an unsigned 32-bit integer the MSB is just the 2³¹ place. For a signed integer it is the sign.

Two's complement, in one paragraph

Nearly every machine you will ship on stores signed integers in two's complement: the top bit carries negative weight. In 8 bits the value is −128·b₇ + 64·b₆ + … + 1·b₀, so 0b11111111 is −1, not 255. Negating is "flip every bit, then add one" (-x == ~x + 1). Three consequences fall out of this and they drive most of the tutorial:

• There is one more negative value than positive: the range is −2³¹ to 2³¹−1. INT_MIN has no positive twin, so -INT_MIN overflows.
• The sign lives entirely in the top bit, so copying that bit downward (an arithmetic right shift) preserves sign.
• x >> 31 on a signed 32-bit value is either all-zeros (x non-negative) or all-ones (x negative). That all-or-nothing mask is the seed of dozens of branchless tricks.

C++20 went further and declared two's complement the only legal signed representation, ending decades of "in principle a C compiler could use sign-magnitude" hedging^[12]; C23 followed. Click the bits below: the signed and unsigned readings agree until bit 31 is set.

03Left & right shifts

A shift slides every bit a fixed number of places. Left shift (<<) moves bits toward the MSB and feeds zeros in at the bottom. Each step doubles the value, because every bit moves to the next-higher power of two. Right shift (>>) moves bits toward the LSB and (for an unsigned value) feeds zeros in at the top, halving the value and discarding the bit that falls off the bottom.

So x << 3 is x × 8 and x >> 3 is roughly x ÷ 8. The "roughly" matters for negative values, and §6 covers it. Load a negative value and the right shift's two modes (next section) start to matter.

04Signed vs unsigned: SAR and SHR

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 (the x86 instruction is SHR). An arithmetic right shift copies the sign bit into the top, so a negative number stays negative (the instruction is SAR).

In C and C++, unsigned >> is logical. Signed >> of a negative value is implementation-defined in C (still, as of C23) and was in C++ until C++20, which is standardese for "every mainstream compiler sign-extends, but the standard won't promise it." C++20 requires arithmetic right shift for signed types^[12]. On x86, compilers emit SAR for signed and SHR for unsigned^[10]; ARM's equivalents are ASR and LSR.

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

Replacing x * 8 with x << 3 made code faster on early microprocessors with slow or missing multipliers. On the CPUs games ship on today it doesn't, because the compiler already emits the shift (or an equivalent lea) for you. The optimization is called strength reduction, and optimizing compilers have done it for decades.

Two facts retire the myth. First, the barrel shifter makes a shift's cost independent of its distance: shifting by 1 and shifting by 31 are the same price. The "big shifts are slow" intuition dates from the 8086 and 80286, where a shift by the CL register took extra clocks for every bit position. Second, on a modern x86 core an integer multiply is about 3 cycles of latency with one finishing every cycle, and a shift is 1 cycle^[11]. That gap is real in a tight dependent chain, 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

For unsigned values, x / 8 and x >> 3 are identical. For signed values they are not, and the difference is a real bug that survives code review, senior review included, because the two expressions look interchangeable.

The difference is rounding direction. An arithmetic right shift rounds toward negative infinity (it floors): -1 >> 1 is -1, because 0xFFFFFFFF shifted right with sign extension is still 0xFFFFFFFF. But C and C++ integer division rounds toward zero (it truncates): -1 / 2 is 0. So -7 >> 1 is -4 while -7 / 2 is -3. Off by one, only for negatives, only when the division is inexact.

The compiler knows this, which is why signed x / 8 in the widget above was not a single sar. It adds a bias of 2ⁿ−1 to negative operands before shifting, nudging them back toward zero^[5][17]. The bias is computed branchlessly, with the sign-broadcast mask from §4 or a conditional move. Drag the dividend negative: the floor and the true quotient split apart, and the bias closes the gap.

07Undefined behavior & the count-masking footgun

Shifts have a surprising amount of undefined behavior packed into a simple-looking operator. In both C and C++ a shift is undefined when the count is negative, or greater than or equal to the width of the (promoted) left operand. 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 undefined. C++ had a similar rule until C++20, which defines signed left shift as wrapping modulo 2^N[12]. "Undefined" means the compiler may assume it never happens and optimize on that assumption.

The count rule is the practical landmine, because the hardware disagrees with the language. An x86 shift instruction masks the count to the low 5 bits for a 32-bit operand, or 6 bits for a 64-bit operand^[10], so shl eax, 32 leaves eax unchanged (32 masks to 0). 32-bit ARM's register-count shifts use the bottom 8 bits of the count instead, so the same shift by 32 gives 0 there. Leaving the case undefined lets a C compiler emit the bare instruction on each machine without checking the count^[13]. The result: one line with a variable shift count can produce three different answers.

08Rotates, and why C has no rotate operator

A rotate is a shift that wraps: bits that fall off one end reappear at the other, so no information is lost and the population count never changes. CPUs have had rotate instructions for decades (ROL and ROR on x86). Hash functions, cryptographic primitives, and PRNGs lean on them because a rotate moves high bits down and low bits up without throwing any away.

C and C++ have no rotate operator, so for years people wrote the idiom (x << n) | (x >> (32 - n)). That idiom has a bug: when n is 0, the second shift becomes x >> 32, which is the undefined behavior 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

Shifts position a bit; masks act on it. The whole toolkit is four bitwise operators and a couple of idioms, and almost every higher-level trick in this tutorial is built from them^[1]. Knuth catalogs the scholarly version 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: 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. And subtracting 1 borrows through the trailing zeros up to the lowest set bit, so x & (x - 1) erases it. Together they let you walk the set bits of a word in as many steps as there are set bits, not 32 or 64. That is the engine behind iterating a bitset, which is the next section.

10Flags, bitsets & bitboards

The most common bit work in a game is one integer with one bit per yes/no fact. Sixty-four booleans 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 decide whether two objects can collide with a pair of bitmasks. Each body has a category (one bit: which layer it is) and a mask (which 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

An ECS often gives 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. Iterating the matching components 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 to its logical end. A bitboard packs an 8×8 board into a 64-bit word, one bit per square. The payoff is that a shift moves every piece at once: shifting the whole board left by 8 slides every piece one rank north, by 1 one file east. The catch is wraparound. Shifting east moves a piece on the h-file onto the a-file of the next rank, so you AND with a "not the a-file" mask to delete the wrapped bits^[14]. Population count gives material; count-trailing-zeros gives the next occupied square.

11Packing: color & bitfields

Shifts and masks are how you stuff several small values into one word and pull them back out. The canonical example is color. An 8-bit-per-channel RGBA pixel is four bytes packed into a 32-bit word, and the whole codec is shifts on the way in, masks on the way out.

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, 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 seen in 16-bit gradients. Unpacking has to invent the low bits back, usually by replicating the high bits down, (r5 << 3) | (r5 >> 2). Replication maps the top code to 255 exactly (0b11111 becomes 0b11111111) and 0 to 0, so black and full intensity survive the round trip, which a plain r5 << 3 (topping out at 248) does not. Color Cycling §3 applies these conversions to VGA and Amiga palette guns. The widget shows the error.

12Morton order & swizzling

Packing puts independent fields side by side. Morton order does something subtler: it interleaves the bits of two coordinates so that points close together in 2D get keys close together in 1D. Guy Morton described it in a 1966 IBM technical report on file sequencing for a geodetic database^[6], and graphics has leaned on it since.

The encode is pure shift-and-mask: spread x into the even bit positions, spread y into the odd positions, OR them together. Walking the resulting indices 0, 1, 2, 3 traces a recursive Z (hence "Z-order curve"), and that Z keeps spatial neighbors mostly adjacent 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

Before hardware floating point was free, and in any system that needs bit-exact reproducibility today, fractions are stored as integers with an implied binary point. A Q16.16 value is a 32-bit integer; the real number it represents is that integer divided by 2¹⁶.

Conversion is a shift: an integer n becomes 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 do not 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 determinism. Floating-point results can differ across compilers, CPUs, and optimization flags (fused multiply-add here, a different rounding there), which quietly desynchronizes a lockstep simulation where every client must compute 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 an FPU: the SNES and the Game Boy Advance did their world math in fixed-point shifts.

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

Computing 1/√x for vector normalization once cost a division and a square root, 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]. Reinterpret 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). Because IEEE 754 puts the exponent in the high bits, the integer value is roughly a scaled, offset base-2 logarithm of the float. A right shift by one halves that integer, which halves the log, which square-roots the value; subtracting from the magic constant 0x5f3759df negates it, turning √x into 1/√x. Reinterpret back to float and you have a seed within about 3.4% of the true value, and one Newton-Raphson step sharpens it to within about 0.18%. Chris Lomont reverse-engineered why the constant is near-optimal in 2003^[8].

Xorshift: a PRNG that is only shifts

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 full-period shift triple such as (13, 17, 5), a 32-bit xorshift runs through all 2³²−1 non-zero states before repeating. It is fast enough for particle jitter, loot rolls, and procedural placement, though it fails some stringent statistical tests and is not 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

Three queries about a word show up everywhere: how many bits are set (popcount), how many leading zeros (clz), how many trailing zeros (ctz). Popcount gives set cardinality and 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.

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 is not available, the classic fallback is a SWAR population count: treat the word as many small lanes, add adjacent pairs, then nibbles, then bytes, halving the lane count each step. Thirty-two bits fall in five fold 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, and look the top five bits up in a 32-entry table^[7].

16Hardware bit-manip: BMI1 and BMI2

Since 2012–2013, x86 has shipped two extension sets, BMI1 and BMI2, that turn several of this tutorial's multi-step idioms into single instructions^[10]. Compilers emit them automatically when you target a recent enough CPU; recognizing them in a disassembly tells you what the source was doing.

Two are worth dwelling on. The variable-count shifts SHLX, SHRX, and SARX do not read or write the flags register and do not pin the count to the CL register, so they avoid a false dependency that the legacy shl reg, cl form carries; each is a single micro-op^[11]. And PDEP collapses the Morton encode from §12 to one instruction per coordinate by depositing each coordinate's bits straight into an interleave mask.

17Pitfalls

The recap, as a checklist of the mistakes that survive 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 tutorial stayed on scalar integer bit work. 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.

For where these bits go next: 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.