Chapter 03 of 39

Number Systems & Conversions

We count in tens because we have ten fingers. A computer has no fingers; it has transistors that are either on or off. Telling two states apart is easy and reliable even when voltages are noisy, while telling ten states apart would be fragile. So computers count in twos: everything inside them, from your marks sheet to a YouTube video, is stored as binary digits (bits).

Long strings of bits are hard for humans to read, so we also use octal (base 8) and especially hexadecimal (base 16) as compact shorthands. In this chapter we learn how positional number systems work and how to convert between any two bases, for both integers and fractions. These conversions are the foundation of every later chapter, and they appear directly in university exams and GATE.


Positional Number Systems

In a positional number system with base (radix) r, a number is written with digits from 0 to r - 1, and each position has a weight that is a power of r. The digit just left of the radix point has weight r0, the next r1, and so on; digits to the right have weights r-1, r-2, and so on.

For a number with digits dn-1 ... d1 d0 . d-1 d-2 ... d-m in base r:

Value = d(n-1) x r^(n-1) + ... + d1 x r^1 + d0 x r^0 + d(-1) x r^(-1) + ... + d(-m) x r^(-m)

Decimal works exactly this way: 472.5 = 4 × 102 + 7 × 101 + 2 × 100 + 5 × 10-1. We write the base as a subscript when there is any doubt: (472.5)10, (1011)2, (9C)16.

System

Base

Digits

Common notation in code

Binary

2

0, 1

0b1011 (Python, C23, GCC extension)

Octal

8

0 to 7

0o17 (Python), 017 (C, leading zero)

Decimal

10

0 to 9

15

Hexadecimal

16

0 to 9, A (10), B (11), C (12), D (13), E (14), F (15)

0xF

The First Sixteen Numbers

Memorise this table; it makes every grouping conversion instant.

Decimal

Binary

Octal

Hex

Decimal

Binary

Octal

Hex

0

0000

0

0

8

1000

10

8

1

0001

1

1

9

1001

11

9

2

0010

2

2

10

1010

12

A

3

0011

3

3

11

1011

13

B

4

0100

4

4

12

1100

14

C

5

0101

5

5

13

1101

15

D

6

0110

6

6

14

1110

16

E

7

0111

7

7

15

1111

17

F

Also remember the powers of two: 20 to 210 are 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024.


Any Base to Decimal

Method: multiply each digit by its positional weight and add. This is just the definition.

Example 1. (10110.101)2

Integer part : 1x16 + 0x8 + 1x4 + 1x2 + 0x1 = 22
Fraction part: 1x(1/2) + 0x(1/4) + 1x(1/8)  = 0.5 + 0.125 = 0.625
(10110.101)2 = (22.625)10

Example 2. (3A7.C)16

3 x 16^2 + 10 x 16^1 + 7 x 16^0 + 12 x 16^-1
= 768 + 160 + 7 + 0.75
= (935.75)10

Example 3. (212)3 = 2 × 9 + 1 × 3 + 2 × 1 = (23)10.

