Binary Representation and Computer Arithmetic

EveryEvery value a computer works with — a character, an integer, a photograph, a piece of music — is, underneath, a sequence of binary digits. What makes that workable isn't magic; it's a small set of agreed encodings for turning numbers and text into bit patterns and back, applied consistently enough that hardware built by one manufacturer can exchange data with software written by someone who has never seen that hardware. Patterson and Hennessy's textbook is the standard modern treatment of this material, and the account below follows its framing¹.

Positional Number Systems

Decimal,Decimal, binary, and hexadecimal are all positional systems: a digit's contribution to the total depends on which position it sits in, not just which symbol it is. In binary (base 2), the rightmost bit is worth 2⁰ = 1, the next worth 2¹ = 2, then 2², 2³, and so on — so the pattern 1011 is (1×8) + (0×4) + (1×2) + (1×1) = 11 in decimal. Hexadecimal (base 16, digits 0-9 then A-F) is used constantly alongside binary purely for human convenience: each hex digit maps exactly onto four binary bits, so 1011 1100 becomes BC in hex — far easier for a person to read, write, and spot errors in than thirty-two raw bits, while remaining trivially convertible back to exactly the same binary pattern.

Two's Complement

RepresentingRepresenting negative integers naively — a dedicated sign bit plus a magnitude — creates an awkward problem: addition needs completely different logic depending on the signs of the two operands, and there ends up being two representations of zero (+0 and -0). Two's complement avoids both problems with a single trick: to negate a number, flip every bit, then add 1. In 4-bit two's complement, 3 is 0011; flipping gives 1100, adding 1 gives 1101, which represents -3.

The reason this representation dominates every modern processor is that it makes subtraction "just addition" — the hardware needs only one adder circuit, not a separate adder and subtracter. Adding 5 + (-3) in 4-bit two's complement: 0101 + 1101 = 10010; discard the overflow bit that doesn't fit in 4 bits, leaving 0010 = 2, which is exactly 5 + (-3). The same addition circuit that computes 5 + 3 also, with no special-casing at all, correctly computes 5 - 3, purely because of how negative numbers were encoded.

Floating-Point Representation

IntegersIntegers can't represent fractional or very large/small values efficiently, so the IEEE 754 standard — the actual normative specification every mainstream language's floating-point type ultimately implements² — splits a floating-point number into three fields: a sign bit, an exponent (how far to shift the binary point), and a mantissa (the significant digits) — conceptually the same idea as scientific notation (6.02 × 10²³), just in binary and packed into a fixed number of bits.

Format	Sign	Exponent	Mantissa	Total bits
Single precision	1	8	23	32
Double precision	1	11	52	64

The consequence worth knowing before it causes a confusing bug: not every decimal fraction has an exact binary representation, in exactly the same way ⅓ has no exact finite decimal representation. 0.1 in binary is an infinitely repeating fraction, so it gets rounded to the nearest value the mantissa can actually hold — which is why, in most programming languages, 0.1 + 0.2 == 0.3 evaluates to false: both sides are already tiny roundings of the "true" values, and those roundings don't happen to cancel out exactly. Interval Arithmetic covers the standard technique for making this kind of rounding error a tracked, guaranteed bound rather than a silent surprise.

Binary Logic and Arithmetic Circuits

AND,AND, OR, XOR, and NOT are the logical operations a processor's arithmetic is actually built from. A single-bit adder — a half-adder — is the cleanest illustration: given two input bits A and B, the sum bit is A XOR B (1 exactly when the inputs differ) and the carry bit is A AND B (1 exactly when both inputs are 1, the only case that produces a carry). Chaining half-adders together, with each one also taking the previous stage's carry as a third input, builds a full adder, and chaining full adders builds an adder for an entire multi-bit word — the same two's-complement addition described above, implemented directly as a physical circuit of logic gates rather than as an abstract operation.

A  B  | Sum (A XOR B) | Carry (A AND B)
0  0  |      0        |       0
0  1  |      1        |       0
1  0  |      1        |       0
1  1  |      0        |       1

This is the same three-bit vocabulary — AND, OR, XOR — used throughout the rest of computing wherever bit-level operations show up, from setting permission flags to implementing a hash function; the arithmetic-circuit use here is simply the most literal one, where a logic gate's output is, physically, a number being computed.

References