Number Representations

Positional Notation

A number in base $b$ with digits $d_n d_{n-1} \ldots d_1 d_0$ represents: $d_n \cdot b^n + d_{n-1} \cdot b^{n-1} + \cdots + d_1 \cdot b + d_0$

Each digit satisfies $0 \leq d_i < b$.

Common Number Systems

Base	Name	Digits
2	Binary	0, 1
8	Octal	0-7
10	Decimal	0-9
16	Hexadecimal	0-9, A-F

Hexadecimal Digits

Hex	Dec	Binary
0	0	0000
1	1	0001
2	2	0010
3	3	0011
4	4	0100
5	5	0101
6	6	0110
7	7	0111
8	8	1000
9	9	1001
A	10	1010
B	11	1011
C	12	1100
D	13	1101
E	14	1110
F	15	1111

Conversion: Base $b$ to Decimal

Expand using positional notation.

Example: $(1011)_2$ to decimal

$1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 8 + 0 + 2 + 1 = 11$

Example: $(2F)_{16}$ to decimal

$2 \cdot 16 + 15 = 32 + 15 = 47$

Conversion: Decimal to Base $b$

Repeatedly divide by $b$, record remainders (read bottom to top).

Example: 156 to binary

$156 \div 2 = 78 \text{ R } 0$ $78 \div 2 = 39 \text{ R } 0$ $39 \div 2 = 19 \text{ R } 1$ $19 \div 2 = 9 \text{ R } 1$ $9 \div 2 = 4 \text{ R } 1$ $4 \div 2 = 2 \text{ R } 0$ $2 \div 2 = 1 \text{ R } 0$ $1 \div 2 = 0 \text{ R } 1$

Answer: $(10011100)_2$

Quick Conversions

Binary ↔ Octal

Group binary digits in 3s (from right).

$(10011100)_2 = (010|011|100)_2 = (234)_8$

Binary ↔ Hexadecimal

Group binary digits in 4s (from right).

$(10011100)_2 = (1001|1100)_2 = (9C)_{16}$

Binary Arithmetic

Addition

  1011
+ 0111
------
 10010

Carry: 1 + 1 = 10 (write 0, carry 1)

Subtraction

Use borrowing or two's complement.

Multiplication

Similar to decimal, but simpler (only 0 and 1).

Signed Integer Representations

Sign-Magnitude

First bit is sign (0 = positive, 1 = negative), rest is magnitude.

Problem: Two representations of 0 (+0 and -0).

One's Complement

Negative: flip all bits.

Problem: Still two zeros.

Two's Complement (Most Common)

For $n$-bit number:

• Positive: standard binary
• Negative: flip bits and add 1 (or $2^n - |x|$)

Range: $-2^{n-1}$ to $2^{n-1} - 1$

Example (8-bit):

• $5 = 00000101$
• $-5$: flip → 11111010, add 1 → $11111011$

Advantage: Single zero, addition works for signed numbers.

Converting Negative Numbers

Method 1: Flip bits, add 1 Method 2: $-x$ in $n$ bits = $2^n - |x|$

Example

$-6$ in 8-bit two's complement: $2^8 - 6 = 256 - 6 = 250 = (11111010)_2$

Floating-Point Numbers

IEEE 754 Single Precision (32-bit)

Sign	Exponent	Mantissa
1 bit	8 bits	23 bits

Value: $(-1)^s \times 1.m \times 2^{e-127}$

where $s$ = sign bit, $m$ = mantissa, $e$ = biased exponent.

Special Values

• Zero: $e = 0$, $m = 0$
• Infinity: $e = 255$, $m = 0$
• NaN: $e = 255$, $m \neq 0$

Precision Limits

• Single (32-bit): ~7 decimal digits
• Double (64-bit): ~15 decimal digits

Bit Manipulation

Bitwise Operations

Operation	Symbol	Example
AND	&	$1010 \land 1100 = 1000$
OR	|	$1010 \lor 1100 = 1110$
XOR	^	$1010 \oplus 1100 = 0110$
NOT	~	$\neg 1010 = 0101$

Shift Operations

Left shift: $x << n$ multiplies by $2^n$ Right shift: $x >> n$ divides by $2^n$ (for unsigned)

Common Tricks

Check if bit $k$ is set: (x >> k) & 1 Set bit $k$: x | (1 << k) Clear bit $k$: x & ~(1 << k) Toggle bit $k$: x ^ (1 << k) Check power of 2: (x & (x-1)) == 0

Powers of 2

$2^n$	Value
$2^0$	1
$2^{10}$	1,024 (1 KB)
$2^{20}$	1,048,576 (1 MB)
$2^{30}$	1,073,741,824 (1 GB)
$2^{32}$	4,294,967,296
$2^{64}$	18,446,744,073,709,551,616