Bitwise Operators Explained: AND, OR, XOR, NOT and Shifts

Bitwise operators look like line noise, &, |, ^, ~, <<, >>, and many programmers avoid them until an interview question demands them. They are simpler than arithmetic: each one works on the binary digits of a number lane by lane, with no carries between lanes. Once you can picture an integer as a row of switches, every bit trick is a combination of a few one-line rules, and the only real surprises are negative numbers and Python's integers that never overflow.

The problem it solves

Some data is naturally a set of yes/no flags: file permissions, feature toggles, which of 20 items are chosen, which cells of a board are occupied. Storing each flag as a separate boolean costs space and time; packing them into one integer lets a single instruction test, set or combine all of them. Bitwise operators are also how hardware adds, how hash functions mix bits and how many interview tricks find the odd element out in O(1) space.

The intuition

Write both numbers in binary, line up the lanes, and decide each lane on its own:

• a & b (AND): 1 only where both lanes are 1. Used to test or clear bits with a mask.
• a | b (OR): 1 where either lane is 1. Used to set bits.
• a ^ b (XOR): 1 where the lanes differ. Used to toggle bits; x ^ x == 0, which powers the classic XOR tricks.
• ~a (NOT): flips every lane.
• a << k: slides every lane k places up, multiplying by 2^k. a >> k slides down, dividing by 2^k and rounding down.

Negative numbers use two's complement: -x is "flip every bit of x, then add one", so ~x is always -x - 1. Fixed-width languages cut this off at 32 or 64 bits. Python integers have unlimited width, so a negative number behaves as if it had infinitely many leading 1s. To see the bits a 32-bit machine would hold, mask with & 0xFFFFFFFF. Right shift on a negative number rounds toward minus infinity, so -13 >> 1 is -7, not -6.

Unix permissions are the classic real-world mask: nine bits, read, write and execute for owner, group and others. chmod 644 is the octal number 0o644, and "may the group write?" is one AND.

Watch it run

The animation lines up 12 and 10 as eight-lane rows. To the CPU, 12 is eight switches, with only the 8 lane and the 4 lane on. 10 lights the 8 lane and the 2 lane; lanes never talk to each other, so there are no carries anywhere. AND keeps a lane only if both sides have it: both have the 8, so the result keeps it. In the 4 lane, 12 has it and 10 does not, and one missing side is enough for a 0. In the 2 lane only 10 has it, so that one goes dark too; every lane is decided the same way, at once. 12 & 10 = 8: one lane survived, and the whole row was settled in a single instruction. OR asks "either?", so the 8, 4 and 2 lanes all light up: 14. XOR asks "exactly one?", so the shared 8 lane goes dark and only the differences remain: 6. A left shift slides every lane one place up, so 12 doubles to 24, with no multiply involved. And each right shift halves: 12 >> 2 is 3, halved twice. Eight lanes, no carries, no branches.

The code

The lesson's operations, NOT and shifts on negative numbers, and a permission mask decoded class by class:

a, b = 12, 10
print(f"{a:08b} {b:08b}")                           # 00001100 00001010
print(a & b, a | b, a ^ b, a << 1, a >> 2)          # 8 14 6 24 3

# NOT flips every bit, including the sign: in two's complement ~x is -x - 1.
print(~12, f"{~12 & 0xFF:08b}")                     # -13 11110011  (the low 8 bits)
print(-12 >> 1, -13 >> 1)                           # -6 -7  right shift rounds DOWN

# chmod 644: nine permission bits, three per class (owner, group, others).
mode = 0o644
READ, WRITE, EXEC = 4, 2, 1
for who, shift in (("owner", 6), ("group", 3), ("others", 0)):
    bits = (mode >> shift) & 0o7                    # slide the class down, mask 3 bits
    print(who, bool(bits & READ), bool(bits & WRITE), bool(bits & EXEC))
# owner True True False
# group True False False
# others True False False
print(oct(mode | 0o020), oct(mode & ~0o004))        # 0o664 0o640  grant g+w, revoke o+r

