Bit manipulation

intermediateCommon atGoogleMetaAppleJane StreetCitadelRead firstArraysPractise in the Sandbox →

An integer is a fixed row of bits, and the CPU applies &, |, ^, ~, <<, >> to all of them at once in O(1). That makes an int a tiny set of up to 32/64 flags, gives you identities like x ^ x = 0 (pairs cancel) and x & (x − 1) (drop the lowest 1), and packs state compactly. The traps are width and sign: JS works in 32-bit signed, C# has fixed int/long, Python ints never overflow.

The idea in plain words

Picture a light-switch panel with 8 switches, numbered 0 on the right to 7 on the left. Switch k is worth 2^k, and the panel’s number is the sum of the switches that are on: 10110100 is 128 + 32 + 16 + 4 = 180.

The operators act on every switch at once:

Operator	Rule per bit	Everyday use
a & b (AND)	1 if both are 1	mask: keep only some bits; test a bit
a | b (OR)	1 if either is 1	set bits
a ^ b (XOR)	1 if they differ	toggle bits; cancel pairs (x ^ x = 0)
~a (NOT)	flip every bit	build “everything except” masks
a << k	slide left k places	multiply by 2^k; build 1 << k
a >> k	slide right k places	floor-divide by 2^k

Negative numbers use two’s complement: −x is ~x + 1, and the top bit means “negative”. In 8 bits, 11111111 is 255 unsigned or −1 signed. Same bits, two readings.

See it

Click bits to change a, pick an operation, and watch the result. Try a & (a − 1) and a & −a on a few values until the patterns click; they appear constantly.

Bit playground (8-bit)

click the bits

a (0-255)

76543210

unsigned / signed

a

10110100

180 / -76

a − 1

10110011

179 / -77

a & (a − 1)

10110000

176 / -80

a (bin)0b10110100

result0b10110000

set bits in a4

power of two?no

a & (a − 1): Clears the lowest set bit. a − 1 flips that bit and every 0 below it. In the result row, raised accent cells are bits that differ from a; green = 1; yellow marks bit k.

When to reach for it

The problem says…	Bit idea
“every element appears twice except one”	XOR everything: pairs cancel.
“set of at most ~20-64 small items”, “which subset”, “visited states”	An int as a bitmask set: union |, intersection &, membership (m >> i) & 1.
“enumerate all subsets of n items” (n ≤ ~20)	Loop mask from 0 to 2^n − 1; bit i says whether item i is in.
“count 1-bits”, “Hamming distance”, “power of two?”	popcount, x & (x − 1).
“flags / permissions / options”	Each flag is one bit; combine with |, test with &.
“O(1) extra space” on integer data	XOR or sign tricks sometimes replace a hash set.
DP over subsets	The mask is the state. See advanced DP.

How it works

The core moves

1. Read bit k: (x >> k) & 1.
2. Set / clear / toggle bit k: x | (1 << k), x & ~(1 << k), x ^ (1 << k).
3. Drop the lowest 1: x & (x − 1). Use it to count bits or to test “power of two” (x > 0 and x & (x − 1) == 0).
4. Isolate the lowest 1: x & −x. Fenwick trees are built on this.

Python

bit tricks.py

def get_bit(x: int, k: int) -> int:
    return (x >> k) & 1  # 1. shift bit k down to position 0, mask it


def set_bit(x: int, k: int) -> int:
    return x | (1 << k)


def clear_bit(x: int, k: int) -> int:
    return x & ~(1 << k)


def popcount(x: int) -> int:
    """Kernighan: each x & (x - 1) removes the lowest set bit. Needs x >= 0 in Python."""
    count = 0
    while x:
        x &= x - 1  # 2. one iteration per set bit, not per bit position
        count += 1
    return count


def is_power_of_two(x: int) -> bool:
    return x > 0 and x & (x - 1) == 0  # 3. exactly one bit set


def lowest_bit(x: int) -> int:
    return x & -x  # 4. -x = ~x + 1 matches x only at the lowest set bit


if __name__ == "__main__":
    assert get_bit(0b1010, 1) == 1 and get_bit(0b1010, 0) == 0
    assert set_bit(0b1000, 0) == 0b1001 and clear_bit(0b1111, 2) == 0b1011
    assert popcount(0b1011001000) == 4 == (0b1011001000).bit_count()  # int.bit_count: 3.10+
    assert is_power_of_two(64) and not is_power_of_two(0) and not is_power_of_two(96)
    assert lowest_bit(0b101000) == 0b1000
    assert ~5 == -6  # Python ints are unbounded two's complement: ~x == -x - 1
    assert -1 & 0xFF == 255  # mask to fix a width before printing or counting
    print("ok")

