Bit Manipulation Basics

Bit manipulation means working directly with the individual binary digits (bits) that make up an integer, using operators like AND, OR, XOR, NOT, and the shift operators instead of ordinary arithmetic. It matters because bitwise operations map almost directly onto single CPU instructions, so they’re extremely fast and extremely memory-efficient, and because many classic problems — tracking a small set of flags, toggling state, finding a unique element among duplicates, checking parity — have elegant constant-space solutions once you think in bits. In coding interviews, bit tricks are a favorite because they test whether you understand how numbers are actually represented, not just whether you know a library function.

Overview: How Bit Manipulation Works

Every integer a computer stores is ultimately a sequence of bits, each either 0 or 1, weighted by powers of two. The number 13, for example, is 1101 in binary: 1·8 + 1·4 + 0·2 + 1·1 = 13. Python lets you inspect this directly with bin(13), which returns the string '0b1101', or convert a binary string back to an integer with int('1101', 2).

Python provides six bitwise operators, all of which act on the binary representation of integers:

Operator Name Effect
& AND 1 only where both operands have a 1 in that position
| OR 1 where either operand has a 1 in that position
^ XOR 1 where exactly one operand has a 1 (the bits differ)
~ NOT flips every bit; in Python, ~n equals -n - 1
<< Left shift shifts bits left, filling with 0s (multiplies by 2 per shift)
>> Right shift shifts bits right, sign-extending (floor-divides by 2 per shift)

A crucial Python-specific detail: unlike C, Java, or Go, Python integers are arbitrary precision — there is no fixed 32-bit or 64-bit container a number lives in. Conceptually, Python treats every integer as if it had infinitely many bits, with positive numbers sign-extended by 0s to the left and negative numbers sign-extended by 1s to the left (two’s complement). That’s why ~5 gives -6 instead of some large positive "flipped" value: there’s no fixed width to flip within. If you need fixed-width behavior (say, simulating an 8-bit register), you must mask the result yourself with & ((1 << width) - 1).

Bit tricks earn their keep whenever a problem has a natural "yes/no per position" structure: representing a small set of flags as one integer (a bitmask, useful for visited-state in subset-DP problems), toggling state, or exploiting the algebra of XOR — it’s its own inverse, so x ^ x == 0 and x ^ 0 == x — to cancel out duplicate values without any extra memory.

Time and Space Complexity

A single bitwise operation (&, |, ^, ~, <<, >>) on two ordinary, fixed-size numbers is O(1) time and O(1) space, because the CPU performs it on a machine word in a single instruction. Strictly speaking, since Python ints are arbitrary precision, an operation on a number with b bits costs O(b) in the worst case — but for the integers you’ll meet in DSA problems (well under 64 bits) this is indistinguishable from O(1), so it’s conventional to call single bitwise operations O(1).

Algorithms that scan across all the bits of a number scale with the number of bits, not the value of the number:

Operation Time Space Why
Single bitwise op O(1) O(1) one machine-word instruction
Count set bits, naive loop over all bits O(b) O(1) checks every one of the b bit positions once
Count set bits, Brian Kernighan’s trick O(s) O(1) each iteration clears exactly one set bit, so it loops only s times (s = number of 1-bits, s <= b)
Check power of two (n & (n - 1)) O(1) O(1) one AND and one comparison
XOR sweep to find a lone unmatched element O(n) O(1) one pass over the n elements, a single accumulator variable

Here n is the size of the input collection, while b and s refer to the bit width and set-bit count of one individual number — keep those two notions of "n" separate, since conflating them is a common source of confusion when reading about bit tricks.

Examples

Example 1: The basic bitwise operators

This example prints each operator’s result on a = 12 (1100) and b = 10 (1010) alongside its binary form, so you can see exactly which bit positions changed.

def demonstrate_bitwise_operators(a: int, b: int) -> None:
    print(f"a = {a} ({bin(a)})")
    print(f"b = {b} ({bin(b)})")
    print(f"a & b = {a & b} ({bin(a & b)})")
    print(f"a | b = {a | b} ({bin(a | b)})")
    print(f"a ^ b = {a ^ b} ({bin(a ^ b)})")
    print(f"~a = {~a}")
    print(f"a << 2 = {a << 2} ({bin(a << 2)})")
    print(f"a >> 1 = {a >> 1} ({bin(a >> 1)})")

