C Base Conversion: Binary, Decimal, and Hexadecimal

# C Base Conversion: Binary, Decimal, and Hexadecimal

## CS 315 Computer Architecture

---

## Learning Objectives

- Parse optional command-line arguments using a loop
- Distinguish a numeric **quantity** from its **string** and **machine integer** forms
- Apply positional notation in base 10, 2, and 16
- Read C literals: `13`, `0b1101`, `0xD` — same value, different notation
- Compute the value range of an `n`-bit unsigned number
- Convert a decimal string to a machine integer using ASCII arithmetic
- Convert a machine integer to a digit string using division and modulo
- Detect input base from prefix (`0b`, `0x`, or none) for Project 1

---

## Optional Command-Line Arguments

Unix tools accept **options** (flags) beginning with `-`:

```bash
ls -a              # one option
ls -a -l           # two options (order doesn't matter)
gcc -o foo main.c  # option that TAKES an argument
```

Key rules:
- Options can appear in any order
- Some options consume the **next** token as their value

---

## Argument Parsing Strategy

Walk `argv` left to right; recognize and **consume** each option:

<div class="mermaid">
flowchart LR
    A[Start at argv index 1] --> B{Starts with '-'?}
    B -- yes --> C[Identify option]
    C --> D{Takes argument?}
    D -- yes --> E[Consume next argv]
    D -- no --> F[Set flag]
    E --> G[Advance index]
    F --> G
    B -- no --> H[Positional argument]
    H --> G
    G --> I{More args?}
    I -- yes --> B
    I -- no --> J[Done]
</div>

---

## Example: echorepeat

```bash
echorepeat -h -f -n <count> <string>
```

| Token | Meaning |
|-------|---------|
| `-h` | print a header |
| `-f` | print a footer |
| `-n <count>` | repeat `count` times |
| `<string>` | positional argument |

```bash
$ echorepeat -h -f foo
- - - - -
foo
- - - - -
```

---

## argc and argv

`argv[0]` is always the program name. For `echorepeat -h foo`:

```text
echorepeat   -h   foo
    0          1    2     <- argv index

argc == 3
```

The loop starts at index `1` and runs while `i < argc`.

Options that take a value advance `i` by **2**; standalone flags advance by **1**.

---

## Keep main Small

<div class="mermaid">
flowchart LR
    A["argc, argv"] --> B["parse_args()"]
    B --> C["struct options\n(header, footer, count, string)"]
    C --> D["generate_output()"]
    D --> E["stdout"]
</div>

<div class="info-box">
Split parsing from output generation. Do not pile all logic into <code>main</code>.
</div>

---

## Three Faces of a Number

Consider the value two hundred forty-five:

```text
   245            "245"              [ 245 ]
 quantity         string          machine integer
                                     (binary)
```

| Form | What it is | In memory |
|------|-----------|-----------|
| quantity | Abstract math value | A concept |
| `"245"` | Characters `'2'`, `'4'`, `'5'` | ASCII bytes |
| machine int | CPU's binary encoding | Fixed-width bits |

---

## The String "245" Is ASCII Bytes

```text
"245"
 byte  byte  byte  byte
 '2'   '4'   '5'   '\0'
  50    52    53     0     <- ASCII codes
```

<div class="highlight-box">
The character <code>'2'</code> is <em>not</em> the number 2 — it is the byte value 50.
</div>

The machine integer 245 is stored as binary: `1111 0101`

---

## The Conversion Round-Trip

Project 1's job: convert between string and machine integer forms.

<div class="mermaid">
flowchart LR
    A["input string\n0x2AF"] --> B["parse\nASCII arithmetic"]
    B --> C["uint32_t\n687"]
    C --> D["format\ndiv/mod"]
    D --> E["output strings\n0b..., 0xF5, 245"]
</div>

---

## Bases: Decimal, Binary, Hexadecimal

| Base | Name | Digits | C prefix |
|------|------|--------|----------|
| 10 | decimal | `0–9` | none |
| 2 | binary | `0 1` | `0b` |
| 16 | hexadecimal | `0–9, A–F` | `0x` |

The number of distinct digits equals the base.
Hex borrows letters `A–F` for values 10–15.

---

## Positional Notation

The one formula behind **all** bases:

$$\text{value} = \sum_{i=0}^{n-1} d_i \times b^{\,i}$$

Example: `245` in base 10

