Bit Manipulation Basics: AND, OR, XOR, NOT, Shifts

Bit manipulation is doing arithmetic directly on the binary representation of an integer. It is fast (a single CPU instruction in most cases), compact (a 64-bit integer holds 64 yes/no flags), and shows up everywhere: low-level systems, embedded code, hashing, compression, and a noticeable slice of algorithm interviews. This post is the gentle introduction — the operators and what they do. The next post is the trick book.

Binary, briefly

A non-negative integer is a sum of powers of two. The bit at position i (from the right, starting at 0) contributes 2^i if it is 1.

decimal 13 → binary 1101
                    │││└── 1 × 2^0 = 1
                    ││└─── 0 × 2^1 = 0
                    │└──── 1 × 2^2 = 4
                    └───── 1 × 2^3 = 8
                                    ─────
                                    13

In Python, bin(13) returns '0b1101'. You can write literals as 0b1101.

print(bin(13))    # 0b1101
print(0b1101)     # 13

AND — &

a & b returns a number whose bit i is 1 only if both a and b have bit i set.

bit position : 3  2  1  0
8  4  2  1
a = 12     :  1  1  0  0
b = 10     :  1  0  1  0
─────────────────────────
a & b = 8  :  1  0  0  0

print(12 & 10)    # 8
print(bin(12 & 10))    # 0b1000

AND is the operation for masking — keeping only the bits you care about. x & 0xFF extracts the low 8 bits of x.

OR — |

a | b returns a number whose bit i is 1 if either a or b has bit i set.

bit position : 3  2  1  0
a = 12     :  1  1  0  0
b = 10     :  1  0  1  0
─────────────────────────
a | b = 14 :  1  1  1  0

print(12 | 10)    # 14

OR is the operation for setting bits — turning specific bits on without disturbing the others.

XOR — ^

a ^ b returns a number whose bit i is 1 if exactly one of a or b has bit i set.

bit position : 3  2  1  0
a = 12     :  1  1  0  0
b = 10     :  1  0  1  0
─────────────────────────
a ^ b = 6  :  0  1  1  0

print(12 ^ 10)    # 6

XOR has two delightful properties:

• x ^ x = 0 (a number XORed with itself is zero)
• x ^ 0 = x (a number XORed with zero is itself)

Together these make XOR the foundation of many bit tricks — most famously, finding the single non-duplicated element in a list. We use that in the next post.

NOT — ~

~x flips every bit. In Python — which uses arbitrary-precision integers with two’s complement semantics — ~x is equivalent to -x - 1.

print(~5)     # -6
print(~0)     # -1
print(~-1)    # 0

That looks strange. The reason is two’s complement: negative numbers are represented by inverting the bits of the positive value and adding one. Python pretends every integer has infinitely many leading sign bits.

For most algorithmic uses you don’t need to worry about the sign — you’ll mask ~x with & 0xFFFFFFFF (or similar) when you need a fixed-width result:

def invert_32(x):
    return ~x & 0xFFFFFFFF

print(bin(invert_32(0b1101)))    # 0b11111111111111111111111111110010

Left shift — <<

x << n shifts all bits of x to the left by n positions, filling in 0s on the right. It is the same as multiplying by 2^n.

bit position : 5  4  3  2  1  0
x = 3      :  0  0  0  0  1  1
x << 2 = 12:  0  0  1  1  0  0
◀──── shifted left by 2

print(3 << 2)     # 12
print(1 << 10)    # 1024  (a quick way to write 2**10)

1 << n is a clean way to produce a number with only bit n set — useful in masks.

Right shift — >>

x >> n shifts bits right by n. For non-negative x this is integer division by 2^n.

bit position : 3  2  1  0
x = 13     :  1  1  0  1
x >> 1 = 6 :  0  1  1  0
────▶ shifted right by 1
drops the 1

print(13 >> 1)    # 6
print(13 >> 2)    # 3

For negative numbers, Python’s >> is an arithmetic shift — it preserves the sign by filling in 1s on the left.

Common single-bit operations

Most bit manipulation work is about a specific bit at position i. Four operations cover almost every case.

Check bit i

Is bit i set?

def is_set(x, i):
    return (x >> i) & 1

print(is_set(0b1010, 1))    # 1
print(is_set(0b1010, 0))    # 0

Equivalently (x & (1 << i)) != 0.

Set bit i

Force bit i to 1.

def set_bit(x, i):
    return x | (1 << i)

print(bin(set_bit(0b1010, 0)))    # 0b1011

bit position : 3  2  1  0
x          :  1  0  1  0
1 << 0     :  0  0  0  1
─────────────────────────
result     :  1  0  1  1