demonstrate_bitwise_operators(12, 10)

Output:

a = 12 (0b1100)
b = 10 (0b1010)
a & b = 8 (0b1000)
a | b = 14 (0b1110)
a ^ b = 6 (0b110)
~a = -13
a << 2 = 48 (0b110000)
a >> 1 = 6 (0b110)

AND keeps a 1 only where both 1100 and 1010 have a 1, which is just position 3 (value 8). OR keeps a 1 wherever either has a 1, giving 1110 = 14. XOR keeps a 1 exactly where they differ, giving 0110 = 6. ~a flips every bit of a‘s (conceptually infinite) two’s-complement form, and for any integer n that always equals -n - 1, so ~12 is -13. Shifting a left by 2 appends two 0 bits (multiplying by 4): 1100 becomes 110000 = 48. Shifting a right by 1 drops the last bit (dividing by 2, rounding down): 1100 becomes 110 = 6.

Example 2: Checking if a number is a power of two

A power of two has exactly one set bit (100...0). Subtracting 1 from it flips that single bit to 0 and every bit below it to 1 (011...1), so ANDing n with n - 1 can only be 0 if n had exactly one set bit to begin with.

def is_power_of_two(n: int) -> bool:
    if n <= 0:
        return False
    return (n & (n - 1)) == 0

for value in [1, 2, 3, 4, 16, 18, 0, -8]:
    print(f"{value}: {is_power_of_two(value)}")

Output:

1: True
2: True
3: False
4: True
16: True
18: False
0: False
-8: False

Trace 18: in binary it’s 10010, and 17 is 10001. ANDing them gives 10000 = 16, which is not 0, so the function correctly reports False. Non-positive inputs are rejected up front, since the "single set bit" property is only meaningful for positive numbers.

Example 3: Finding the element that doesn’t have a pair (XOR sweep)

Because x ^ x == 0 and XOR is commutative and associative, XORing every number in a list together cancels out every value that appears an even number of times, leaving only the one that appears an odd number of times.

