Algorithms
  • Understand bits as the fundamental building blocks of digital information
  • Learn how binary representation works and why computers use it
  • Master the six basic bit operations (AND, OR, XOR, NOT, shifts)
  • Recognize when bit manipulation provides advantages over traditional approaches

Introduction to Bit Manipulation

Here's something that might surprise you: underneath all the high-level abstractions we work with—objects, functions, strings, arrays—your computer is just flipping billions of tiny switches on and off. Those switches are bits, and learning to manipulate them directly gives you superpowers that most programmers never discover.

Bit manipulation feels like cheating. You can solve problems that would normally require loops and conditionals with a single elegant expression. You can store information in ways that seem impossible. You can make your code run faster than anyone thought possible. But first, you need to think in binary.

What Are Bits, Really?

At the hardware level, a bit is a transistor that's either conducting electricity or not. On or off. 1 or 0. That's it.

Everything your computer does—rendering this text, playing videos, running machine learning models—comes down to manipulating patterns of ones and zeros. When you type the number 42, your computer stores it as 101010. When you type the letter 'A', it stores it as 01000001. Every piece of data is ultimately just a pattern of bits.

We work with higher-level representations because thinking in binary is hard. But sometimes, dropping down to the bit level lets you do things that are otherwise difficult or impossible.

How Binary Actually Works

You probably learned this in school and forgot it. Let's make it stick with an analogy.

Think of binary like an odometer, except instead of digits 0-9, you only have 0 and 1. When you increment:

0000 → 0001 → 0010 → 0011 → 0100 → 0101 → ...
  0      1      2      3      4      5   ...

Each position represents a power of 2, just like each position in decimal represents a power of 10.

In decimal, the number 3,427 means:

3 × 1000  +  4 × 100  +  2 × 10  +  7 × 1
3 × 10³   +  4 × 10²  +  2 × 10¹ +  7 × 10⁰

In binary, the number 1011 means:

1 × 8  +  0 × 4  +  1 × 2  +  1 × 1
1 × 2³ +  0 × 2² +  1 × 2¹ +  1 × 2⁰  =  11 in decimal

Each bit position represents a power of 2:

Position: 7    6    5    4    3    2    1    0
Value:    128  64   32   16   8    4    2    1

So if you see the binary number 10110101, you can decode it:

1×128 + 0×64 + 1×32 + 1×16 + 0×8 + 1×4 + 0×2 + 1×1
= 128 + 32 + 16 + 4 + 1
= 181

Why This Matters

Most of the time, you don't need to think about bits. High-level languages handle it for you. But there are scenarios where bit manipulation is either the only solution or dramatically better than alternatives.

Space efficiency: Suppose you're building a game and need to track 32 true/false states (has the player visited this room, picked up this item, defeated this boss, etc.). You could use an array of 32 booleans, wasting potentially 32 bytes. Or you could use a single 32-bit integer, where each bit represents one state. That's a 32x space reduction.

Speed: Bit operations are among the fastest things a CPU can do. They typically execute in a single clock cycle. If you can replace a loop or complex logic with bit operations, your code might get orders of magnitude faster.

Elegance: Some problems have beautiful bit-based solutions. Swapping two variables without a temporary, finding the only non-duplicate in an array, generating all subsets of a set—these can all be solved with clever bit manipulation.

The Basic Operations

There are six fundamental bit operations. Let's look at each one.

AND (&) - Both Must Be True

The AND operation compares bits pairwise. The result bit is 1 only if both input bits are 1.

  1010  (10 in decimal)
& 1100  (12 in decimal)
------
  1000  (8 in decimal)

Think of AND as a filter. It keeps only the bits that are set in both numbers.

Common use: Checking if a bit is set. If you want to know if the 3rd bit is set in a number:

number = 13      # binary: 1101
mask = 8         # binary: 1000 (only 3rd bit set)
if number & mask:
    print("3rd bit is set")

OR (|) - Either Can Be True

The OR operation sets a bit to 1 if either input bit is 1.

  1010  (10)
| 1100  (12)
------
  1110  (14)

Think of OR as a combiner. It merges the set bits from both numbers.

Common use: Setting bits. If you want to ensure the 3rd bit is set:

number = 5       # binary: 0101
number |= 8      # binary: 1000
# Result: 13     # binary: 1101

XOR (^) - Exactly One Must Be True