def add(x, y, bits=32):
    """Addition from gates: XOR adds without carries, AND << 1 is the carries."""
    mask = (1 << bits) - 1
    x, y = x & mask, y & mask
    while y:
        x, y = (x ^ y) & mask, ((x & y) << 1) & mask
    return x - (1 << bits) if x >> (bits - 1) else x   # read the top bit as the sign

print(add(12, 10), add(-7, 3), add(2**31 - 1, 1))   # 22 -4 -2147483648  (32-bit overflow)

The adder is the "sum of two integers without +" question. XOR is the sum of each lane ignoring carries; AND finds the lanes that produce a carry, and the shift moves each carry into the next lane. The loop repeats until no carries are left. In Python the mask is essential: without it, adding a negative number would chase carries through Python's endless leading 1s forever.

Checked on 5,000 seeded random pairs: each operator against a brute force that applies the one-bit truth table lane by lane, the identities for NOT and shifts on negative numbers, and the gate adder against Python's + wrapped to 32 bits:

import random

def lane_by_lane(x, y, rule, bits=16):
    """Brute force: apply a one-bit truth table to each lane separately."""
    out = 0
    for i in range(bits):
        out |= rule((x >> i) & 1, (y >> i) & 1) << i
    return out

def wrap(v, bits=32):                               # what a 32-bit register would hold
    v &= (1 << bits) - 1
    return v - (1 << bits) if v >> (bits - 1) else v

rng = random.Random(30)
ok = True
for _ in range(5_000):
    x, y = rng.randrange(1 << 16), rng.randrange(1 << 16)
    ok &= (x & y) == lane_by_lane(x, y, lambda p, q: p and q)
    ok &= (x | y) == lane_by_lane(x, y, lambda p, q: p or q)
    ok &= (x ^ y) == lane_by_lane(x, y, lambda p, q: p != q)
    ok &= x + y == (x ^ y) + 2 * (x & y)            # sum = no-carry part + carries
    s, k = rng.randint(-10**6, 10**6), rng.randint(0, 20)
    ok &= ~s == -s - 1 and s >> k == s // 2**k and s << k == s * 2**k
    p, q = rng.randint(-2**31, 2**31 - 1), rng.randint(-2**31, 2**31 - 1)
    ok &= add(p, q) == wrap(p + q)                  # the gate adder vs Python's +
print(ok)                                           # True

The complexity

• Fixed-width integers: every operator is one CPU instruction, O(1).
• Python integers: O(number of machine words), which is O(1) for anything that fits in 64 bits and grows only for huge numbers.
• The gate adder: at most bits + 1 loop iterations, because a carry can travel at most the full width.

Where it goes wrong

• Operator precedence. Arithmetic binds tighter than shifts, so 1 << n - 1 means 1 << (n - 1), and in C x & 1 == 0 parses as x & (1 == 0). Parenthesise every mixed expression.
• Expecting overflow in Python. 1 << 40 is simply a big number, and ~x is negative, never a large unsigned value. Mask explicitly when you need a fixed width.
• Right-shifting negatives. >> rounds down; C-style division truncates toward zero. -7 >> 1 is -4, while truncating -7 / 2 gives -3.
• Confusing ^ with power. 2 ^ 3 is 1 in Python; exponentiation is 2 ** 3.

When it shows up in interviews

As warm-ups ("what is 13 & 6?", "is this a power of two?") and as the core of classic problems: XOR tricks for the single and missing number, masks to set, clear and toggle bits, counting set bits and bitmask DP over subsets. The patterns cheat sheet groups these bit tricks with the problems they crack.

How to say it in an interview

"Bitwise operators work on each binary digit independently, with no carries: AND keeps bits both sides have, OR keeps bits either has, XOR keeps the differences, NOT flips everything, and shifts multiply or divide by powers of two. Negative numbers are two's complement, so ~x is -x - 1. In Python integers are unbounded, so when a problem assumes 32 bits I mask with 0xFFFFFFFF and convert the top bit back to a sign. To add without +, XOR gives the sum without carries and AND shifted left gives the carries; I loop until the carry is zero."