def find_single_number(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result

numbers = [4, 1, 2, 1, 2]
print(find_single_number(numbers))

Output:

4

Walking through it: result starts at 0. 0 ^ 4 = 4, then 4 ^ 1 = 5, then 5 ^ 2 = 7, then 7 ^ 1 = 6 (the second 1 cancels the first), then 6 ^ 2 = 4 (the second 2 cancels the first). What’s left, 4, is the element with no partner — found in one O(n) pass using O(1) extra space, versus O(n) space for a hash-set approach.

How It Works Step by Step: Brian Kernighan’s Bit-Counting Trick

The expression n & (n - 1) doesn’t just detect powers of two — more generally, it always clears the lowest set bit of n, whatever else n contains, because subtracting 1 turns that lowest 1 into a 0 and every 0 below it into a 1, and ANDing with the original number keeps all the higher bits unchanged while zeroing that one bit out. Looping this until n becomes 0 counts the set bits in exactly as many steps as there are set bits — not as many steps as there are bit positions.

def count_set_bits(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

value = 13
print(f"Number of set bits in {value} ({bin(value)}): {count_set_bits(value)}")

Output:

Number of set bits in 13 (0b1101): 3

Tracing n = 13 (1101) step by step:

Step n before n - 1 n & (n - 1) count after
1 1101 (13) 1100 (12) 1100 (12) 1
2 1100 (12) 1011 (11) 1000 (8) 2
3 1000 (8) 0111 (7) 0000 (0) 3

After step 3, n is 0, so the while n: loop ends and count_set_bits returns 3 — matching the three 1s in 1101.

Common Mistakes

Mistake 1: Expecting ~ to flip a fixed number of bits

Coming from a language with fixed-width integers, it’s tempting to assume ~n gives you the "other side" of an 8-bit or 32-bit number. In Python it doesn’t, because Python ints have no fixed width.

def flip_bits_8bit(n: int) -> int:
    return ~n

print(flip_bits_8bit(5))

Output:

-6

The intent was to flip 00000101 into 11111010 (250 as an unsigned 8-bit value), but ~5 just computes -5 - 1 = -6 under Python’s arbitrary-precision two’s complement — there is no 8-bit boundary to wrap around. The fix is to mask the result down to the width you actually want:

def flip_bits_8bit(n: int, bit_width: int = 8) -> int:
    mask = (1 << bit_width) - 1
    return ~n & mask

print(flip_bits_8bit(5))

Output:

250

Here mask is 11111111 (255). ANDing ~5‘s infinite ...11111010 pattern with that mask keeps only the low 8 bits, giving the intended 11111010 = 250.

Mistake 2: Confusing ^ (XOR) with exponentiation

In math notation, and in some other languages, ^ means "to the power of". In Python it’s the XOR operator, and mixing the two up produces a plausible-looking but wrong number instead of an error.

def combine_values(a: int, b: int) -> int:
    return a ^ b

result = combine_values(2, 10)
print(result)

Output:

8

The author likely wanted 2 to the 10th power (1024), but 2 ^ 10 XORs 0010 and 1010 bit by bit, giving 1000 = 8. Python’s exponentiation operator is **, not ^:

def combine_values(a: int, b: int) -> int:
    return a ** b

result = combine_values(2, 10)
print(result)

Output:

1024

Best Practices

  • Use plain a, b = b, a for swapping in real Python code — the XOR swap is a teaching example, and it breaks if a and b are the same variable (XORing a value with itself zeroes it).
  • Reach for a bitmask (one integer standing in for a fixed-size boolean array) when you have a small, fixed number of flags to track, such as visited-state in subset-based dynamic programming — it’s O(1) space and O(1) per lookup, versus O(k) for a list of booleans.
  • Use n & (n - 1) to clear the lowest set bit — it’s the building block for popcount and power-of-two checks, and for iterating over just the set bits of a number.
  • Use XOR’s self-canceling property for "everything appears twice except one" problems, but recognize its limits — it does not generalize to "appears three times except one" without extra bit-counting work (see Practice Exercise 2).
  • Never assume ~ or a left shift wraps around at some fixed width like it would in C or Java — Python ints are arbitrary precision, so mask explicitly with & ((1 << width) - 1) when you need fixed-width semantics.
  • Use bin(n) and int(s, 2) liberally while developing bit-manipulation code — seeing the binary representation catches mistakes fast.
  • Don’t reach for bit tricks purely because they’re clever — if a hash set or list comprehension is clearer and performance isn’t critical, prefer readability. Bit manipulation earns its place when it measurably saves space or is the expected interview approach.

Practice Exercises

  • Power of two, the counting way. Write is_power_of_two_by_count(n) that returns True only when n is positive and has exactly one set bit, by reusing count_set_bits from this lesson instead of the n & (n - 1) shortcut. Check that it agrees with is_power_of_two for every value from 1 to 20.
  • Single Number II. Given an integer array where every element appears exactly three times except for one that appears exactly once, find that element. The XOR sweep from Example 3 will not work here, since XOR only cancels pairs. Hint: for each bit position, count how many numbers in the array have that bit set, and look at that count modulo 3. Test on [2, 2, 3, 2] — the answer should be 3.
  • XOR swap. Implement a swap of two integer variables using only XOR and no temporary variable (a ^= b; b ^= a; a ^= b). Start with a = 5, b = 9, print both before and after, and confirm you get a = 9, b = 5. Then explain in a comment why this trick would fail if you tried to "swap a variable with itself".

Summary

  • Bitwise operators (&, |, ^, ~, <<, >>) act directly on the binary representation of integers, and each runs in O(1) time on typical interview-sized numbers.
  • Python integers are arbitrary precision — there’s no fixed width to wrap around, so ~n equals -n - 1, and fixed-width behavior must be simulated with an explicit mask.
  • n & (n - 1) clears the lowest set bit — the basis for O(1) power-of-two checks and O(s) popcount via Brian Kernighan’s algorithm, where s is the number of set bits.
  • XOR is its own inverse (x ^ x == 0), giving an O(n) time, O(1) space way to find the one array element without a matching pair.
  • Watch for two Python-specific traps: expecting ~ to behave like a fixed-width flip, and confusing ^ (XOR) with exponentiation, which is ** in Python.
  • Use bitmasks for small, fixed sets of flags; prefer plain a, b = b, a over an XOR swap in real code; and keep bit tricks for where they measurably help.