```text
245 = (2 × 10²) + (4 × 10¹) + (5 × 10⁰)
    =    200    +    40     +    5
    = 245
```

Positions are counted from the **right**, starting at 0.

---

## Binary (Base 2)

Place values are powers of 2. Evaluate `0b1101`:

```text
 3  2  1  0    <- positions
 1  1  0  1
 8  4  2  1    <- place values (2³ 2² 2¹ 2⁰)

0b1101 = 8 + 4 + 0 + 1 = 13
```

The same value written three ways in C — identical machine bits:

```c
int x = 13;       // decimal literal
int x = 0b1101;   // binary literal  (GCC extension)
int x = 0xD;      // hexadecimal literal
```

---

## MSB and LSB

```text
        0b 1  1  0  1
            ↑        ↑
         most      least
      significant  significant
         bit (MSB)  bit (LSB)
```

- **MSB** — leftmost, largest place value
- **LSB** — rightmost, place value $2^0 = 1$

---

## n-Bit Value Range

With `n` bits there are $2^n$ distinct patterns:

| Bits | Patterns ($2^n$) | Min | Max ($2^n - 1$) |
|------|-----------------|-----|-----------------|
| 4 | 16 | 0 | 15 |
| 8 | 256 | 0 | 255 |
| 16 | 65,536 | 0 | 65,535 |
| 32 | 4,294,967,296 | 0 | 4,294,967,295 |

<div class="info-box">
Project 1 uses <code>uint32_t</code>: 32 bits, range 0 to 4,294,967,295.
</div>

---

## Hexadecimal (Base 16)

Each hex digit corresponds to exactly **4 bits** (a nibble), because $2^4 = 16$.

| Dec | Bin | Hex | | Dec | Bin | Hex |
|-----|-----|-----|-|-----|-----|-----|
| 0 | 0000 | 0 | | 8 | 1000 | 8 |
| 1 | 0001 | 1 | | 9 | 1001 | 9 |
| 4 | 0100 | 4 | | 10 | 1010 | A |
| 7 | 0111 | 7 | | 15 | 1111 | F |

Project 1 must accept both upper and lower case (`A`/`a` through `F`/`f`).

---

## Hex to Decimal: 0x2AF

```text
   2   1   0     <- positions
0x 2   A   F

= (2 × 16²) + (A × 16¹) + (F × 16⁰)
= (2 × 256) + (10 × 16) + (15 × 1)
=    512    +    160    +    15
=  687
```

---

## Hex-Binary Substitution

Because each hex digit is exactly 4 bits, convert by **direct substitution** — no arithmetic:

```text
Hex:     0x  2      A      F
Binary:    0010   1010   1111

0x2AF = 0b 0010 1010 1111
```

Going hex → binary: replace each digit with its 4-bit group.
Going binary → hex: group bits into fours from the right.

---

## Project 1: numconv

```bash
$ numconv 687 -o 16
0x2AF

$ numconv 0x2AF -o 10
687

$ numconv 213 -o 2 -o 16 -o 10
0b11010101
213
0xd5
```

When multiple `-o` bases are given, output order is fixed: **2, 10, 16**.

---

## Normalization Strategy

Rather than one converter per (input, output) pair, funnel everything through a single `uint32_t`:

<div class="mermaid">
flowchart LR
    A["dec str"] --> N["uint32_t"]
    B["bin str"] --> N
    C["hex str"] --> N
    N --> D["dec str"]
    N --> E["bin str"]
    N --> F["hex str"]
    style N fill:#e8f5e9,stroke:#00543c,stroke-width:2px
</div>

Two reusable directions: **string → int** and **int → string**.

---

## Detecting Input Base

Inspect the first two characters (the prefix):

```text
if (prefix == "0b")  ->  binary  (base 2)
if (prefix == "0x")  ->  hex     (base 16)
else                 ->  decimal (base 10)
```

| Prefix | Base | Example |
|--------|------|---------|
| `0b` | 2 | `0b1010` |
| `0x` | 16 | `0xFF` |
| none | 10 | `1234` |

After detection, strip the prefix, then convert the remaining digits.

---

## String to Integer: ASCII Arithmetic

Project 1 forbids `atoi` and `scanf`. We convert by hand.

The key trick — digit characters are consecutive in ASCII:

```text
'0' = 48,  '1' = 49,  '2' = 50,  ...  '9' = 57
```

Subtracting `'0'` gives the digit's numeric value:

```c
'2' - '0'  =  50 - 48  =  2
'5' - '0'  =  53 - 48  =  5
```

---

## decstr_to_uint32: The Loop

Process left to right: multiply running total by base, then add digit.

```c
uint32_t decstr_to_uint32(char *s) {
    int v = 0, i = 0;
    while (s[i] != '\0') {
        v = v * 10;
        v = v + (s[i] - '0');
        i = i + 1;
    }
    return v;
}
```

Trace for `"245"`:

| i | s[i] | digit | v |
|---|------|-------|---|
| 0 | `'2'` | 2 | 2 |
| 1 | `'4'` | 4 | 24 |
| 2 | `'5'` | 5 | 245 |

---

## Handling Hex Letters

For any base, replace `s[i] - '0'` with a helper:

```c
int char_to_digit(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'a' && c <= 'f') return c - 'a' + 10;
    if (c >= 'A' && c <= 'F') return c - 'A' + 10;
    return -1;  // invalid
}
```

Then replace `10` in the loop with the detected `base` variable.

---

## Integer to String: Division and Modulo

For value `v` and base 10:

```text
245 / 10  = 24   <- quotient (strips last digit)
245 % 10  = 5    <- remainder (extracts last digit)
```

Repeat to peel off digits one at a time:

| Step | v | d = v % 10 | char | v = v / 10 |
|------|---|-----------|------|-----------|
| 1 | 245 | 5 | `'5'` | 24 |
| 2 | 24 | 4 | `'4'` | 2 |
| 3 | 2 | 2 | `'2'` | 0 |

Digits come out **least significant first** — must be reversed.

---

## int_to_string: The Algorithm

```c
void int_to_string(uint32_t value, char *str, int base) {
    char buf[33];
    int i = 0;
    if (value == 0) { buf[i++] = '0'; }
    while (value != 0) {
        buf[i++] = digit_to_char(value % base);
        value = value / base;
    }
    // reverse buf into str
    int j = 0;
    while (i > 0) { str[j++] = buf[--i]; }
    str[j] = '\0';
}
```

<div class="highlight-box">
After producing digits, prepend the prefix: <code>0b</code> for binary, <code>0x</code> for hex, nothing for decimal.
</div>

---

## int_to_string: Flow

<div class="mermaid">
flowchart TD
    A["value, base"] --> B{"value == 0?"}
    B -- yes --> C["emit '0'"]
    B -- no --> D["rem = value % base"]
    D --> E["push digit_to_char(rem)"]
    E --> F["value = value / base"]
    F --> G{"value != 0?"}
    G -- yes --> D
    G -- no --> H["reverse digits"]
    C --> H
    H --> I["null-terminate"]
</div>

---

## Complete numconv Data Flow

<div class="mermaid">
flowchart TD
    A["input string\ne.g. 0x2AF"] --> B["detect base from prefix"]
    B --> C["strip prefix"]
    C --> D["string_to_int\nASCII arithmetic"]
    D --> E["uint32_t value\ne.g. 687"]
    E --> F["for each -o base\norder: 2, 10, 16"]
    F --> G["int_to_string\ndiv / mod"]
    G --> H["prepend prefix\n0b / none / 0x"]
    H --> I["print line"]
</div>

---

## Worked Trace: numconv 0x2AF -o 10

1. Prefix `0x` → base **16**
2. Strip prefix → `"2AF"`
3. `string_to_int("2AF", 16)` → **687**
4. Output base **10** requested
5. `int_to_string(687, str, 10)` → `"687"`
6. No prefix for decimal → print `687`

The same `uint32_t` 687 could be formatted as `0b1010101111` or `0x2af` with the same `int_to_string` function.

---

## Summary

1. **Option parsing** uses a loop over `argv` that recognizes `-` prefixes and consumes each option (and its value when needed).

2. **Three forms**: quantity (abstract), string (ASCII bytes), machine integer (binary bits). Computation happens in binary.

3. **Positional notation**: value = sum of digit × base^position. Works for base 10, 2, and 16.

4. **Binary** uses powers of 2; **hex** uses powers of 16. Each hex digit = exactly 4 bits.

5. **n-bit range**: $2^n$ patterns, values 0 to $2^n - 1$.

6. **String → int**: subtract `'0'` (or A-offset) per digit; accumulate with `v = v * base + digit`.

7. **Int → string**: repeated `% base` (digit) and `/ base` (advance); reverse result; prepend prefix.