TypeScript

bit tricks.ts

import assert from "node:assert/strict";

// JS bitwise operators work on 32-bit signed integers; `>>> 0` reinterprets as unsigned.
export const getBit = (x: number, k: number): number => (x >>> k) & 1; // 1. shift down, mask
export const setBit = (x: number, k: number): number => (x | (1 << k)) >>> 0;
export const clearBit = (x: number, k: number): number => (x & ~(1 << k)) >>> 0;

/** Kernighan: each x & (x - 1) removes the lowest set bit. */
export function popcount(x: number): number {
  let count = 0;
  x >>>= 0; // treat as unsigned 32-bit so negative inputs terminate too
  while (x !== 0) {
    x = (x & (x - 1)) >>> 0; // 2. one iteration per set bit
    count++;
  }
  return count;
}

export const isPowerOfTwo = (x: number): boolean => x > 0 && (x & (x - 1)) === 0; // 3. one bit set
export const lowestBit = (x: number): number => x & -x; // 4. -x = ~x + 1

assert.equal(getBit(0b1010, 1), 1);
assert.equal(getBit(0b1010, 0), 0);
assert.equal(setBit(0b1000, 0), 0b1001);
assert.equal(clearBit(0b1111, 2), 0b1011);
assert.equal(popcount(0b1011001000), 4);
assert.equal(popcount(-1), 32); // all 32 bits set
assert.ok(isPowerOfTwo(64) && !isPowerOfTwo(0) && !isPowerOfTwo(96));
assert.equal(lowestBit(0b101000), 0b1000);
assert.equal(1 << 31, -2147483648); // the sign bit: surprise!
assert.equal((1 << 31) >>> 0, 2147483648);
assert.equal(2 ** 32 | 0, 0); // values past 32 bits are truncated; use BigInt for 64-bit
console.log("ok");

C#

bit tricks.cs

using System.Numerics;

static int GetBit(int x, int k) => (x >> k) & 1;       // 1. shift bit k down, mask it
static int SetBit(int x, int k) => x | (1 << k);
static int ClearBit(int x, int k) => x & ~(1 << k);

// Kernighan: each x & (x - 1) removes the lowest set bit.
static int Popcount(uint x)                            // uint, so negative ints terminate too
{
    int count = 0;
    while (x != 0)
    {
        x &= x - 1;                                    // 2. one iteration per set bit
        count++;
    }
    return count;
}

static bool IsPowerOfTwo(int x) => x > 0 && (x & (x - 1)) == 0; // 3. exactly one bit set
static int LowestBit(int x) => x & -x;                          // 4. -x = ~x + 1

if (GetBit(0b1010, 1) != 1 || GetBit(0b1010, 0) != 0) throw new Exception("get");
if (SetBit(0b1000, 0) != 0b1001 || ClearBit(0b1111, 2) != 0b1011) throw new Exception("set/clear");
if (Popcount(0b1011001000) != 4 || BitOperations.PopCount(0b1011001000u) != 4) throw new Exception("popcount");
if (Popcount(unchecked((uint)-1)) != 32) throw new Exception("all ones");
if (!IsPowerOfTwo(64) || IsPowerOfTwo(0) || IsPowerOfTwo(96)) throw new Exception("pow2");
if (LowestBit(0b101000) != 0b1000) throw new Exception("lowbit");
if ((-16 >> 2) != -4 || (-16 >>> 2) != 1073741820) throw new Exception("shifts"); // >>> is C# 11+
if (1L << 40 != 1099511627776L) throw new Exception("use long for wide masks");
Console.WriteLine("ok");

x & (x − 1) works because subtracting 1 flips the lowest 1-bit to 0 and every 0 below it to 1; ANDing with the original wipes all of those. So a loop of it runs once per set bit:

Counting set bits: x & (x − 1)

step through

n (0-65535)

x

0

0

0

0

0

0

1

0

1

1

0

0

1

0

0

0

712

x712

count0

Count the 1-bits of 712. A naive loop checks all 10 bit positions; this one loops once per set bit.

↺◀▶ Play▶1 / 10

XOR as cancellation

1. XOR is its own inverse: x ^ x = 0, x ^ 0 = x.
2. It’s commutative and associative, so order doesn’t matter: a ^ b ^ a = b.
3. XOR together everything that should pair up; whatever doesn’t pair is left over.

Python

single / missing / differ_in.py

from functools import reduce
from operator import xor


