Bit Shifting Deep Dive

March 2026 · 24 min read

Left Shift in Detail

Left shift by $k$ moves every bit $k$ positions to the left. The $k$ vacated positions on the right are filled with 0. Bits that shift beyond the width are lost.

uint8_t x = 0b00110101;   // 53
uint8_t y = x << 2;      // 0b11010100 = 212

// Mathematically: x << k = x × 2^k (mod 2^n for n-bit type)
// 53 × 4 = 212 ✓

// Overflow: if high bits shift out, they are lost
uint8_t z = 0b11000000 << 1;  // 0b10000000 (top bit lost)

Right Shift: Logical vs Arithmetic

Logical Right Shift

Fills vacated high bits with 0. Always used for unsigned types.

uint8_t x = 0b11010100;   // 212
uint8_t y = x >> 2;      // 0b00110101 = 53

// Mathematically: x >> k = ⌊x / 2^k⌋ for unsigned
// 212 / 4 = 53 ✓

Arithmetic Right Shift

Fills vacated high bits with the sign bit. Used for signed types (implementation-defined in C++, but virtually all compilers do arithmetic shift).

int8_t x = -24;           // 0b11101000
int8_t y = x >> 2;       // 0b11111010 = -6

// The sign bit (1) is replicated into the top positions
// Mathematically: ⌊-24 / 4⌋ = -6 ✓

// But watch out for negative odd numbers:
int8_t a = -7;            // 0b11111001
int8_t b = a >> 1;       // 0b11111100 = -4 (rounds toward -∞, not toward 0!)
// -7 / 2 = -3.5 → arithmetic shift gives -4 (floor)
// But integer division gives -3 (truncate toward zero)

Shift Undefined Behavior

// UB 1: Shifting by negative amount
x << -1;    // UNDEFINED

// UB 2: Shifting by >= bit width
uint32_t x = 1;
x << 32;    // UNDEFINED (shift amount must be in [0, 31])

// UB 3: Left-shifting a negative value (until C++20)
int x = -1;
x << 1;     // Undefined before C++20, defined as -2 in C++20

// UB 4: Left-shifting into or past the sign bit (before C++20)
int x = 1;
x << 31;    // UB before C++20 if int is 32-bit (sets sign bit)

Shift-Based Tricks

Fast Multiplication

// x * 2   = x << 1
// x * 4   = x << 2
// x * 8   = x << 3
// x * 10  = (x << 3) + (x << 1)
// x * 12  = (x << 3) + (x << 2)
// x * 15  = (x << 4) - x
// x * 100 = (x << 6) + (x << 5) + (x << 2)

Computing Average Without Overflow

// (a + b) / 2 might overflow if a + b > INT_MAX
// Fix: use the bit manipulation identity
int average(int a, int b) {
    return (a & b) + ((a ^ b) >> 1);
}
// (a & b) = bits both have in common (sum without carry)
// (a ^ b) = bits that differ (carry bits, halved)
// Together: exact average without overflow!

Sign of an Integer

int sign(int x) {
    return (x >> 31) | (!!x);
    // Returns -1 for negative, 0 for zero, 1 for positive
}
// x >> 31: -1 if negative, 0 otherwise (arithmetic shift)
// !!x: 0 if zero, 1 if nonzero

Reversing Bits

uint32_t reverseBits(uint32_t n) {
    n = ((n & 0x55555555) << 1)  | ((n >> 1) & 0x55555555);
    n = ((n & 0x33333333) << 2)  | ((n >> 2) & 0x33333333);
    n = ((n & 0x0F0F0F0F) << 4)  | ((n >> 4) & 0x0F0F0F0F);
    n = ((n & 0x00FF00FF) << 8)  | ((n >> 8) & 0x00FF00FF);
    n = (n << 16) | (n >> 16);
    return n;
}
// Swap adjacent bits, then pairs, then nibbles, then bytes, then halves
// Same divide-and-conquer pattern as parallel popcount

Summary

• Left shift: multiply by $2^k$. Fills right with zeros.
• Logical right shift (unsigned): divide by $2^k$. Fills left with zeros.
• Arithmetic right shift (signed): divide by $2^k$ rounding toward $-\infty$. Fills left with sign bit.
• Shift amount must be non-negative and less than the bit width.
• Average without overflow: (a & b) + ((a ^ b) >> 1).
• Bit reversal uses the same divide-and-conquer as parallel popcount.

CP Pitfalls & Companion Tricks

A few shift-adjacent gotchas that show up constantly in contests:

Always shift a 64-bit literal for 64-bit masks

// BUG: 1 is `int`. `1 << 40` is UB (shift >= width of int).
long long mask = 1 << 40;          // WRONG

// FIX: shift a long long. Use 1LL (or 1ULL).
long long mask = 1LL << 40;        // OK
unsigned long long all = (1ULL << 63) | ((1ULL << 63) - 1);  // all 64 bits set

Portable Logical Right Shift on Signed Types

If you need a guaranteed zero-fill right shift but your value is in a signed type, cast to the matching unsigned type first. The compiler optimizes the cast away.

int      x = -1;          // 0xFFFFFFFF
int      a = x >> 1;     // implementation-defined (almost always -1)
unsigned u = (unsigned)x >> 1;  // guaranteed 0x7FFFFFFF (logical)

// Works for long long too:
long long y = -1LL;
unsigned long long v = (unsigned long long)y >> 1;  // 0x7FFFFFFFFFFFFFFF

Isolating the Lowest Set Bit: n & -n

In two's complement, -n is ~n + 1. ANDing them isolates exactly the lowest set bit of n (zero if n == 0). Foundational for Fenwick trees and many bit DPs.

int n = 0b10110100;          // 180
int lsb = n & -n;            // 0b00000100 = 4

// Iterate over set bits in O(popcount(n)):
for (int m = n; m; m &= m - 1) {
    int bit = m & -m;        // current lowest set bit
    int idx = __builtin_ctz(m);
    // ... process bit at position idx
}

Brian Kernighan's Trick: n & (n - 1)

Subtracting 1 from n flips its lowest set bit and every zero below it. ANDing with n therefore clears the lowest set bit. This gives an O(popcount) loop instead of O(width).

int popcount(unsigned n) {
    int c = 0;
    while (n) { n &= n - 1; ++c; }
    return c;
}
// Loops only as many times as there are set bits.
// Detect power of two: n && !(n & (n - 1)).

We give counting bits its own deep dive in a dedicated post; mention these here so you have them in muscle memory before getting to the practice problems below.

Practice Problems

These all hinge on shifts, masks, or the tricks above.

• LeetCode 190. Reverse Bits shift + mask — the divide-and-conquer pattern from this page, end-to-end.
• LeetCode 137. Single Number II bit columns — count each bit position mod 3; pure shift & mask.
• LeetCode 260. Single Number III n & -n — partition by the lowest differing bit using the lowest-set-bit trick.
• LeetCode 868. Binary Gap shift loop — scan bits with n >>= 1; track distance between 1s.
• LeetCode 762. Prime Number of Set Bits popcount — combine __builtin_popcount with a tiny prime sieve.
• LeetCode 401. Binary Watch enumeration + popcount — loop hours/minutes, check popcount(h)+popcount(m)==n.
• LeetCode 50. Pow(x, n) fast exponent — binary exponentiation; iterate the bits of n with shifts.
• LeetCode 29. Divide Two Integers shift + subtract — long division using only shifts and subtraction; mind the overflow corner cases.