Number systems and conversion

Why it exists

A digital circuit can only tell two voltage levels apart, so every number inside a computer is written with the two digits 0 and 1. People and programs, however, write numbers in decimal, and hardware designers and debuggers write them in octal or hexadecimal because those are short ways of writing long bit strings. GATE questions in this area are almost all conversions: write this number in another base, find the unknown base from an equation, or say how many bits or digits are needed. All of them follow from one idea, positional notation, and a handful of mechanical procedures.

Everything later in this subject (signed numbers, floating point, adders, memory addressing in COA) assumes that you can move between these bases without thinking.

Prerequisites

None. This is a starting point.

Nothing from earlier pages. You need to be comfortable with exponents and with integer division with remainder.

Precise definitions

Positional number system. A base (radix) $b \ge 2$ uses the digits $0, 1, \dots, b-1$ (for $b > 10$ the letters A, B, C, ... stand for 10, 11, 12, ...). The digit string $d_{k}\,d_{k-1}\dots d_1\,d_0\,.\,d_{-1}\,d_{-2}\dots d_{-m}$ has the value

$\sum_{i=-m}^{k} d_i\, b^{\,i}.$

The position of a digit gives its weight, a power of $b$. The point separates the non-negative powers from the negative ones.

The four bases you must know.

Bit, nibble, byte. A bit is one binary digit. A nibble is 4 bits (one hexadecimal digit). A byte is 8 bits (two hexadecimal digits).

Conversion of the integer part from decimal to base $b$ (repeated division). Divide the number by $b$, record the remainder, replace the number by the quotient, and repeat until the quotient is 0. The remainders, read from the last to the first, are the digits from the most significant to the least significant.

Conversion of the fractional part from decimal to base $b$ (repeated multiplication). Multiply the fraction by $b$. The integer part of the product is the next digit after the point (the first digit produced is the most significant). Keep the fractional part and repeat, until the fractional part is 0 or you have the number of digits you want. Read the digits in the order they are produced.

Conversion to decimal. Add digit times weight for every position (this is the formula above).

Binary, octal and hexadecimal are interchangeable by grouping. Since $8 = 2^3$ and $16 = 2^4$, one octal digit is exactly three bits and one hexadecimal digit is exactly four. Group the bits in threes (octal) or fours (hexadecimal) starting at the binary point and moving outwards, padding the outer ends with zeros: the integer part is padded on the left, the fractional part on the right. Then translate each group. Going the other way, replace each digit by its 3-bit or 4-bit group. No arithmetic is needed, and octal to hexadecimal goes through binary.

When does a fraction stop? A fraction $p/q$ in lowest terms has a finite expansion in base $b$ if and only if every prime factor of $q$ is also a prime factor of $b$. Otherwise the digits repeat forever. For base 2 that means $q$ must be a power of 2. So $0.5$, $0.375 = 3/8$ and $0.6875 = 11/16$ are finite in binary, while $0.1 = 1/10$, $0.2$ and $1/3$ are not. In base 10, $q$ may only have the factors 2 and 5.

How many digits does a number need? The positive integer $n$ has $\lfloor \log_b n \rfloor + 1$ digits in base $b$. To distinguish $N$ different values with bits you need $\lceil \log_2 N \rceil$ bits. In particular $n$ bits give $2^n$ patterns, the largest unsigned value is $2^n - 1$, and an $n$-digit string in base $b$ gives $b^n$ values.

Arithmetic in a base. The school rules apply in any base: add digit by digit, carry when the column sum reaches $b$. In binary the column rules are $0+0=0$, $0+1=1$, $1+1=10$ (write 0, carry 1) and $1+1+1=11$ (write 1, carry 1).

How it works

The animation walks through the five procedures on real numbers. Every line is computed by exact integer and fraction arithmetic by a script (not typed by hand), and the tests decode each row again independently. Use the step button and read the remainders or the doubled values as they appear.

156 / 2 = 78 remainder 0
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

Three habits make conversions fast and safe:

