Cam's Cyberspace

Recent Notes

Bitwise Operators — Core Logic and Low-Level Tricks

4 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.

Why it matters

Note

Bitwise operations are constant time, making them extremely fast for encoding flags, implementing sets, and writing compact algorithms.

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|`10101100`1110
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

Bit Masking — The Swiss Army Knife

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

Common Bit Mask Patterns

ActionExpressionEffect
Set kth bit`x= (1 << k)`
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
x |= (1 << 1);   // Set bit 1  -> 00101011
x &= ~(1 << 3);  // Clear bit 3 -> 00100011
x ^= (1 << 0);   // Toggle bit 0

Isolating & Manipulating Bits

Isolate Least Significant Bit (LSB)

int lsb = x & -x;

Extracts only the rightmost 1-bit.

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;
}

Tip

(x & -x) isolates; (x & (x - 1)) clears — these two lines appear in countless 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

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.

Pitfalls

Warning

Overflow: (1 << 31) in 32-bit signed int is undefined — use unsigned types or 64-bit integers.

Warning

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

Tip

Always clarify intent with parentheses — bitwise precedence can differ subtly across languages.

Applications

  • Flag management (e.g., configuration bits, permissions)

  • Cryptographic primitives

  • Subset enumeration in DP

  • Compression and encoding

  • Graphics and color channels

  • Error detection (checksums, parity bits)

Summary

Bitwise operators provide fine-grained control over data representation, enabling optimization beyond what high-level arithmetic can achieve. They remain critical in systems, algorithms, and performance engineering contexts.

See also

Graph View

Backlinks