Bit Manipulation Basics: AND, OR, XOR & Shifts

Bit manipulation means working directly with the binary digits (bits) of an integer — treating a number as a row of on/off switches. It powers fast, memory-tiny solutions: flags packed into one integer, set membership in O(1), and clever O(1) math tricks. This page covers the bitwise operators (AND, OR, XOR, NOT, shifts) and the four fundamental single-bit operations: get, set, clear, toggle.

The bitwise operators

Each operator works on the bits of its operands in parallel. Numbers below are shown in binary for clarity.

Operator	Symbol	`1100 ? 1010`	Meaning
AND	`&`	`1000`	1 only where both bits are 1
OR	`\|`	`1110`	1 where either bit is 1
XOR	`^`	`0110`	1 where bits differ
NOT	`~`	flips all bits	bitwise complement
left shift	`<<`	`a << k`	multiply by `2^k`
right shift	`>>`	`a >> k`	divide by `2^k` (floor)

int a = 12, b = 10;     // 1100, 1010
int andv = a & b;       // 8   (1000)
int orv  = a | b;       // 14  (1110)
int xorv = a ^ b;       // 6   (0110)
int notv = ~a;          // -13 (two's complement)
int shl  = a << 1;      // 24  (multiply by 2)
int shr  = a >> 1;      // 6   (divide by 2)

int a = 12, b = 10;     // 1100, 1010
int andv = a & b;       // 8   (1000)
int orv  = a | b;       // 14  (1110)
int xorv = a ^ b;       // 6   (0110)
int notv = ~a;          // -13 (two's complement)
int shl  = a << 1;      // 24  (multiply by 2)
int shr  = a >> 1;      // 6   (signed shift, divide by 2)

let a = 12, b = 10;     // 1100, 1010
let andv = a & b;       // 8   (1000)
let orv  = a | b;       // 14  (1110)
let xorv = a ^ b;       // 6   (0110)
let notv = ~a;          // -13 (operates on 32-bit signed)
let shl  = a << 1;      // 24  (multiply by 2)
let shr  = a >> 1;      // 6   (sign-propagating shift)

a, b = 12, 10           # 1100, 1010
andv = a & b            # 8   (1000)
orv  = a | b            # 14  (1110)
xorv = a ^ b            # 6   (0110)
notv = ~a               # -13 (arbitrary-precision two's complement)
shl  = a << 1           # 24  (multiply by 2)
shr  = a >> 1           # 6   (floor divide by 2)

Language note: JavaScript bitwise operators coerce operands to 32-bit signed integers — so 1 << 31 is negative and shifting past 31 wraps. Use >>> for an unsigned right shift in JS. Java also has >>> (unsigned/logical right shift) alongside the signed >>. Python integers are arbitrary precision, so ~ and shifts behave as if there were infinitely many sign bits — there is no fixed width. C++ signed-overflow/left-shift-into-sign-bit is technically undefined; use unsigned when shifting high bits.

XOR — the operator worth memorizing

XOR (^) is the star of interview bit tricks because of three properties:

x ^ 0 == x (XOR with zero changes nothing)
x ^ x == 0 (a value XORed with itself cancels)
XOR is commutative and associative (order doesn’t matter)

Together these mean XORing a list cancels out every value that appears an even number of times — the basis of the “find the single number” problem in the common bit tricks page.

Get, set, clear, and toggle a bit

These four operations are the vocabulary of bit manipulation. Bit positions are counted from 0 at the least-significant (rightmost) bit. The mask 1 << i isolates bit i.

bool getBit(int x, int i)   { return (x >> i) & 1; }       // read bit i
int  setBit(int x, int i)   { return x | (1 << i); }       // force bit i to 1
int  clearBit(int x, int i) { return x & ~(1 << i); }      // force bit i to 0
int  toggleBit(int x, int i){ return x ^ (1 << i); }       // flip bit i

boolean getBit(int x, int i)  { return ((x >> i) & 1) == 1; } // read bit i
int     setBit(int x, int i)  { return x | (1 << i); }        // force bit i to 1
int     clearBit(int x, int i){ return x & ~(1 << i); }       // force bit i to 0
int     toggleBit(int x, int i){ return x ^ (1 << i); }       // flip bit i

const getBit    = (x, i) => (x >> i) & 1;       // read bit i
const setBit    = (x, i) => x | (1 << i);       // force bit i to 1
const clearBit  = (x, i) => x & ~(1 << i);      // force bit i to 0
const toggleBit = (x, i) => x ^ (1 << i);       // flip bit i

def get_bit(x, i):    return (x >> i) & 1        # read bit i
def set_bit(x, i):    return x | (1 << i)        # force bit i to 1
def clear_bit(x, i):  return x & ~(1 << i)       # force bit i to 0
def toggle_bit(x, i): return x ^ (1 << i)        # flip bit i

For beginners: A mask is just a number whose bits you’ve arranged to select certain positions. 1 << i is a mask with a single 1 at position i; ANDing with it tests that bit, ORing sets it, and ~mask (AND) clears it.

Multiply and divide by powers of two

Shifting is the fastest way to multiply or divide by a power of two — though modern compilers do this automatically, recognizing the pattern still helps you read code.

int times8 = x << 3;   // x * 8
int div4   = x >> 2;   // x / 4  (floor for non-negative x)

int times8 = x << 3;   // x * 8
int div4   = x >> 2;   // x / 4  (floor for non-negative x)

const times8 = x << 3; // x * 8 (within 32-bit range)
const div4   = x >> 2; // x / 4 (floor for non-negative x)

times8 = x << 3        # x * 8
div4   = x >> 2        # x // 4 (floor)

Pitfall: Right-shifting a negative signed integer in C++/Java/JS floors toward negative infinity, not toward zero — -7 >> 1 is -4, not -3. For negatives, integer division and shifting disagree.

Complexity

Every operation here is O(1) — a single CPU instruction on numbers up to the machine word size. That’s why bit tricks are so prized: they replace loops with constant-time arithmetic.

When to use it

Compact sets and flags, parity checks, subset enumeration in backtracking, and the speed tricks on the next page. Ready for the clever stuff? Continue to common bit tricks.