Bitwise Operators

March 2026 · 30 min read

Bitwise operators work on individual bits of their operands. They are the fundamental building blocks of every bit manipulation technique. Understanding them deeply is essential before moving to the tricks and patterns in later posts.

Bitwise AND (&)

The AND operator compares each bit of two numbers. The result bit is 1 only if both input bits are 1.

  0b11001010   (202)
& 0b10101100   (172)
-----------
  0b10001000   (136)

// In C++:
int result = 202 & 172;  // 136

Mental model: AND is a filter. It keeps only the bits that are set in both operands. If you AND with a mask, you extract only the bits where the mask has 1s. Everything else becomes 0.

Bitwise OR (|)

The OR operator produces a 1 if either or both input bits are 1.

  0b11001010   (202)
| 0b10101100   (172)
-----------
  0b11101110   (238)

Mental model: OR is a combiner. It merges set bits from both operands. Useful for setting specific bits: flags |= NEW_FLAG.

Bitwise XOR (^)

XOR (exclusive OR) produces a 1 if the input bits are different.

  0b11001010   (202)
^ 0b10101100   (172)
-----------
  0b01100110   (102)

Mental model: XOR is a difference detector. It highlights where two values differ. XOR has remarkable properties that make it one of the most useful operators:

• Self-inverse: a ^ b ^ b = a. XOR with the same value twice cancels out.
• Identity: a ^ 0 = a. XOR with zero does nothing.
• Self-cancel: a ^ a = 0. Any number XOR itself is zero.
• Commutative: a ^ b = b ^ a.
• Associative: (a ^ b) ^ c = a ^ (b ^ c).

Bitwise NOT (~)

NOT is a unary operator that flips every bit: 0 becomes 1, 1 becomes 0.

uint8_t x = 0b11001010;   // 202
uint8_t y = ~x;           // 0b00110101 = 53

// For signed 32-bit: ~0 = -1 (all bits set = 0xFFFFFFFF)

Key identity: In two's complement, ~x = -(x+1). Equivalently, -x = ~x + 1.

Left Shift (<<)

Shifts all bits left by the specified number of positions. New bits on the right are filled with 0. Each left shift by 1 multiplies by 2.

uint8_t x = 0b00001010;   // 10
uint8_t y = x << 2;      // 0b00101000 = 40  (10 × 4)

// General: x << n  =  x × 2^n  (if no overflow)

Right Shift (>>)

Shifts all bits right. Each right shift by 1 divides by 2 (rounding toward zero for unsigned, implementation-defined for signed).

uint8_t x = 0b00101000;   // 40
uint8_t y = x >> 2;      // 0b00001010 = 10  (40 / 4)

There are two types of right shift:

• Logical shift: Fills new high bits with 0. Used for unsigned types.
• Arithmetic shift: Fills new high bits with the sign bit (preserving the sign). Used for signed types on most compilers.

// Arithmetic right shift (signed):
int8_t x = -8;            // 0b11111000
int8_t y = x >> 2;       // 0b11111110 = -2  (sign bit replicated)

// Logical right shift (unsigned):
uint8_t u = 0b11111000;   // 248
uint8_t v = u >> 2;       // 0b00111110 = 62  (zeros filled in)

Operator Precedence Trap

Bitwise operators have lower precedence than comparison operators in C++. This is a notorious source of bugs:

// BUG: this is parsed as x & (1 == 1), not (x & 1) == 1
if (x & 1 == 1) { ... }   // WRONG!

// FIX: always use parentheses with bitwise operators
if ((x & 1) == 1) { ... }  // CORRECT

// Precedence order (high to low):
// ~        (NOT, unary)
// << >>   (shifts)
// &        (AND)
// ^        (XOR)
// |        (OR)

Compound Assignment Operators

x &= mask;    // x = x & mask
x |= mask;    // x = x | mask
x ^= mask;    // x = x ^ mask
x <<= n;      // x = x << n
x >>= n;      // x = x >> n

Key Identities

// AND identities:
x & 0         = 0          // AND with zero clears all bits
x & x         = x          // AND with self is identity
x & ~0        = x          // AND with all-ones is identity
x & (x - 1)   clears the lowest set bit

// OR identities:
x | 0         = x          // OR with zero is identity
x | x         = x          // OR with self is identity
x | ~0        = ~0         // OR with all-ones sets all bits

// XOR identities:
x ^ 0         = x          // XOR with zero is identity
x ^ x         = 0          // XOR with self cancels
x ^ ~0        = ~x         // XOR with all-ones flips all bits

// De Morgan's Laws (bitwise):
~(a & b)      = ~a | ~b
~(a | b)      = ~a & ~b

Summary

• AND (&): Both bits must be 1. Filters/extracts bits.
• OR (|): Either bit can be 1. Combines/sets bits.
• XOR (^): Bits must differ. Toggles bits, detects differences.
• NOT (~): Flips all bits. ~x = -(x+1) in two's complement.
• Left shift (<<): Multiply by powers of 2. Fills with zeros.
• Right shift (>>): Divide by powers of 2. Arithmetic vs logical for signed vs unsigned.
• Always parenthesize bitwise expressions due to unintuitive precedence.

GCC/Clang Built-in Intrinsics (CP Essential)

Competitive programmers lean heavily on compiler intrinsics. They compile down to single CPU instructions (POPCNT, BSF/TZCNT, BSR/LZCNT) and are dramatically faster than a hand-written loop.

// All of these take an unsigned int. Behavior is UB if x == 0
// for __builtin_clz / __builtin_ctz, so guard against it.

__builtin_popcount(x)   // # of set bits  (e.g., popcount(0b1011) = 3)
__builtin_ctz(x)        // # of trailing zeros (index of lowest set bit)
__builtin_clz(x)        // # of leading zeros  (31 - floor(log2(x)) for 32-bit)
__builtin_parity(x)     // popcount(x) & 1  (1 if odd # of set bits)

// 64-bit versions: append 'll' (long long)
__builtin_popcountll(x)
__builtin_ctzll(x)
__builtin_clzll(x)
__builtin_parityll(x)

// Common idioms:
int highest_bit  = 31 - __builtin_clz(x);     // floor(log2(x))
int lowest_bit   = __builtin_ctz(x);          // position of lsb set
bool is_pow2     = x && !(x & (x - 1));       // (also __builtin_popcount(x)==1)

#include <bit>
std::popcount(0u)         // 0  (defined, unlike __builtin_clz(0))
std::countr_zero(0b1000u) // 3
std::bit_width(5u)        // 3  (smallest k with 2^k > x, == floor(log2)+1)

Practice Problems

Work through these in order — they exercise everything on this page (truth tables, masks, XOR identities, popcount, parity).

• LeetCode 191. Number of 1 Bits popcount — warmup for __builtin_popcount and the n & (n-1) trick.
• LeetCode 136. Single Number XOR — the canonical "self-cancel" XOR application.
• LeetCode 268. Missing Number XOR / sum — XOR all indices and values; the survivor is the missing one.
• LeetCode 461. Hamming Distance XOR + popcount — popcount(a ^ b) in one line.
• LeetCode 477. Total Hamming Distance bit columns — count contributions per bit position; classic CP pattern.
• LeetCode 371. Sum of Two Integers XOR + AND — addition without +: XOR is sum-without-carry, AND<<1 is the carry.
• LeetCode 89. Gray Code XOR construction — i ^ (i >> 1) generates a Gray code in one expression.
• CSES — Bit Strings modular pow — count length-n bit strings; combinatorics warmup that pairs with this series.