1. Memorise the powers of two from $2^0$ to $2^{16}$ (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536). Most decimal to binary conversions are then a subtraction game: write the largest power that fits, subtract, continue.
2. Group, do not divide, when both bases are powers of two.
3. Check by converting back, or at least by a parity test: a binary integer is odd exactly when its last bit is 1, and a hexadecimal integer is odd exactly when its last digit is odd.

Worked examples

#include <stdio.h>
 
int main(void) {
    unsigned n = 156;
    printf("octal %o hex %X\n", n, n);
    printf("binary ");
    for (int i = 7; i >= 0; i--) putchar(((n >> i) & 1) ? '1' : '0');
    printf("\n");
    return 0;
}

octal 234 hex 9C
binary 10011100

#include <stdio.h>
 
int main(void) {
    double x = 0.6875;
    printf("0.");
    while (x != 0.0) {
        x *= 2;
        if (x >= 1.0) { putchar('1'); x -= 1.0; } else putchar('0');
    }
    printf("\n");
    double y = 0.1;
    printf("0.");
    for (int i = 0; i < 24; i++) {
        y *= 2;
        if (y >= 1.0) { putchar('1'); y -= 1.0; } else putchar('0');
    }
    printf("...\n");
    return 0;
}

0.1011
0.000110011001100110011001...

  1011.101
+  110.110

#include <stdio.h>
#include <stdlib.h>
 
int main(void) {
    printf("%ld %ld %ld\n", strtol("2A3", NULL, 16), strtol("3763", NULL, 8), strtol("10011100", NULL, 2));
    printf("%X %o\n", 0x7F3, 0x7F3);
    int bits = 0;
    unsigned long long v = 999999ULL;
    while (v) { bits++; v >>= 1; }
    printf("%d\n", bits);
    return 0;
}

675 2035 156
7F3 3763
20

Cheat box

Traps and GATE patterns

Other things examiners twist:

• Questions that mix a fraction and an integer part in one conversion. Convert the two parts separately and join them at the point.
• Subtraction or addition performed directly in octal or hexadecimal. Carry when the column reaches the base, not 10.
• The number of distinct values in a string of $n$ digits is $b^n$ (leading zeros count), while the number of $n$-digit numbers without a leading zero is $b^n - b^{n-1}$.

Connections

Fixed-length strings of bits are interpreted as negative numbers in signed number representation and as numbers with a fractional part in IEEE 754. The same ideas explain the output of printf("%o %X") and the widths of types in C types and operators. Binary codes that are not positional, such as BCD and Gray code, are treated in codes.

PYQs

Which of the following is/are EQUAL to 224 in
radix-5 (i.e., base-5) notation?

A particular number is written as 132 in radix-4
representation. The same number in radix-5
representation is __________.

If the numerical value of a 2-byte unsigned integer on
a little-endian computer is 255 more than that on a
big-endian computer, which of the following choices
represent(s) the unsigned integer on a little-endian
computer?

If x and y are two decimal digits and

(0.1101)2=(0.8xy5)10, the decimal value of x+y is?

Let the representation of a number in base 3 be 210.
What is the hexadecimal representation of the
number?

Two numbers are chosen independently and
uniformly at random from the set {1, 2, ..., 13}. The
probability (rounded off to 3 decimal places) that
their 4-bit (unsigned) binary representations have
the same most significant bit is ______.

The representation of the value of a 16-bit unsigned
integer X in the hexadecimal number system is
BCA9. The representation of the value of X in octal
number system is

Consider the equation (43)x = (y3)8
where x and y are unknown. The number of possible
solutions is ________

Consider the equation (123)5 = (x8)y with x and y
as unknown. The number of possible solutions is
______.

The base (or radix) of the number system such that
the following equation holds

312
20 = 13.1 is ____________

DIGITAL LOGIC

(1217)8 is equivalent to

Let r denote the number system radix. The only
value(s) of r that satisfy the equation

√121r = 11r is/are

The hexadecimal representation of (657)8 is:

Self-check

Revision card

References