Bit Manipulation: Bitwise Operations and Tricks

Key Insights

Bit manipulation provides constant-time operations for tasks that would otherwise require loops or complex arithmetic, making it essential for performance-critical code and embedded systems.
Mastering a handful of core techniques—setting, clearing, toggling, and checking bits—unlocks dozens of practical applications from permission systems to data compression.
The classic bit tricks (power-of-two checks, XOR swap, population count) appear frequently in interviews and production code alike, making them worth committing to memory.

Introduction to Binary and Bits

Every value in your computer ultimately reduces to bits—ones and zeros stored in memory. While high-level programming abstracts this away, understanding bit manipulation gives you direct control over data at its most fundamental level.

Binary representation is straightforward: each position represents a power of two, starting from the right. The decimal number 13 becomes 1101 in binary: 8 + 4 + 0 + 1 = 13.

Why should you care? Three reasons: performance (bit operations execute in a single CPU cycle), memory efficiency (pack multiple values into single integers), and necessity (network protocols, file formats, and hardware interfaces demand bit-level precision).

# Converting between decimal and binary
decimal_value = 42

# Decimal to binary string
binary_str = bin(decimal_value)  # '0b101010'
binary_clean = format(decimal_value, 'b')  # '101010'

# Binary to decimal
back_to_decimal = int('101010', 2)  # 42

# Visualize bit positions
def show_bits(n, width=8):
    """Display a number with its bit positions labeled."""
    binary = format(n, f'0{width}b')
    positions = ''.join(str(i % 10) for i in range(width-1, -1, -1))
    return f"Value: {n}\nBits:  {binary}\nPos:   {positions}"

print(show_bits(42))
# Value: 42
# Bits:  00101010
# Pos:   76543210

Core Bitwise Operators

Six operators form the foundation of all bit manipulation. Master these, and everything else follows.

AND (&): Returns 1 only when both bits are 1. Use it to extract or mask specific bits.

OR (|): Returns 1 when either bit is 1. Use it to set bits without affecting others.

XOR (^): Returns 1 when bits differ. Use it for toggling and finding differences.

NOT (~): Inverts all bits. In two’s complement, ~n equals -(n+1).

Left Shift (<<): Shifts bits left, filling with zeros. Equivalent to multiplying by powers of two.

Right Shift (>>): Shifts bits right. Equivalent to integer division by powers of two.

a = 0b1100  # 12
b = 0b1010  # 10

# AND: bits set in BOTH
print(f"AND: {a & b:04b} = {a & b}")   # 1000 = 8

# OR: bits set in EITHER
print(f"OR:  {a | b:04b} = {a | b}")   # 1110 = 14

# XOR: bits that DIFFER
print(f"XOR: {a ^ b:04b} = {a ^ b}")   # 0110 = 6

# NOT: inverts all bits (shows as negative in two's complement)
print(f"NOT a: {~a}")                   # -13

# Left shift: multiply by 2^n
print(f"12 << 2 = {12 << 2}")          # 48 (12 * 4)

# Right shift: divide by 2^n
print(f"12 >> 2 = {12 >> 2}")          # 3 (12 / 4)

Common Bit Manipulation Techniques

Four operations handle 90% of practical bit manipulation: set, clear, toggle, and check.

def set_bit(value, position):
    """Set bit at position to 1."""
    return value | (1 << position)

def clear_bit(value, position):
    """Set bit at position to 0."""
    return value & ~(1 << position)

def toggle_bit(value, position):
    """Flip bit at position."""
    return value ^ (1 << position)

def check_bit(value, position):
    """Return True if bit at position is 1."""
    return bool(value & (1 << position))

# Demonstration
flags = 0b0000

flags = set_bit(flags, 0)    # 0001
flags = set_bit(flags, 2)    # 0101
print(f"After setting: {flags:04b}")

print(f"Bit 2 set? {check_bit(flags, 2)}")  # True
print(f"Bit 1 set? {check_bit(flags, 1)}")  # False

flags = toggle_bit(flags, 2)  # 0001
print(f"After toggle: {flags:04b}")

flags = clear_bit(flags, 0)   # 0000
print(f"After clear: {flags:04b}")

For extracting and inserting bit fields (multiple consecutive bits), you need masks:

def extract_bits(value, start, length):
    """Extract 'length' bits starting at 'start' position."""
    mask = (1 << length) - 1  # Creates mask of 'length' 1s
    return (value >> start) & mask

def insert_bits(value, bits, start, length):
    """Insert 'bits' into 'value' at 'start' position."""
    mask = (1 << length) - 1
    cleared = value & ~(mask << start)  # Clear target bits
    return cleared | ((bits & mask) << start)  # Insert new bits

# Pack RGB values into a single integer
red, green, blue = 255, 128, 64

color = 0
color = insert_bits(color, red, 16, 8)    # Red in bits 16-23
color = insert_bits(color, green, 8, 8)   # Green in bits 8-15
color = insert_bits(color, blue, 0, 8)    # Blue in bits 0-7