def single(nums: list[int]) -> int:
    """Every value appears twice except one. x ^ x = 0 and x ^ 0 = x, so pairs cancel."""
    return reduce(xor, nums, 0)  # 1. order doesn't matter: XOR is commutative and associative


def missing(nums: list[int]) -> int:
    """nums holds 0..n with one value missing. XOR all indices and values; the leftover is it."""
    acc = len(nums)  # 2. start with n, the one index the loop below never produces
    for i, x in enumerate(nums):
        acc ^= i ^ x  # 3. every present value cancels its matching index
    return acc


def differ_in(a: int, b: int) -> int:
    return (a ^ b).bit_count()  # 4. Hamming distance: count the bits that differ


if __name__ == "__main__":
    assert single([4, 1, 2, 1, 2]) == 4
    assert single([7]) == 7
    assert missing([3, 0, 1]) == 2
    assert missing([0]) == 1
    assert differ_in(1, 4) == 2  # 001 vs 100
    print("ok")

TypeScript

single / missing / differ_in.ts

import assert from "node:assert/strict";

/** Every value appears twice except one. x ^ x = 0 and x ^ 0 = x, so pairs cancel. */
export const single = (nums: number[]): number => nums.reduce((acc, x) => acc ^ x, 0); // 1. any order

/** nums holds 0..n with one value missing. XOR all indices and values; the leftover is it. */
export function missing(nums: number[]): number {
  let acc = nums.length; // 2. start with n, the one index the loop never produces
  nums.forEach((x, i) => { acc ^= i ^ x; }); // 3. each present value cancels its index
  return acc;
}

export function differIn(a: number, b: number): number {
  let x = (a ^ b) >>> 0, count = 0; // 4. Hamming distance: count differing bits
  for (; x; x = (x & (x - 1)) >>> 0) count++;
  return count;
}

assert.equal(single([4, 1, 2, 1, 2]), 4);
assert.equal(single([7]), 7);
assert.equal(missing([3, 0, 1]), 2);
assert.equal(missing([0]), 1);
assert.equal(differIn(1, 4), 2); // 001 vs 100
console.log("ok");

C#

single / missing / differ_in.cs

using System.Numerics;

// Every value appears twice except one. x ^ x = 0 and x ^ 0 = x, so pairs cancel.
static int Single(int[] nums) => nums.Aggregate(0, (acc, x) => acc ^ x); // 1. any order works

// nums holds 0..n with one value missing. XOR all indices and values; the leftover is it.
static int Missing(int[] nums)
{
    int acc = nums.Length;                       // 2. start with n, the index the loop never produces
    for (int i = 0; i < nums.Length; i++)
        acc ^= i ^ nums[i];                      // 3. each present value cancels its index
    return acc;
}

static int DifferIn(int a, int b) => BitOperations.PopCount((uint)(a ^ b)); // 4. Hamming distance

if (Single([4, 1, 2, 1, 2]) != 4 || Single([7]) != 7) throw new Exception("single");
if (Missing([3, 0, 1]) != 2 || Missing([0]) != 1) throw new Exception("missing");
if (DifferIn(1, 4) != 2) throw new Exception("hamming");
Console.WriteLine("ok");

Width and sign in each language

This table is where most bit bugs live.

	Python	TypeScript / JS	C#
