Binary Representation and Number Bases

# Binary Representation and Number Bases

## CS 631 Systems Foundations

---

## Positional Notation

Value of a number depends on **position** and **base**:

$$value = \sum_{i=0}^{n-1} d_i \times base^i$$

**Decimal example**: `735`

| Position | Digit | Place Value | Contribution |
|----------|-------|-------------|--------------|
| 2 | 7 | 10² = 100 | 700 |
| 1 | 3 | 10¹ = 10 | 30 |
| 0 | 5 | 10⁰ = 1 | 5 |

Same formula works for **any base**.

---

## Binary (Base 2)

Two digits: `0` and `1`

| Bit Position | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|-------------|---|---|---|---|---|---|---|---|
| Place Value | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |

**Example**: `1011` in binary

```text
1×8 + 0×4 + 1×2 + 1×1 = 11
```

---

## 32-Bit Registers

```text
Bit:  31 30 29 28 ... 3  2  1  0
      MSB                     LSB
```

| Unit | Bits | Distinct Values |
|------|------|-----------------|
| Bit | 1 | 2 |
| Nibble | 4 | 16 |
| Byte | 8 | 256 |
| Word | 32 | 4,294,967,296 |

**MSB** = Most Significant Bit (leftmost)

**LSB** = Least Significant Bit (rightmost)

---

## Decimal-to-Binary Conversion

Convert `13` to binary (repeated division by 2):

```text
13 / 2 = 6 remainder 1  (LSB)
 6 / 2 = 3 remainder 0
 3 / 2 = 1 remainder 1
 1 / 2 = 0 remainder 1  (MSB)

Read bottom-to-top: 1101
```

13₁₀ = 1101₂

---

## Hexadecimal (Base 16)

4 binary digits = 1 hex digit (since 2⁴ = 16)

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

---

## Hex-Binary Conversion

Just substitute each hex digit with its 4-bit pattern:

```text
Hex:     0x1A3F
Binary:  0001 1010 0011 1111
         ^^^^  ^^^^  ^^^^  ^^^^
          1     A     3     F
```

<div class="info-box">
This 4-bit grouping is why hex is so useful for systems programming!
</div>

---

## Two's Complement: The Problem

With n bits, we have 2ⁿ bit patterns.

**Signed magnitude** (MSB = sign bit) has problems:

- Two zeros: `+0` and `-0`
- Addition requires checking signs
- Complex hardware

<div class="highlight-box">
We need a better representation for negative numbers.
</div>

---

## Two's Complement: The Solution

**To negate**: invert all bits, then add 1.

```text
 5 = 0101
     ↓ invert all bits
     1010
     ↓ add 1
-5 = 1011
```

**Verify**: `0101 + 1011 = 10000` → carry discarded → `0000` = 0 ✓

---

## Two's Complement: 4-Bit Range

| Binary | Unsigned | Signed |
|--------|----------|--------|
| `0000` | 0 | 0 |
| `0001` | 1 | 1 |
| `0010` | 2 | 2 |
| `0011` | 3 | 3 |
| `0100` | 4 | 4 |
| `0101` | 5 | 5 |
| `0110` | 6 | 6 |
| `0111` | 7 | **7** (max) |
| `1000` | 8 | **-8** (min) |
| `1001` | 9 | -7 |
| `1010` | 10 | -6 |
| `1011` | 11 | -5 |
| `1100` | 12 | -4 |
| `1101` | 13 | -3 |
| `1110` | 14 | -2 |
| `1111` | 15 | -1 |

---

## Two's Complement: Range Formula

For n-bit two's complement:

| Property | Formula | 32-bit Value |
|----------|---------|-------------|
| Minimum | −2ⁿ⁻¹ | −2,147,483,648 |
| Maximum | 2ⁿ⁻¹ − 1 | 2,147,483,647 |
| Total | 2ⁿ | 4,294,967,296 |

**Key properties:**

- MSB = 1 means negative
- Only one zero
- Addition works the same as unsigned

---

## Bitwise NOT

Inverts every bit: 0 → 1, 1 → 0

```text
NOT 0101 1010
  = 1010 0101
```

| Input | Output |
|-------|--------|
| 0 | 1 |
| 1 | 0 |

