Bit Manipulation Tricks Every Developer Should Know (With Examples)

Bit manipulation is the act of algorithmically manipulating bits or memory addresses. While high-level languages like Python and Java abstract this away, bit operations happen at the hardware level, making them blazing fast.

In coding interviews and systems programming, bit manipulation is a recurring theme. Whether you are optimizing memory, implementing a Fenwick Tree, or trying to solve a problem without using extra space, knowing your bitwise operators is a superpower.

Here is a complete guide to the most essential bit manipulation tricks every developer should know.

The Core Bitwise Operators (A Quick Refresher)

Before we get to the tricks, ensure you know the basic operators. Let's use a fixed 4-bit system just for visualization.

⚠️ The NOT (~) Operator Caveat: In a fixed 4-bit visualization, ~0110 becomes 1001. However, in real programming languages like Python, Java, or C++, integers use two's complement representation with many more bits. Therefore, ~6 actually evaluates to -7, not 9. The ~ operator flips all bits, including the sign bit.

Trick 1: Check if a Number is Even or Odd

The most basic bit manipulation trick. Instead of using the modulo operator (%), use the bitwise AND operator.

Why it works: The least significant bit (LSB) of an odd number is always 1. For an even number, it is 0. ANDing the number with 1 isolates this LSB.

def is_odd(n):
    return (n & 1) == 1

# 5 (0101) & 1 (0001) = 1 (Odd)
# 6 (0110) & 1 (0001) = 0 (Even)

Trick 2: Multiply or Divide by 2

Shifting bits to the left multiplies a number by 2. Shifting right divides by 2.

Caveat: Left shifting by one bit is equivalent to multiplying by 2 for non-negative integers that do not overflow the integer type. In languages like C/C++, shifting out of bounds causes undefined behavior. In Python, integers have arbitrary precision, so they just grow larger.

n = 4
print(n << 1)  # Output: 8 (Multiply by 2)
print(n >> 1)  # Output: 2 (Divide by 2)

Trick 3: Isolate the Rightmost Set Bit (x & -x)

If you read our Fenwick Tree guide, you know this one! It isolates the lowest 1 bit of a number.

Why it works: Two's complement means -x is essentially ~x + 1. ANDing x with -x zeroes out everything except the rightmost 1. This is highly useful for calculating trailing zeros in algorithms.

x = 12  (1100)
-x = 4  (0100)

1100 & 0100 = 0100 (4)

Trick 4: Remove the Rightmost Set Bit (x & (x - 1))

This is arguably the most famous bit manipulation trick. It turns the rightmost 1 bit into a 0.

Why it works: Subtracting 1 from a number flips all bits up to and including the rightmost 1. ANDing this with the original number clears that bit.

x   = 12 (1100)
x-1 = 11 (1011)

1100 & 1011 = 1000 (8)

The Killer Application: This is the core of Brian Kernighan’s Algorithm, used to count the number of set bits (1s) in a number in $O(\text{number of 1s})$ time.

def count_set_bits(n):
    count = 0
    while n:
        n = n & (n - 1) # Removes the rightmost 1 bit
        count += 1
    return count

print(count_set_bits(15)) # 15 is 1111 in binary. Output: 4

Built-in Popcounts

In production code, you rarely write Brian Kernighan's Algorithm yourself. Modern languages have built-in popcount (population count) functions: * Python 3.10+: n.bit_count() (e.g., 15.bit_count() returns 4) * C++: __builtin_popcount(n) * Java: Integer.bitCount(n)

However, interviewers still expect you to know how to implement it manually!

Trick 5: Check if a Number is a Power of 2

A power of 2 (like 2, 4, 8, 16) has exactly one 1 bit in its binary representation.

If we apply Trick 4 (x & (x - 1)), it will remove that single 1 bit, resulting in 0.

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

print(is_power_of_two(16)) # True (10000 & 01111 = 0)
print(is_power_of_two(14)) # False (1110 & 1101 = 1100)

Trick 6: Bit Masking (Set, Clear, Toggle, Check, Extract)

When working with hardware, flags, or writing low-level algorithms (like Chess engines), you often need to manipulate specific bits at index i (0-indexed from the right).

Let mask = 1 << i (shift the 1 to the desired position).

• Extract the $i$-th bit: (n >> i) & 1
• Check if the $i$-th bit is set: (n & mask) != 0
• Set the $i$-th bit (make it 1): n | mask
• Clear the $i$-th bit (make it 0): n & ~mask
• Toggle the $i$-th bit: n ^ mask

n = 5  # 0101

# Extract the 1st bit (index 1)
bit = (n >> 1) & 1  # Returns 0

# Set the 1st bit (index 1, which is currently 0)
n = n | (1 << 1)
print(n) # Output: 7 (0111)

Trick 7: Check if Two Numbers Have Opposite Signs

A very common interview trick. The sign bit is the leftmost bit (in fixed-width integers). If two numbers have different sign bits, XORing them will result in a negative number.

def opposite_signs(a, b):
    return (a ^ b) < 0

print(opposite_signs(5, -3)) # True
print(opposite_signs(-5, -3)) # False

Trick 8: Swap Two Numbers Without a Temporary Variable

A classic interview trivia question. You can swap two variables using XOR (^) without a temp variable.

Note: Although this is a classic interview trick, using a temporary variable is clearer in production code, and modern compilers optimize temporary variables effectively anyway.

a = 5
b = 3

a = a ^ b
b = a ^ b  # (a ^ b) ^ b = a
a = a ^ b  # (a ^ b) ^ a = b

print(a, b) # Output: 3 5

Complexity Analysis

Common Real-World Applications

"When do I actually use this?" Outside of LeetCode, bit manipulation is foundational to computer science: * Permission Systems: Unix file permissions (rwx = 7) use bitmasking. * Flags: Passing multiple boolean configurations to a function in a single integer. * Chess Engines: Representing board states efficiently using 64-bit integers (Bitboards). * Bloom Filters: Probabilistic data structures using bit arrays. * Networking & Cryptography: Calculating checksums, hashes, and XOR ciphers. * Compression: Huffman coding relies heavily on bit-level I/O.

Pattern Recognition: When to Use What

Instead of just memorizing tricks, learn to recognize the interview signals:

The Ultimate Bit Manipulation Cheat Sheet

Bookmark this table for quick reference:

Real Interview Questions & Practice Problems

Bit manipulation problems are notoriously tricky to visualize but become easy once you apply the right trick.

Frequently Asked Questions (FAQ)

Why use bit manipulation when I can just use + or %? In high-level languages, the compiler often optimizes arithmetic operations into bitwise operations anyway. However, bitwise operations are strictly necessary when dealing with raw memory, writing device drivers, implementing data structures like Tries or Fenwick Trees, or solving specific LeetCode puzzles that ban standard operators.

Is XOR (^) the same as Exponentiation? NO. This is a massive beginner mistake, especially in Python (where ^ is XOR and ** is exponentiation). 2 ^ 3 is 1 (XOR), not 8 (Exponent).

How does the Sum of Two Integers work without + or -? You use & to calculate the carry, and ^ to calculate the sum without carry. You loop until there is no carry left. (It's a great interview question to test your bit math!).