integer width	unbounded (no overflow)	number is a 64-bit float; bitwise ops convert to 32-bit signed	int 32-bit, long 64-bit, uint/ulong unsigned
1 << 31	2147483648	−2147483648	−2147483648 (int); use 1L << 31 or 1u << 31
~5	−6	−6	−6
logical (unsigned) right shift	n/a; mask first: (x & 0xFFFFFFFF) >> k	x >>> k	x >>> k (C# 11+), or shift a uint
arithmetic right shift	>> (floors, even for negatives)	>>	>> on signed types
popcount	x.bit_count() (3.10+), bin(x).count('1')	none; loop or SWAR trick	BitOperations.PopCount(uint), int.PopCount (.NET 7+)
bit length / leading zeros	x.bit_length()	Math.clz32(x)	BitOperations.LeadingZeroCount, TrailingZeroCount
binary literal / print	0b1010, bin(x), f"{x:08b}"	0b1010, x.toString(2)	0b1010, Convert.ToString(x, 2)
64-bit masks	just work	BigInt (1n << 40n)	long / ulong

Shift counts are taken modulo the width

In JS and C#, the shift count is masked: 1 << 32 is 1 (because 32 mod 32 = 0), not 0. In C#, 1L << 64 is also 1. Python has no such limit: 1 << 100 is a 101-bit integer. Guard shift amounts if they come from input.

What it costs

Operation	Cost	Note
& | ^ ~ << >> on a machine word	O(1)	A single instruction.
popcount (built-in)	O(1)	Hardware POPCNT on modern CPUs.
Kernighan popcount loop	O(set bits)	≤ 32 or 64 iterations.
Python ops on huge ints	O(number of bits / 30)	Python’s big ints are arrays of 30-bit digits.
bitmask set of n ≤ 64 items	O(1) per union/intersect/test	versus O(n) for a list, O(1) avg for a hash set but much larger
enumerate all subsets	O(2^n) masks	Fine up to n ≈ 20 (about a million).

Variations you’ll meet

• Bitmask DP. dp[mask] over subsets of up to ~20 items (assignment problems, travelling salesman on small n). See advanced DP.
• Iterate submasks. s = mask; while s: …; s = (s − 1) & mask visits every subset of mask without testing each bit.
• Bitsets. Arrays of 64-bit words for large sets (C# BitArray, Python big ints, JS Uint32Array): 64× less memory than bool[], and set operations work a word at a time.
• Bit packing. Store several small fields in one integer with shifts and masks: (a << 8) | b, unpack with (x >> 8) & 0xFF. Common in compact keys, flags and wire formats.
• Gray code. i ^ (i >> 1): consecutive values differ in exactly one bit.
• Fenwick trees. Index jumps by i & −i give O(log n) prefix sums. See segment trees.

Pitfalls

• Operator precedence. In JS and C#, &, ^ and | bind looser than ==: x & 1 == 0 means x & (1 == 0) (always 0 in JS, a compile error in C#). Python happens to parse it as (x & 1) == 0, but x & 1 + 1 is x & 2 in all three. Always parenthesize.
• JS’s 32-bit cliff. Bitwise ops silently truncate values above 2^31 − 1. Timestamps in milliseconds, 64-bit ids and large masks break. Use BigInt or arithmetic.
• Python negative numbers never “end”. while x: x >>= 1 loops forever for negative x (-1 >> 1 is still -1). Mask to a width first.
• Overflow in C#. 1 << 31 is negative; 1 << 32 is 1. Use long/ulong and 1L << k.
• ~ isn’t “logical not”. ~1 is −2, which is truthy. Use ! / not for booleans.
• Signed right shift on negatives rounds toward −∞ (-7 >> 1 == -4). C#’s -7 / 2 truncates to -3, so shift and divide disagree; Python’s -7 // 2 == -4 matches the shift.

In the interview

• Ask the width and sign of the input: “Are these 32-bit signed? Can they be negative?” It changes >> vs >>> and loop termination.
• Explain each trick in words: “x & (x − 1) drops the lowest set bit, so the loop runs once per 1-bit.” Don’t present it as magic.
• Offer the readable alternative when it’s fair: “a hash set works too; the bitmask is O(1) and fits in a register because there are at most 20 items.”
• Follow-ups: “what if the values are 64-bit in JS?” (BigInt), “every element appears three times except one” (count bits mod 3), “two numbers appear once” (split by any set bit of their XOR).

Check yourself

Check yourself

pick one

In JavaScript, what is (1 << 31) > 0?

AtrueBfalse

Check yourself

pick one

What does x & (x − 1) == 0 (with x > 0) tell you?

Ax is evenBx is a power of twoCx has its lowest bit set

Check yourself

pick one

Values are 32-bit, every one appears exactly twice except one that appears once. Which uses O(1) space?

AA hash set of seen valuesBSorting, then scanning pairsCXOR of all values

Practice on your own

Classic textbook exercises, not gym questions:

• Reverse the bits of a 32-bit unsigned integer.
• Count bits for every number from 0 to n in O(n) (bits[i] = bits[i >> 1] + (i & 1)).
• Every element appears three times except one: find it with O(1) space.
• Generate all subsets of a small list with a mask loop, then the Gray-code ordering.

Go deeper

• Henry S. Warren Jr., Hacker’s Delight (2nd ed.), ch. 2 “Basics” and ch. 5 “Counting Bits”: the canonical reference for these identities.
• Sean Eron Anderson, “Bit Twiddling Hacks”, Stanford.
• MDN, Bitwise operators and 32-bit conversion; Microsoft Learn, BitOperations; Python docs, int.bit_count.
• cp-algorithms: Bit manipulation, including submask enumeration.

Related

Advanced DPBitmask states over subsets.

Math for interviewsParity, modular arithmetic, powers of two.

Segment treesFenwick trees use i & -i.

Memory efficiencyBitsets and packing to save space.