Binary Representation Revisited — The Language of Low-Level Optimization

Everything you've ever computed—every search query, every video frame, every neural network inference, every cryptocurrency transaction—ultimately reduces to operations on bits. The bit, short for 'binary digit,' is the atomic unit of digital information: a single entity that can exist in exactly one of two states.

We typically represent these states as 0 and 1. But at the hardware level, they manifest as voltage levels (low/high), magnetic orientations (north/south), optical states (dark/bright), or transistor conditions (off/on). The abstraction of 0 and 1 is how we reason about them—the physical reality is engineering marvel.

This page explores why bits form the foundation of all computation, how hardware implements bit-level operations, and why this understanding matters for writing efficient algorithms.

Why do computers use binary rather than decimal or some other base? The answer lies in physics and engineering—binary isn't a mathematical preference; it's a physical necessity for reliable computation.

Historical context:

Early computers explored various bases. ENIAC (1945) used decimal internally. But the transition to binary proved universal—by the 1950s, nearly all digital computers adopted binary representation. The advantages in reliability, speed, and cost were overwhelming.

The modern result:

Today's processors contain billions of transistors, each operating as a binary switch. The reliability of binary representation allows these switches to operate at frequencies exceeding 5 billion cycles per second (5 GHz) while maintaining correct computation. This wouldn't be possible with multi-level (e.g., decimal) representations.

Understanding how hardware implements bits illuminates why certain operations are fast and others slow. At the lowest level, transistors act as electrically controlled switches:

• Off (0): The transistor blocks current flow
• On (1): The transistor allows current to flow

By combining transistors, we build logic gates—the fundamental circuits that implement Boolean operations:

From gates to operations:

By connecting gates in specific configurations, we build more complex circuits:

• Adders: Combining AND, OR, and XOR gates to add binary numbers
• Multiplexers: Selecting between inputs based on control signals
• Registers: Storing bits using feedback loops
• ALU (Arithmetic Logic Unit): Combining all basic operations into a single component

The ALU performs operations like ADD, SUBTRACT, AND, OR, XOR, and SHIFT in response to control signals. Each of these operations typically completes in a single clock cycle—the fundamental unit of processor time.

The key insight for programmers:

Bitwise operations are not abstractions that get compiled down to something else—they directly correspond to hardware operations. When you write a & b in code, the processor literally performs an AND operation on the corresponding bits using AND gates. There's no interpretation, no library call, no overhead. This directness is why bit manipulation can be so efficient.

In binary representation, each bit position carries a specific weight or significance. Understanding this positional structure is essential for effective bit manipulation.

For an unsigned n-bit integer, the bits are numbered from 0 (rightmost, least significant) to n-1 (leftmost, most significant). The value of the integer is the sum of each bit multiplied by its positional weight:

Key terminology:

• Least Significant Bit (LSB): Bit position 0, weight 2⁰ = 1. Determines odd/even.
• Most Significant Bit (MSB): Highest bit position. For signed integers, this is the sign bit.
• Low bits / High bits: Informal terms for positions near LSB / MSB respectively.
• Bit n: Specifically refers to the bit at position n (0-indexed from right).

This positional structure has profound implications:

Visualizing bit positions:

Think of an integer's bits as a row of light switches, each controlling a different power of 2. Flipping switch 3 adds or removes 8 from the value. The switches are independent—flipping one never accidentally affects another.

This independence is what makes bit manipulation so powerful. We can encode multiple pieces of information in a single integer, manipulate them separately, and combine them freely.

Bits don't exist in isolation—they're grouped into larger units for practical computation:

• Bit: Single binary digit (0 or 1)
• Nibble: 4 bits (can represent 0–15, one hex digit)
• Byte: 8 bits (can represent 0–255 unsigned, or -128 to 127 signed)
• Word: Platform-dependent; typically 32 or 64 bits on modern systems

Most programming works with fixed-width integer types:

Why fixed-width matters for bit manipulation:

Bit manipulation techniques assume you know exactly how many bits you're working with. Consider left-shifting:

• In an 8-bit context, 10000000 << 1 results in 00000000 (the 1 bit shifts out)
• In a 16-bit context, 0000000010000000 << 1 results in 0000000100000000 (the 1 bit shifts into a higher position)

The same operation yields different results based on the bit width. Always be conscious of your integer type's width when performing bit manipulation.

Endianness—byte order:

When multi-byte integers are stored in memory, the order of bytes can vary:

• Little-endian: Least significant byte stored first (x86, ARM default)
• Big-endian: Most significant byte stored first (network protocols, some ARM)

For most bit manipulation, endianness doesn't matter—we work with the integer's value, not its memory layout. However, when interpreting raw bytes or writing low-level code, endianness becomes relevant.

Endianness affects byte order, not bit order within a byte. We'll revisit this when it matters; for now, focus on the logical bit structure rather than physical layout.

Modern CPUs are designed around bit-parallel operations. Understanding how the CPU handles bits explains why certain operations are fast and informs optimization strategies.

What this means for you:

When you can express an operation using bitwise logic rather than arithmetic, you're often choosing the fastest possible implementation. Replacing n % 2 with n & 1 isn't just stylistic—it's potentially 80x faster (though modern compilers often make this optimization automatically).

More importantly, understanding CPU bit capabilities helps you recognize when hardware can help. Need to count 1 bits in an integer? Don't write a loop—use the popcount intrinsic. Need the position of the lowest set bit? That's one instruction on most processors.

One of the most powerful aspects of working at the bit level is information density. Because each bit can represent two states, n bits can represent 2ⁿ distinct values. This exponential relationship has profound implications:

Practical power: subset representation

Consider a set of n elements. How many subsets are there? Exactly 2ⁿ—each element is either included or not. This maps perfectly to n bits:

• Bit i = 1: element i is in the subset
• Bit i = 0: element i is not in the subset

With 32 bits, we can represent any subset of a 32-element set. With 64 bits, any subset of 64 elements. Set operations become bitwise operations:

• Union: A | B (OR)
• Intersection: A & B (AND)
• Complement: ~A (NOT)
• Difference: A & ~B (AND NOT)
• Symmetric difference: A ^ B (XOR)

These set operations execute in O(1) time, regardless of how many elements are in the sets. This is the basis of bitmask techniques we'll explore extensively later.

Understanding bits at the hardware level directly informs algorithm design. Here's how the connections manifest:

Example: turning hardware knowledge into code

Suppose you need to check if a number is a power of 2. The naive approach:

function isPowerOfTwo(n) {
    if (n <= 0) return false;
    while (n > 1) {
        if (n % 2 != 0) return false;
        n = n / 2;
    }
    return true;
}

This loops O(log n) times with division in each iteration. Now, knowing that:

1. Powers of 2 have exactly one bit set
2. Subtracting 1 flips all bits from the rightmost 1
3. AND operates in parallel on all bits

We can write:

function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) == 0;
}

O(1) time, single-cycle operation. Hardware knowledge → algorithmic advantage.

Let's consolidate what we've learned about bits as the foundation of computation:

What's next:

With the foundational understanding of what bits are and how hardware handles them, we're ready to tackle a crucial question: how do we represent negative numbers? The next page explores positive and negative number representation—unsigned versus signed integers, the challenge of representing negatives, and the various schemes computers have employed to solve this fundamental problem.