13.2 Number systems and binary arithmetic

Number systems and binary arithmetic are the foundation of how digital systems represent and process information. Every operation a computer performs ultimately comes down to manipulating numbers in binary. This topic covers the four major number systems, how to convert between them, binary math, and the logic operations that drive digital circuits.

Number Systems

Binary, Decimal, Hexadecimal, and Octal

Each number system uses a different base, which determines how many unique digits it has and how place values work.

• Decimal (base 10) uses digits 0–9. This is the system you already know. Each place value is a power of 10 (ones, tens, hundreds, etc.).
• Binary (base 2) uses only 0 and 1. Each place value is a power of 2. This is the native language of digital hardware because circuits have two states: on and off.
• Hexadecimal (base 16) uses digits 0–9 and letters A–F (where A = 10, B = 11, ... F = 15). Each hex digit maps to exactly four binary bits, which makes it a convenient shorthand for long binary strings.
• Octal (base 8) uses digits 0–7. Each octal digit maps to exactly three binary bits. It's less common today but still shows up in some contexts like Unix file permissions.

Base Conversion

Decimal to Binary (repeated division by 2):

1. Divide the decimal number by 2.
2. Record the remainder (0 or 1).
3. Take the quotient and divide by 2 again.
4. Repeat until the quotient is 0.
5. Read the remainders from bottom to top. That's your binary number.

Example: Convert 13 to binary.

• 13 ÷ 2 = 6 remainder 1
• 6 ÷ 2 = 3 remainder 0
• 3 ÷ 2 = 1 remainder 1
• 1 ÷ 2 = 0 remainder 1

Reading bottom to top: $13_{10} = 1101_2$

Binary to Decimal (sum of weighted bits):

Multiply each bit by its corresponding power of 2, then add the results.

Example: $1101_2 = (1 \times 2^3) + (1 \times 2^2) + (0 \times 2^1) + (1 \times 2^0) = 8 + 4 + 0 + 1 = 13_{10}$

Binary ↔ Hexadecimal:

Group the binary digits into sets of four (starting from the right), then replace each group with its hex equivalent.

Example: $10111010_2$ → group as $1011 \; 1010$ → $B \; A$ → $BA_{16}$

To go the other direction, expand each hex digit into four bits.

Binary ↔ Octal:

Same idea, but group into sets of three bits.

Example: $101110_2$ → group as $101 \; 110$ → $5 \; 6$ → $56_8$

Binary Arithmetic

Binary Addition and Subtraction

Binary addition follows the same column-by-column approach as decimal addition, but with only two digits:

• $0 + 0 = 0$
• $0 + 1 = 1$
• $1 + 0 = 1$
• $1 + 1 = 10$ (write 0, carry 1)
• $1 + 1 + 1 = 11$ (write 1, carry 1)

Example: Add $1011 + 0110$

</>Code
  1 0 1 1
+ 0 1 1 0
---------
1 0 0 0 1

Work right to left: $1+0=1$, $1+1=10$ (write 0 carry 1), $0+1+1=10$ (write 0 carry 1), $1+0+1=10$ (write 0 carry 1), carry drops down as 1. Result: $10001_2$.

Binary subtraction is typically handled using two's complement (see next section), which lets you subtract by adding. This is a big deal in hardware design because it means the same adder circuit handles both addition and subtraction.

Signed vs. Unsigned Numbers and Two's Complement

Unsigned binary numbers represent only non-negative values. An $n$-bit unsigned number can represent values from $0$ to $2^n - 1$. For example, 8 bits gives you 0–255.

Signed binary numbers need a way to represent negatives. The standard method is two's complement:

• The most significant bit (MSB) acts as the sign bit: 0 means positive, 1 means negative.
• Positive numbers look the same as unsigned.
• An $n$-bit two's complement number ranges from $-2^{n-1}$ to $2^{n-1} - 1$. For 8 bits, that's $-128$ to $+127$.

Finding the two's complement (i.e., negating a number):

1. Write the binary representation of the positive value.
2. Flip every bit (0 → 1, 1 → 0). This is called the one's complement.
3. Add 1 to the result.

Example: Find the 4-bit two's complement of 5.

• $5_{10} = 0101_2$
• Flip bits: $1010$
• Add 1: $1011$

So $-5$ in 4-bit two's complement is $1011_2$.

Subtraction via two's complement: To compute $A - B$, find the two's complement of $B$ and add it to $A$. Any carry out beyond the bit width is discarded.

Example: $1101 - 0101$ (which is $13 - 5$ in 4-bit unsigned, or you can treat it as signed).

• Two's complement of $0101$ is $1011$.
• $1101 + 1011 = 11000$. Discard the carry → $1000_2 = 8_{10}$. Correct.

Bitwise Operations and Boolean Algebra

Bitwise Operations

Bitwise operations work on each pair of corresponding bits independently. They're used constantly in programming and hardware design for tasks like masking, toggling flags, and building logic circuits.

• AND: Output is 1 only if both input bits are 1.
• OR: Output is 1 if at least one input bit is 1.
• XOR (exclusive OR): Output is 1 if the inputs are different.
• NOT: Flips every bit (unary operation, applies to a single value).

Example with 4-bit numbers:

</>Code
  A =  1 1 0 1
  B =  1 0 1 1
--------------
AND =  1 0 0 1
 OR =  1 1 1 1
XOR =  0 1 1 0
NOT A= 0 0 1 0

A practical use: if you want to check whether bit 2 of a byte is set, you AND the byte with $00000100_2$. If the result is nonzero, that bit is 1. This is called bit masking.

Boolean Algebra

Boolean algebra is the math behind digital logic. It deals with variables that are either true (1) or false (0), combined using AND, OR, and NOT operations.

Boolean expressions describe the behavior of logic circuits. For example, the expression $F = A \cdot B + \overline{C}$ means "F is true when both A and B are true, or when C is false."

Several key laws let you simplify Boolean expressions (and therefore simplify circuits):

• Commutative: $A \cdot B = B \cdot A$ and $A + B = B + A$
• Associative: $A \cdot (B \cdot C) = (A \cdot B) \cdot C$
• Distributive: $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$
• Identity: $A \cdot 1 = A$ and $A + 0 = A$
• Complement: $A \cdot \overline{A} = 0$ and $A + \overline{A} = 1$
• De Morgan's Theorems: $\overline{A \cdot B} = \overline{A} + \overline{B}$ and $\overline{A + B} = \overline{A} \cdot \overline{B}$

Boolean algebra connects directly to circuit design: every Boolean expression can be built from AND, OR, and NOT gates. Simplifying the expression means fewer gates, which means cheaper, faster hardware.