Bits, bytes and number representation

Everything is bits

Memory can store only two states per cell: on or off, written 1 or 0. One such cell is a bit. Everything a program keeps, numbers, text, images and the code itself, is a row of bits that the program agrees to interpret in a particular way.

Bits are grouped into bytes of 8. A byte can hold 2⁸ = 256 different patterns, from 00000000 to 11111111. The byte is the smallest unit a processor gives an address to: you can ask for the byte at address 1000, but not for a single bit on its own. Larger values use several bytes side by side. A 32-bit integer takes 4 bytes, a 64-bit integer 8, and on a 64-bit machine a memory address takes 8 as well.

Those sizes add up quickly, and they are the first thing to know about any data structure. A million 32-bit integers in an array take 4 MB. The same million numbers in a structure that adds an 8-byte pointer to each one take three times as much.

Binary and hexadecimal

A binary number works like a decimal one, except each position is worth twice the one to its right instead of ten times. Reading 100101100 from the right, the 1s sit at the positions worth 4, 8, 32 and 256, so it is 4 + 8 + 32 + 256 = 300.

Long binary numbers are hard to read, so programmers write them in hexadecimal, base 16. One hex digit stands for exactly 4 bits, using 0–9 and then A–F for 10–15:

Because 4 bits map to one hex digit, a byte is always exactly two hex digits, from 00 to FF. That is why memory dumps, colors such as #FF8800 and addresses such as 0x7ffd5a10 are written in hex. The 0x prefix just marks a number as hexadecimal.

How an integer sits in memory

In the trace above, x = 300 stores the 32-bit value 0x0000012C. Those are four bytes: 00, 00, 01 and 2C. The question is which one goes first.

On x86 and ARM processors, which run nearly every laptop, phone and server today, the least significant byte goes at the lowest address. This order is called little-endian, so 300 is stored as 2C 01 00 00. The opposite order, most significant byte first, is big-endian. Network protocols use big-endian, which is why it is also called network byte order.

Inside one program you rarely notice byte order, because the processor loads all 4 bytes at once and reassembles them. It matters the moment bytes leave the program: when you write integers to a file, send them over a network or read a binary format written on another machine. Every file format and protocol therefore states its byte order, and libraries such as Python's struct or Java's ByteBuffer let you choose it.

Negative numbers: two's complement

The bits can't hold a minus sign, so negative integers need a convention. Almost every processor uses two's complement: in an n-bit integer, the top bit is worth −2ⁿ⁻¹ instead of +2ⁿ⁻¹, and every other bit keeps its usual positive weight.

In 8 bits, the top bit is worth −128:

Two consequences are worth remembering. First, a number with every bit set is −1, at any width. Second, the range is lopsided: 8 bits hold −128 to 127, and 32 bits hold −2,147,483,648 to 2,147,483,647. There is one more negative number than positive.

To negate a number, flip every bit and add 1. Five is 00000101; flipped, 11111010; plus one, 11111011, which is −128 + 123 = −5. The reason processors use this scheme is that addition then needs no special cases: the same adder circuit gives the right bits whether the program treats them as signed or unsigned.

Overflow

A fixed-width integer has a largest value, and arithmetic can produce a result beyond it. The trace above adds 1 to 2,147,483,647, which is 0x7FFFFFFF. The carry ripples through bytes 0, 1 and 2 and finally sets the top bit. The bits are 0x80000000, and in two's complement that pattern means −2,147,483,648. The processor raised no error. It set an internal overflow flag that most compiled code never checks.

Languages decide what to do about that:

• Java, C# and Go define signed overflow to wrap around, exactly as in the trace.
• C and C++ make signed overflow undefined behavior. The compiler may assume it never happens and optimize on that basis, so a check such as if (x + 1 < x) can be deleted entirely. Unsigned integers do wrap.
• Rust panics on overflow in debug builds and wraps in release builds, and offers explicit checked_add and wrapping_add.
• Python integers have no fixed width. They grow as needed, so 2147483647 + 1 is simply 2147483648.
• JavaScript numbers are 64-bit floating-point values. They hold integers exactly only up to 2⁵³, about 9 × 10¹⁵.

Overflow bugs hide in ordinary code. For years, Java's Arrays.binarySearch computed the middle index as (low + high) / 2. Once arrays grew past about a billion elements, low + high could exceed the largest int and turn negative, and the search crashed. The fix, low + (high - low) / 2, appears in the binary search module of this track.

Numbers with fractions

Integers are exact. Numbers with fractions usually use floating point (IEEE 754): a 64-bit double spends 1 bit on the sign, 11 on an exponent and 52 on the digits. Floating point stores binary fractions, and most decimal fractions, such as 0.1, have no exact binary form, just as 1/3 has no exact decimal form. That is why 0.1 + 0.2 is 0.30000000000000004 in most languages. Never compare floating-point results with ==, and never store money in them; use integer cents or a decimal type instead.

Why a data structure cares

Every structure in this track is, in the end, a pattern of bytes at addresses. Knowing the size of each value tells you how much memory a structure takes and how many values fit in one cache line, which the last lesson of this module turns into speed. Knowing the range of an integer tells you when an index, a counter or a hash will overflow. The next lesson looks at the addresses themselves.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Bits, bytes and number representation from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

int32 x = 300
x = 2147483647      # the largest int32
x = x + 1           # the CPU adds; carries ripple up
print(x)            # -2147483648

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.