Clear bit i

Force bit i to 0.

def clear_bit(x, i):
    return x & ~(1 << i)

print(bin(clear_bit(0b1010, 1)))    # 0b1000

~(1 << i) is a mask of all 1s except at position i. AND with this preserves every other bit and clears position i.

bit position : 3  2  1  0
x          :  1  0  1  0
~(1 << 1)  :  1  1  0  1
─────────────────────────
result     :  1  0  0  0

Toggle bit i

Flip bit i.

def toggle_bit(x, i):
    return x ^ (1 << i)

print(bin(toggle_bit(0b1010, 0)))    # 0b1011
print(bin(toggle_bit(0b1010, 1)))    # 0b1000

XOR with 1 flips; XOR with 0 leaves alone. Toggle is set+clear in a single operation.

A small worked example — packing flags

Bit manipulation lets you store many boolean flags in a single integer. Suppose you have permissions: READ = 1 << 0, WRITE = 1 << 1, EXEC = 1 << 2.

READ  = 1 << 0
WRITE = 1 << 1
EXEC  = 1 << 2

def grant(perms, flag):
    return perms | flag

def revoke(perms, flag):
    return perms & ~flag

def has(perms, flag):
    return perms & flag != 0

p = 0
p = grant(p, READ)
p = grant(p, WRITE)
print(bin(p))                # 0b11
print(has(p, READ))          # True
print(has(p, EXEC))          # False
p = revoke(p, READ)
print(has(p, READ))          # False

This is the same shape Unix uses for file permissions, and exactly the shape many algorithm problems take when they ask about “subsets” of n items.

Two’s complement, briefly

Python’s integers don’t have a fixed width — they grow to fit. But the bitwise operators still behave as if every integer had infinitely many leading bits matching its sign. This is two’s complement with infinite precision.

You usually feel this in two places:

• ~0 is -1 (not some giant positive number).
• bin(-5) returns '-0b101', not a two’s-complement bit string.

If you need a fixed-width view (e.g. for a 32-bit hash), mask explicitly:

def to_32(x):
    return x & 0xFFFFFFFF

print(hex(to_32(~5)))    # 0xfffffffa

For everyday algorithmic work, you can ignore the sign as long as your inputs are non-negative.

Operator precedence — a gotcha

The bitwise operators have lower precedence than comparison operators. This bites everyone at least once:

# WRONG — Python parses as x & (1 == 0), which is x & 0 == 0, always True
if x & 1 == 0:
    ...

# Right
if (x & 1) == 0:
    ...

When in doubt, parenthesise.

Practice problems

1. Is n even?

def is_even(n):
    return (n & 1) == 0

print(is_even(10))    # True
print(is_even(7))     # False

The lowest bit is 0 for even numbers, 1 for odd.

2. Multiply by 8

def mul8(n):
    return n << 3

print(mul8(5))    # 40

Left shift by 3 = multiply by 2³ = 8.

3. Swap nibbles of an 8-bit number

def swap_nibbles(x):
    return ((x & 0x0F) << 4) | ((x & 0xF0) >> 4)

print(bin(swap_nibbles(0b11010010)))    # 0b00101101

4. Print the binary representation of n (no bin())

def to_binary(n):
    if n == 0:
        return "0"
    bits = []
    while n:
        bits.append(str(n & 1))
        n >>= 1
    return "".join(reversed(bits))

print(to_binary(13))    # 1101

5. Check if bit i of n equals bit j of n

def bits_match(n, i, j):
    return ((n >> i) & 1) == ((n >> j) & 1)

print(bits_match(0b1010, 0, 2))    # True  (both 0)
print(bits_match(0b1010, 0, 1))    # False

6. Turn off the rightmost set bit

def turn_off_rightmost(n):
    return n & (n - 1)

print(bin(turn_off_rightmost(0b1100)))    # 0b1000

This is one of the most useful tricks in bit manipulation — we use it heavily in the next post.

Recap

You now know:

• Integers in binary are sums of powers of two
• &, |, ^, ~ operate bit by bit; << and >> shift positions
• 1 << i builds a single-bit mask at position i
• Set / clear / toggle / check are all variations of mask + bitwise op
• Python uses infinite-precision two’s complement; mask with & 0xFFFFFFFF for fixed-width

Next steps

You have the operators. The next post is where they earn their keep — clever tricks (n & (n-1), n & -n, XOR cancellation), Brian Kernighan’s bit counter, and six classic interview problems with full solutions.

→ Next: Bit Manipulation Tricks and Practice Problems

Questions or feedback? Email codeloomdevv@gmail.com.