---

## Bitwise AND

Result is 1 only when **both** bits are 1.

```text
  1100 1010
& 1111 0000
-----------
  1100 0000
```

<div class="info-box">
<strong>Use case — Masking</strong>: Extract specific bits by ANDing with a mask.
</div>

---

## Bitwise OR and XOR

**OR**: Result is 1 when **either** bit is 1.

```text
  1100 1010          Use case: Setting bits
| 0011 0000
-----------
  1111 1010
```

**XOR**: Result is 1 when bits are **different**.

```text
  1100 1010          Use case: Toggling bits
^ 1111 0000
-----------
  0011 1010
```

---

## Bitwise Operations Summary

| Operation | Rule | Use Case |
|-----------|------|----------|
| NOT | Invert all bits | Complement |
| AND | 1 if both 1 | Masking (extract bits) |
| OR | 1 if either 1 | Setting bits |
| XOR | 1 if different | Toggling bits |

---

## Shift Operations

**Logical Shift Left (LSL)**: Fill with 0s on right

```text
0011 0101  (53)  LSL 2 →  1101 0100  (212)
```

Effect: multiply by 2ⁿ

**Logical Shift Right (LSR)**: Fill with 0s on left

```text
1101 0100  (212) LSR 2 →  0011 0101  (53)
```

Effect: unsigned divide by 2ⁿ

---

## Arithmetic Shift Right (ASR)

Preserves the **sign bit** (MSB):

```text
1101 0100  (signed: -44)
ASR 2 →
1111 0101  (signed: -11)
```

```text
LSR:  [0 b31 b30 ... b1]     ← fill with 0
ASR:  [b31 b31 b30 ... b1]   ← fill with sign bit
```

<div class="highlight-box">
ASR = signed divide by 2ⁿ (rounds toward −∞)
</div>

---

## String-to-Integer Algorithm

**Left-to-right accumulation**:

```text
value = 0
for each character c:
    digit = char_to_digit(c)
    value = value * base + digit
```

Example: `"1A3"` in base 16:

| Char | Digit | Computation | Value |
|------|-------|-------------|-------|
| `1` | 1 | 0 × 16 + 1 | 1 |
| `A` | 10 | 1 × 16 + 10 | 26 |
| `3` | 3 | 26 × 16 + 3 | 419 |

---

## Integer-to-String Algorithm

**Division/modulo** (produces digits in reverse):

```text
while value > 0:
    remainder = value % base
    append digit_to_char(remainder)
    value = value / base
reverse the result
```

Example: 419 to hex:

| Value | % 16 | Digit | / 16 |
|-------|------|-------|------|
| 419 | 3 | `3` | 26 |
| 26 | 10 | `A` | 1 |
| 1 | 1 | `1` | 0 |

Reversed: `"1A3"`

---

## Width Mask

Isolate the lower w bits:

$$mask = (1 \ll w) - 1$$

| Width | Mask (Binary) | Mask (Hex) |
|-------|---------------|------------|
| 4 | `0000 1111` | `0x0F` |
| 8 | `1111 1111` | `0xFF` |
| 16 | `0000...1111 1111 1111 1111` | `0xFFFF` |

Apply: `masked_value = value & mask`

---

## Sign Extension

When a narrow value's MSB is 1, fill upper bits with 1:

```text
Width 4, value = 0xB (1011):

Before: 0000 0000 0000 0000 0000 0000 0000 1011
After:  1111 1111 1111 1111 1111 1111 1111 1011
      = 0xFFFFFFFB = -5
```

<div class="info-box">
Sign extension preserves the value's signed interpretation across different widths.
</div>

---

## Summary

1. **Positional notation** — value = digits × base^position

2. **Binary** — 2 digits, foundation of digital hardware

3. **Hexadecimal** — compact binary, 4 bits = 1 hex digit

4. **Two's complement** — negate = invert + add 1

5. **Bitwise ops** — NOT, AND, OR, XOR for bit manipulation

6. **Shifts** — LSL (×2ⁿ), LSR (÷2ⁿ unsigned), ASR (÷2ⁿ signed)

7. **Conversion** — left-to-right (str→int), division/modulo (int→str)

8. **Width masking** — mask = (1 << w) - 1