Faster for integers (Horner's method): start from the leftmost digit, and repeatedly "multiply by the base and add the next digit". For (3A7)16: 3 → 3 × 16 + 10 = 58 → 58 × 16 + 7 = 935. This is also exactly how strtol and similar library functions parse a number string.


Decimal to Any Base

The integer part and the fractional part are converted separately, with different methods.

Integer Part: Repeated Division

Divide by the target base r, write down the remainder, and continue with the quotient until it becomes 0. The remainders, read from last to first (bottom to top), are the digits.

Why it works: N = q × r + d0, so the remainder of N ÷ r is exactly the last digit d0, and the quotient q is the number with that digit removed. Repeating peels off one digit at a time, least significant first.

Example 4. (156)10 to binary:

156 / 2 = 78  remainder 0   <- least significant bit (LSB)
 78 / 2 = 39  remainder 0
 39 / 2 = 19  remainder 1
 19 / 2 =  9  remainder 1
  9 / 2 =  4  remainder 1
  4 / 2 =  2  remainder 0
  2 / 2 =  1  remainder 0
  1 / 2 =  0  remainder 1   <- most significant bit (MSB)

Read bottom to top: (156)10 = (10011100)2

Check: 128 + 16 + 8 + 4 = 156. The same method gives (156)10 = (234)8 and (9C)16.

Example 5. (175)10 to octal: 175 ÷ 8 = 21 r 7; 21 ÷ 8 = 2 r 5; 2 ÷ 8 = 0 r 2. Reading upwards: (257)8. Check: 2 × 64 + 5 × 8 + 7 = 175.

Fractional Part: Repeated Multiplication

Multiply the fraction by r. The integer part of the result is the next digit; continue with the fractional part. The digits are read from first to last (top to bottom). Stop when the fraction becomes 0 or you have enough digits.

Why it works: if F = 0.d-1d-2... in base r, then F × r = d-1.d-2..., so the integer part of F × r is the first digit after the point.

Example 6. (0.6875)10 to binary:

0.6875 x 2 = 1.375   -> 1   (first digit after the point)
0.375  x 2 = 0.75    -> 0
0.75   x 2 = 1.5     -> 1
0.5    x 2 = 1.0     -> 1   fraction is now 0, stop

Read top to bottom: (0.6875)10 = (0.1011)2

Check: 1/2 + 1/8 + 1/16 = 0.5 + 0.125 + 0.0625 = 0.6875.

Example 7. (25.375)10 to binary. Integer part: 25 = 11001. Fraction: 0.375 × 2 = 0.75 → 0; 0.75 × 2 = 1.5 → 1; 0.5 × 2 = 1.0 → 1, so 0.011. Answer: (11001.011)2.

Fractions That Never End

Example 8. (0.1)10 to binary:

0.1 x 2 = 0.2 -> 0
0.2 x 2 = 0.4 -> 0
0.4 x 2 = 0.8 -> 0
0.8 x 2 = 1.6 -> 1
0.6 x 2 = 1.2 -> 1
0.2 x 2 = 0.4 -> 0      <- 0.2 again: the pattern repeats from here
0.4 x 2 = 0.8 -> 0
0.8 x 2 = 1.6 -> 1
0.6 x 2 = 1.2 -> 1
...
(0.1)10 = (0.0 0011 0011 0011 ...)2   the block 0011 repeats forever

A computer has only a fixed number of bits, so it must cut this off. Keeping 8 bits after the point gives (0.00011001)2 = 25/256 = 0.09765625, an error of 0.00234375. This is why 0.1 + 0.2 == 0.3 is false in C, Java, Python and JavaScript, as the program later in this chapter shows. How real hardware stores such numbers is covered in Floating-Point Representation (IEEE 754).

When does a fraction terminate? A fraction p/q (in lowest terms) has a finite representation in base r if and only if every prime factor of q is also a prime factor of r. For base 2, q must be a power of 2. So 0.6875 = 11/16 terminates, but 0.1 = 1/10 does not (10 has the factor 5). The same rule explains why 1/3 is 0.333... in decimal but exactly (0.1)3 in base 3.


Binary, Octal and Hex: The Grouping Shortcut

Since 8 = 23 and 16 = 24, every octal digit corresponds to exactly 3 bits and every hex digit to exactly 4 bits. So no arithmetic is needed, just grouping.

Binary to octal/hex: starting at the binary point, group bits in 3s (octal) or 4s (hex), going left for the integer part and right for the fraction. Pad with zeros at the outer ends, then replace each group by its digit.

Example 9. (10110101.1101)2 to hex and octal:

Hex   :  1011 0101 . 1101
            B    5  .   D           => (B5.D)16

Octal : 010 110 101 . 110 100       (pad: one 0 on the left, two 0s on the right)
          2   6   5 .   6   4       => (265.64)8

Notice the padding direction: the fraction 1101 becomes 110 100, not 001 101. Zeros added to the right of a fraction do not change its value; zeros added to the left would.

Example 10. Octal to hex, (725)8: go through binary.

7   2   5
111 010 101           => 111010101
regroup in 4s from the right: 1 1101 0101 => 0001 1101 0101
                                              1    D    5
(725)8 = (1D5)16      (both equal 469 in decimal)

This is why programmers love hex: a 32-bit value like 0xDEADBEEF is 8 easy-to-read digits, and each one maps straight back to 4 bits.


Converting Between Two Non-Decimal Bases

For bases that are not related by powers (such as 3 and 5), use decimal as a bridge: base r → decimal → base s.

Example 11. (212)3 to base 5. First (212)3 = 23. Then 23 ÷ 5 = 4 r 3; 4 ÷ 5 = 0 r 4. So (212)3 = (43)5. Check: 4 × 5 + 3 = 23.

When both bases are powers of 2 (binary, octal, hex, base 4, base 32), go through binary instead; it is faster and less error-prone.


How Many Digits Are Needed?

  • With n bits we can represent 2n different values: the unsigned integers 0 to 2n - 1. For example, 8 bits give 0 to 255 and 16 bits give 0 to 65535.

  • To represent a positive integer N we need ⌊log2 N⌋ + 1 bits. Example: 1000 lies between 29 = 512 and 210 = 1024, so it needs 10 bits.

  • In general, n digits of base r can represent rn values, from 0 to rn - 1.

  • A 32-bit value needs 32 / 4 = 8 hex digits; the largest is 0xFFFFFFFF = 232 - 1.


Number Systems in Code

Here is a C program that prints a number in several bases, parses strings written in other bases with strtol, and shows the 0.1 problem in action:

#include <stdio.h>
#include <stdlib.h>

/* print the lowest 'bits' bits of x, most significant first */
void print_binary(unsigned int x, int bits) {
    for (int i = bits - 1; i >= 0; i--)
        putchar(((x >> i) & 1) ? '1' : '0');
    putchar('\n');
}

int main(void) {
    unsigned int n = 156;
    printf("decimal : %u\n", n);
    printf("octal   : %o\n", n);
    printf("hex     : %X\n", n);
    printf("binary  : ");
    print_binary(n, 8);

    /* strtol converts a string written in any base 2..36 */
    printf("\"10011100\" base 2  = %ld\n", strtol("10011100", NULL, 2));
    printf("\"725\"      base 8  = %ld\n", strtol("725", NULL, 8));
    printf("\"3A7\"      base 16 = %ld\n", strtol("3A7", NULL, 16));
    printf("\"212\"      base 3  = %ld\n", strtol("212", NULL, 3));

    /* 0.1 has no exact binary form */
    printf("0.1 stored as double = %.20f\n", 0.1);
    printf("0.1 + 0.2 == 0.3 ? %s\n", (0.1 + 0.2 == 0.3) ? "yes" : "no");
    return 0;
}

Output (GCC on x86-64 Linux):

decimal : 156
octal   : 234
hex     : 9C
binary  : 10011100
"10011100" base 2  = 156
"725"      base 8  = 469
"3A7"      base 16 = 935
"212"      base 3  = 23
0.1 stored as double = 0.10000000000000000555
0.1 + 0.2 == 0.3 ? no

The print_binary function is the repeated-division idea in disguise: (x >> i) & 1 extracts bit i, which is the remainder you would get after dividing by 2 a total of i times. In Python, bin(156), oct(156), hex(156) and int("3A7", 16) do the same jobs.


Solved Problems: Unknown Base (GATE Favourite)

Problem 1

(123)5 = (x8)y, where x and y are unknown positive integers. How many solutions (x, y) are possible?

Left side : 1 x 25 + 2 x 5 + 3 = 38
Right side: x . y + 8
So x . y = 30.

Constraints: the digit 8 must be valid in base y  =>  y >= 9
             the digit x must be valid in base y  =>  x <= y - 1, and x >= 1
Factor pairs of 30 with y >= 9: (x, y) = (3, 10), (2, 15), (1, 30)
All three satisfy x < y.

Answer: 3 solutions. The step most students miss is the digit constraint y ≥ 9.

Problem 2

Find the base r such that √(224)r = (13)r.

(224)r = 2r^2 + 2r + 4         (13)r = r + 3
Square both sides: 2r^2 + 2r + 4 = (r + 3)^2 = r^2 + 6r + 9
                   r^2 - 4r - 5 = 0
                   (r - 5)(r + 1) = 0   =>  r = 5   (a base cannot be negative)
Check digit validity: the largest digit used is 4 < 5. OK.

Answer: r = 5. Check: (224)5 = 64 and (13)5 = 8.

Problem 3

In which base b is (111)b = (31)10?

b2 + b + 1 = 31 → b2 + b - 30 = 0 → (b + 6)(b - 5) = 0 → b = 5.

Problem 4

How many 1s are in the binary representation of 3 × 4096 + 15 × 256 + 5 × 16 + 3?

Recognise the powers of 16: 4096 = 163, 256 = 162. So the number is (3F53)16 = 0011 1111 0101 0011. Counting 1s per hex digit: 2 + 4 + 2 + 2 = 10. No decimal arithmetic needed.


Common Mistakes Students Make

  • Reading remainders in the wrong order. For the integer part, the first remainder is the least significant digit; read bottom to top. For the fraction, the first integer part is the most significant digit; read top to bottom.

  • Converting the whole number with one method. Integer and fractional parts need different methods; do them separately and join with the point.

  • Grouping fractional bits from the wrong end. Always group outward from the radix point, padding zeros at the far right of the fraction.

  • Forgetting digit-validity constraints in unknown-base problems (a digit d needs base ≥ d + 1).

  • Assuming every decimal fraction has an exact binary form. Only fractions whose denominator is a power of 2 do.

  • Writing 017 in C and expecting seventeen. A leading 0 makes it octal: 017 is 15.


GATE / Interview Questions

1. Convert (2AF)16 to decimal and octal.

Decimal: 2 × 256 + 10 × 16 + 15 = 687. Octal via binary: 0010 1010 1111 → regroup in 3s: 001 010 101 111 → (1257)8. Check: 512 + 128 + 40 + 7 = 687.

2. Convert (47.8125)10 to hexadecimal.

47 ÷ 16 = 2 r 15, so the integer part is 2F. 0.8125 × 16 = 13.0, so the fraction is D. Answer: (2F.D)16.

3. Is (0.6)10 exactly representable in binary? Write its first 8 bits.

No: 0.6 = 3/5 and 5 is not a power of 2. Repeated multiplication gives 0.1001 1001 ..., so the first 8 bits are 0.10011001, with 1001 repeating forever.

4. What is the largest unsigned number that fits in 12 bits? How many hex digits is that?

212 - 1 = 4095 = (FFF)16, which is 3 hex digits (12 / 4).

5. Why do programmers use hexadecimal instead of octal for memory addresses and bytes?

Bytes and words are multiples of 4 bits, so each byte is exactly two hex digits and a 32-bit word is exactly eight. Octal digits are 3 bits, which do not divide 8, 16, 32 or 64 evenly, so byte boundaries do not line up.

6. Find the decimal value of (1001.0101)2.

Integer: 8 + 1 = 9. Fraction: 1/4 + 1/16 = 0.3125. Answer: 9.3125.


Summary

  • In base r, each digit is multiplied by a power of r according to its position. Computers use base 2; humans use base 16 (and sometimes 8) as shorthand.

  • Base r → decimal: sum of digit × weight (or Horner's method).

  • Decimal → base r: integer part by repeated division (remainders read bottom-up), fraction by repeated multiplication (integer parts read top-down).

  • A fraction terminates in base r only if its denominator's prime factors all divide r; (0.1)10 is a repeating binary fraction.

  • Binary ↔ octal/hex: group bits in 3s or 4s outward from the radix point. Use binary as the bridge between octal and hex, and decimal as the bridge between unrelated bases.

  • n bits represent 2n values (0 to 2n - 1); N needs ⌊log2 N⌋ + 1 bits.

So far every number has been positive. Real programs also need negative numbers, and there are several ways to encode the sign in bits. That is the subject of the next chapter, Signed Numbers: Sign-Magnitude, 1's & 2's Complement.