Cam's Cyberspace

Recent Notes

Bitwise Operations - Core Logic, Manipulation, and Low-Level Tricks

5 min read

Definition

Bitwise operators directly manipulate binary digits (bits) of integers. They form the foundation of low-level computation, hardware interaction, and high-performance algorithms. Mastering them allows for efficient state encoding, compression, and arithmetic tricks.

Bit manipulation leverages these operators and binary representations to perform fast, memory-efficient computations - foundational in low-level programming, competitive algorithms, and system design.

Why it matters

Note

Bitwise operations are constant time, making them extremely fast for encoding flags, implementing sets, and writing compact algorithms. They are integral in embedded systems, compression algorithms, cryptography, and fast mathematical functions.

Model & Assumptions

Be explicit about the machine model

  • Word size: use fixed-width types (uint32_t, uint64_t) when shifts depend on width.

  • Signed right shift: implementation-defined in C/C++; prefer unsigned for portable logical shifts.

  • Shift range: shifting by >= word size is undefined; guard indices.

  • Two’s complement: most platforms use it; tricks like x & -x rely on two’s complement.

Operators

The Core Bitwise Operators

OperatorSymbolExampleResultDescription
AND&1010 & 110010001 only if both bits are 1
OR|1010 | 110011101 if either bit is 1
XOR^1010 ^ 110001101 if bits differ
NOT~~10100101Flips all bits
Left Shift<<0011 << 10110Moves bits left, inserts 0s
Right Shift>>1010 >> 10101Moves bits right, discards rightmost

Working Example

A = 60 -> 0011 1100
B = 13 -> 0000 1101
 
A & B = 0000 1100 (12)
A | B = 0011 1101 (61)
A ^ B = 0011 0001 (49)
~A    = 1100 0011 (-61 in 2's complement)

Masks

A bitmask is a pattern used to isolate, set, or clear specific bits in a value.

Common Bit Mask Patterns

ActionExpressionEffect
Set kth bitx |= (1 << k)Forces bit to 1
Clear kth bitx &= ~(1 << k)Forces bit to 0
Toggle kth bitx ^= (1 << k)Flips bit
Check kth bit(x >> k) & 1Tests if set
int x = 42;          // 00101010
int mask = 1 << 3;   // 00001000
 
x |= mask;           // Set bit 3 → 00111010
x &= ~mask;          // Clear bit 3 → 00101010
x ^= mask;           // Toggle bit 3

Isolating & Manipulating Bits

Isolate Least Significant Bit (LSB)

int lsb = x & -x;

Extracts only the rightmost 1-bit (two’s complement trick).

Clear LSB

x &= (x - 1);

Removes the lowest set bit - useful for subset enumeration or counting bits.

Power of Two Test

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Works because powers of two have only one bit set (e.g., 1000, 0100).

Count Set Bits (Population Count)

int popcount(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // Clears lowest set bit
        count++;
    }
    return count;
}

Each iteration clears the lowest 1-bit - making it run in O(k), where k = number of set bits.

Tip

These four patterns - power of two, popcount, clear bit, and extract bit - form the “bit-hack core” of many algorithms.

Bit Packing & Fields

Packing multiple small values into one integer saves space and improves cache performance.

int packed = (r << 16) | (g << 8) | b;  // Combine RGB components

Unpacking:

int r = (packed >> 16) & 0xFF;
int g = (packed >> 8) & 0xFF;
int b = packed & 0xFF;

Used heavily in graphics, network protocols, and compression.

Shifts - Signed vs Logical

  • Left shift (<<) → multiplies by powers of two (if no overflow).
  • Right shift (>>) → divides by powers of two (depends on sign).
TypeBehaviorExample
Logical right shiftFills left bits with zeros0001 1010 >> 2 = 0000 0110
Arithmetic (signed) shiftFills left bits with sign bit1110 1000 >> 2 = 1111 1010

Warning

In C/C++, right-shifting negative values is implementation-defined. Always use unsigned integers for portable bit shifts.

Subset Iteration

Represent a subset of {0...n-1} as an integer from 0 to (1<<n)-1. Iterating over all subsets:

for (int mask = 0; mask < (1 << n); mask++) {
    // use subset defined by mask
}

Iterating Submasks

Iterate through all submasks of a given mask:

for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // handle submask
}

Note

This technique is heavily used in bit DP and state compression problems.

Applications

  • Dynamic Programming - encode states as bitmasks
  • Graph problems - represent adjacency and visited sets
  • Set operations - union/intersection via OR/AND
  • Flag management - configuration bits, permissions
  • Cryptographic primitives - fast XOR-based transformations
  • Compression and encoding - compact data representations
  • Graphics and color channels - RGB packing, alpha blending
  • Error detection - checksums, parity bits

Edge Cases & Pitfalls

Warning

0 value: Always handle separately - some bit tricks assume at least one bit is set.

Warning

Overflow: (1 << 31) in 32-bit signed int is undefined - use unsigned types or 64-bit integers. (1 << n) overflows if n ≥ word size.

Warning

Precedence confusion: a & 1 << k means (a & 1) << k, not a & (1 << k). Use parentheses explicitly.

Warning

Signed shifts: Right shifts of negative numbers are implementation-defined in C/C++. Prefer unsigned for logical shifts.

Summary

  • Bitwise operators provide fine-grained control over data representation, enabling optimization beyond what high-level arithmetic can achieve.
  • Bit manipulation enables constant-time arithmetic, fast set logic, and memory efficiency.
  • Learn patterns: x & (x - 1) for clearing, x & -x for extraction, (n & (n - 1)) == 0 for powers of two.
  • Bitmasks unify logic, speed, and compact data representation across low-level and algorithmic contexts.

Graph View

Backlinks