print(f"Packed color: {color:#08x}")  # 0xff8040

# Extract back
print(f"Red: {extract_bits(color, 16, 8)}")    # 255
print(f"Green: {extract_bits(color, 8, 8)}")   # 128
print(f"Blue: {extract_bits(color, 0, 8)}")    # 64

Classic Bit Tricks

These tricks appear constantly in interviews and optimized code. Understanding why they work matters more than memorizing them.

Power of Two Check: A power of two has exactly one bit set. Subtracting 1 flips all bits below it. AND-ing these together yields zero only for powers of two.

def is_power_of_two(n):
    """Check if n is a power of two."""
    return n > 0 and (n & (n - 1)) == 0

# Why it works:
# 8 = 1000, 7 = 0111, 8 & 7 = 0000 ✓
# 6 = 0110, 5 = 0101, 6 & 5 = 0100 ✗

XOR Swap: XOR has a self-inverse property: a ^ b ^ b = a. This enables swapping without temporary storage.

def xor_swap(a, b):
    """Swap two values using XOR (educational, not practical)."""
    a = a ^ b
    b = a ^ b  # b = (a ^ b) ^ b = a
    a = a ^ b  # a = (a ^ b) ^ a = b
    return a, b

# Note: In practice, use tuple unpacking: a, b = b, a

Population Count (Counting Set Bits): Count how many bits are 1. The trick n & (n-1) clears the lowest set bit.

def count_set_bits(n):
    """Count the number of 1 bits (Brian Kernighan's algorithm)."""
    count = 0
    while n:
        n &= (n - 1)  # Clear lowest set bit
        count += 1
    return count

print(count_set_bits(0b10110101))  # 5

Find Single Non-Duplicate: XOR all elements. Duplicates cancel out (a ^ a = 0), leaving the unique value.

def find_single(nums):
    """Find the element that appears once (others appear twice)."""
    result = 0
    for num in nums:
        result ^= num
    return result

print(find_single([2, 3, 5, 3, 2]))  # 5

Practical Applications

Bitmasks excel at permission systems. Each bit represents a capability, enabling efficient storage and checking of multiple permissions simultaneously.

class Permissions:
    NONE = 0
    READ = 1 << 0      # 0001
    WRITE = 1 << 1     # 0010
    DELETE = 1 << 2    # 0100
    ADMIN = 1 << 3     # 1000
    
    ALL = READ | WRITE | DELETE | ADMIN  # 1111

class User:
    def __init__(self, name, permissions=Permissions.NONE):
        self.name = name
        self.permissions = permissions
    
    def grant(self, permission):
        self.permissions |= permission
    
    def revoke(self, permission):
        self.permissions &= ~permission
    
    def has_permission(self, permission):
        return (self.permissions & permission) == permission
    
    def has_any_permission(self, permissions):
        return bool(self.permissions & permissions)

# Usage
admin = User("alice", Permissions.ALL)
reader = User("bob", Permissions.READ)

reader.grant(Permissions.WRITE)
print(f"Bob can write: {reader.has_permission(Permissions.WRITE)}")  # True

reader.revoke(Permissions.WRITE)
print(f"Bob can write: {reader.has_permission(Permissions.WRITE)}")  # False

# Check multiple permissions at once
can_modify = Permissions.WRITE | Permissions.DELETE
print(f"Alice can modify: {admin.has_permission(can_modify)}")  # True

Performance Considerations

Bit manipulation is fast, but don’t optimize prematurely. Modern compilers often generate identical assembly for equivalent operations.

import timeit

def multiply_shift(n):
    return n << 3  # n * 8

def multiply_arithmetic(n):
    return n * 8

# Benchmark
shift_time = timeit.timeit(lambda: multiply_shift(42), number=10_000_000)
arith_time = timeit.timeit(lambda: multiply_arithmetic(42), number=10_000_000)

print(f"Shift: {shift_time:.3f}s")
print(f"Arithmetic: {arith_time:.3f}s")
# Results are typically identical—compilers optimize this automatically

Use bit manipulation when it provides genuine benefits: compact storage, protocol compliance, or hardware interaction. For simple arithmetic, write readable code and trust your compiler.

Hardware provides specialized instructions for common operations. Python’s int.bit_count() (3.10+) uses CPU-level POPCNT when available:

# Use built-in when available
n = 0b10110101
print(n.bit_count())  # 5 (Python 3.10+)
print(bin(n).count('1'))  # 5 (older Python, slower)

Conclusion

Bit manipulation distills to a few core operations: AND for masking, OR for setting, XOR for toggling, and shifts for positioning. The classic tricks—power-of-two checks, population counts, XOR-based algorithms—build directly on these primitives.

Start with the permission system pattern. It’s immediately useful and reinforces the fundamental operations. From there, explore competitive programming problems on LeetCode or HackerRank—their bit manipulation sections provide excellent practice.

The real mastery comes from recognizing when bits solve a problem elegantly. Not every problem needs bit tricks, but when they fit, nothing else comes close.