XOR (exclusive or) sets a bit to 1 if the bits are different.

  1010  (10)
^ 1100  (12)
------
  0110  (6)

XOR is the odd one out. It's incredibly useful because XORing a number with itself gives 0, and XORing with 0 gives the original number.

Common use: Toggling bits, finding unpaired elements, swapping without a temporary variable.

# Toggle the 3rd bit
number = 13      # binary: 1101
number ^= 8      # binary: 1000
# Result: 5      # binary: 0101

NOT (~) - Flip Everything

NOT flips all bits. 1 becomes 0, 0 becomes 1.

~ 1010  (10)
------
  0101  (5 in positive form, but NOT gives -11 due to two's complement)

This one is tricky because of how negative numbers work. In most languages, integers use two's complement representation, so ~n equals -(n+1).

Common use: Creating masks. To clear a bit, you often need ~(1 << position).

Left Shift (<<) - Multiply by Powers of 2

Shifting left moves all bits to the left and fills in zeros on the right.

  1010  (10)
<< 2
------
  101000  (40)

Each left shift multiplies by 2. Shifting by 2 positions multiplies by 4, shifting by 3 multiplies by 8, etc.

Common use: Fast multiplication by powers of 2, creating bit masks.

1 << 5  # Creates a mask with only the 5th bit set: 100000 (32)

Right Shift (>>) - Divide by Powers of 2

Shifting right moves all bits to the right, discarding bits that fall off.

  1010  (10)
>> 2
------
  10  (2)

Each right shift divides by 2 (integer division).

Common use: Fast division by powers of 2, extracting high-order bits.

Thinking in Bits: A Practical Example

Let's say you're designing a permissions system. You have four permissions: read, write, execute, and admin. You could represent them as four separate boolean variables, but here's a more elegant approach:

# Define permissions as powers of 2
READ = 1      # 0001
WRITE = 2     # 0010
EXECUTE = 4   # 0100
ADMIN = 8     # 1000

# Give a user read and execute permissions
user_perms = READ | EXECUTE  # 0001 | 0100 = 0101 (5)

# Check if user has write permission
has_write = bool(user_perms & WRITE)  # 0101 & 0010 = 0000 → False

# Grant write permission
user_perms |= WRITE  # 0101 | 0010 = 0111 (7)

# Revoke execute permission
user_perms &= ~EXECUTE  # 0111 & 1011 = 0011 (3)

# Check if user has admin permission
has_admin = bool(user_perms & ADMIN)  # 0011 & 1000 = 0000 → False

In four bits, you can store four separate boolean flags. In 32 bits, you can store 32 flags. This is how operating systems manage file permissions, how databases optimize storage, how games track achievements.

Common Patterns You'll See

Check if a number is even:

if n & 1 == 0:  # If last bit is 0, number is even
    print("even")

Check if a number is a power of 2:

if n > 0 and (n & (n - 1)) == 0:
    print("power of 2")

Why does this work? Powers of 2 have exactly one bit set (1000, 0100, 0010, 0001). Subtracting 1 flips all bits up to and including that bit (0111, 0011, 0001, 0000). ANDing them gives 0.

Swap two numbers without a temporary variable:

a ^= b
b ^= a
a ^= b
# a and b are now swapped

This works because XOR is its own inverse. If you XOR something twice with the same value, you get back the original.

When NOT to Use Bit Manipulation

Bit manipulation is powerful, but it's not always the right tool.

Readability matters: if user.has_permission(WRITE) is clearer than if user.perms & 0x02. Use bit manipulation when the performance or space savings justify the complexity, not just because it's clever.

Portability concerns: Bit manipulation can be platform-dependent. The size of an int, endianness, and right shift behavior (arithmetic vs logical) can vary.

Not all problems need it: If you're manipulating a handful of flags in application code, regular booleans are fine. Use bits when you're optimizing critical paths or when the problem naturally fits (subsets, masks, etc.).

The Bigger Picture

Bit manipulation is a tool in your toolbox. You won't use it every day, but when you need it, nothing else will do.

Understanding bits gives you insight into how computers actually work. It demystifies performance characteristics. It opens up a class of algorithms that seem like magic until you understand them.

In the next lessons, we'll dive deeper into specific operations, then explore classic bit manipulation algorithms. By the end, you'll be able to look at a problem and recognize when bits are the answer.