Binary system

Conversion from binary to hex

Given a binary number, group its digits in groups of 4, then replace according to the below table:

11010010 \rightarrow 1101\:0010 \rightarrow D2

BinaryHex
00011
00102
00113
01004
01015
01106
01117
10008
10019
1010A
1011B
1100C
1101D
1110E
1111F

Proof

(x_{7}\,x_{6}\,x_{5}\,x_{4}\,x_{3}\,x_{2}\,x_{1}\,x_{0})_{2}

x_{7}\,2^{7} + x_{6}\,2^{6} + x_{5}\,2^{5} + x_{4}\,2^{4} + x_{3}\,2^{3} + x_{2}\,2^{2} + x_{1}\,2^{1} + x_{0}\,2^{0}

x_{7}\,2^{3}\,(2^{4})^{1} + x_{6}\,2^{2}\,(2^{4})^{1} + x_{5}\,2^{1}\,(2^{4})^{1} + x_{4}\,2^{0}\,(2^{4})^{1} + x_{3}\,2^{3}\,(2^{4})^{0} + x_{2} \,2^{2}\,(2^{4})^{0} + x_{1}\,2^{1}\,(2^{4})^{0} + x_{0}\,2^{0}\,(2^{4})^{0}

(x_{7}\,2^{3} + x_{6}\,2^{2} + x_{5}\,2^{1} + x_{4}\,2^{0})\,(2^{4})^{1} + (x_{3}\,2^{3} + x_{2}\,2^{2} + x_{1}\,2^{1} + x_{0}\,2^{0})\,(2^{4})^{0}

(x_{7}\,x_{6}\,x_{5}\,x_{4} \;\;\; x_{3}\,x_{2}\,x_{1}\,x_{0})_{16}

Conversion from binary to octal

Similarly, it’s possible to convert a binary number to octal by grouping the digits in groups of 3:

11010010 \rightarrow 11\:010\:010 \rightarrow 322

Mnemonics

For any base b, b^{n} equals 1 followed by n zeros:
10^{0}=1
10^{1}=10
10^{2}=100
2^{1}=10
2^{2}=100
3^{2}=100

b^{n}-1 equals n times the digit n-1:
10^{2}-1=99
2^{2}-1=11
3^{4}-1=2222

1 has the same representation in any base:
1_{10} = 1
1_{2} = 1

Multiplying by n equates to shifting the digits one place to the left:
120_{10} \times 10 = 1200_{10}
11_{2} \times 2 = 110_{2}
12_{3} \times 3 = 120_{3}

Integer division by n equates to shifting the digits one place to the right:
121_{10} \div 10 = 12_{10}
111_{2} \div 2 = 11_{2}
120_{3} \div 3 = 12_{3}

Numeric complements

Radix complement

Radix complement of an n-digit number y in radix b is the difference between y and b^{n}.

If y is a n-digit number, then radix complement, rc, is b^{n} - y, e.g.
rc((12)_{10}) = (88)_{10}
rc((101)_{2}) = (011)_{2}

Diminished radix complement

Diminished radix complement is radix complement minus 1, drc = rc - 1

The advantage of using drc over rc is its simplicity to calculate: just replace each digit for its corresponding drc, e.g.

    \[drc((12)_{10}) = (drc(1)drc(2))_{10} = (87)_{10} => rc((12)_{10}) = (87)_{10} + 1 = (88)_{10}\]

In a binary representation, it’s even easier as the calculation of the drc is equivalent to flipping zeros and ones:

(1)   \begin{multline*}drc((101)_{2}) = ((drc(1)drc(0)drc(1))_{2}) = (010)_{2} => \\rc((101)_{2}) = (010)_{2} + 1 = (011)_{2}\end{multline*}

Proof

    \[drc = rc - 1 = b^{n} - y -1 = (b^{n} - 1) - y\]


    \[b^{n} - 1 = (b-1) (b^{n-1} + b^{n-2} + ... + b + 1)\]


(2)   \begin{multline*}drc = (b^{n} - 1) - y = ((b-1) - y_{n-1}) b^{n-1} + ((b-1) - y_{n-2}) b^{n-2} + ... \\ + ((b-1) - y_{1}) b + ((b-1) - y_{0}) \end{multline*}


Resulting:

    \[drc = drc(y_{n-1}) b^{n-1} + drc(y_{n-2}) b^{n-2} + ... + drc(y_{1}) b + drc(y_{0})\]


In binary, the radix complement is called the two’s complement and the diminished radix complement the ones’ complement.

Negative numbers

Radix and diminished radix complements are used to represent negative numbers. Given a range of unsigned numbers [0, b^{n}), the subinterval [0, b^{n}/2) corresponds to positive numbers and the subinterval [b^{n}/2, b^{n}) to negative numbers. Any x \in [b^{n}/2, b^{n}) represents the negative value of its radix or diminished radix (depending on the convention used) complement. This way subtractions can be handled as additions without needing to deal with the sign of the negative numbers.

For instance, when using the radix complement in the interval [0, 10^{1}), the negative values are:

  • 9 = -1
  • 8 = -2
  • 7 = -3
  • 6 = -4
  • 5 = -5

and therefore, the numbers represented by the elements of [0, 10^{1}) are: [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4]

If instead we use diminished radix complement, the negative values are:

  • 9 = -0
  • 8 = -1
  • 7 = -2
  • 6 = -3
  • 5 = -4

and the numbers that can be represented are: [-4, -3, -2, -1, 0, 1, 2, 3, 4]

From the above results, it follows that given the interval of unsigned numbers [0, b^{n}), the corresponding interval of signed numbers is:

  • [-b^{n}/2, b^{n}/2-1] in radix complement
  • [-b^{n}/2-1, b^{n}/2-1] in diminished radix complement

Arithmetic with radix complement

Let’s consider now how to add/subtract the numbers in the range [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4] when using radix complement to represent negative values.

Given 3 - 2 = 3 + (-2) = 3 + 8 = 11, the result 11 is out of the range of the interval. We need to remove the overflowing digit to get the expected value 1.

In this other example 3 - 4 = 3 + (-4) = 3 + 6 = 9 = -1.

Based on the above examples, we can infer the following rules for the arithmetic of negative numbers with radix complement:

  • replace the subtrahend with its complement
  • do the sum
  • if the result overflows, remove the overflowing digit
  • otherwise, replace it with the negative of its complement

Let’s prove more formally the above rules derived intuitively:

if x \ge y,

    \[x - y = x - y + b^{n} - b^{n} = x + (b^{n} - y) - b^{n} = x + rc(y) - b^{n}\]

where x + drc(y) > b^{n} (and subtracting b^{n} is equivalent to dropping the overflowing bit).

On the other hand, if x < y, then b^{n}/2 \le x + rc(y) < b^{n} and, after re-arranging the terms, the above formula becomes:

    \[x - y = -(b^{n} - (x + (b^{n} - y)))  = - rc(x + rc(y))\]

Binary system examples

Range of signed 2-byte integers: [-128, 127] = [10000000, 01111111]

    \[5 - 1 = 5 + (-1) = 00000101 + 11111111 =  (1)00000100 = 00000100 = 4\]

    \[5 - 6 = 5 + (-6) = 00000101 + 11111010 = -rc(11111111) = - 00000001 = -1\]

Arithmetic with diminished radix complement

Let’s take the same examples from the previous section:

3 - 2 = 3 + (-2) = 3 + 7 = 10, the result 10 is out of the range of the interval. We need to remove the overflowing digit and add 1, resulting in 0 + 1 = 1.

3 - 4 = 3 + (-4) = 3 + 5 = 8, similarly to what we did in the previous section, we need to get the complement of the result to obtain the expected value -1.

Again, we can infer the following rules for the arithmetic of negative numbers with diminished radix complement:

  • replace the subtrahend with its complement
  • do the sum
  • if the result overflows, remove the overflowing digit and add 1
  • if not, replace it with the negative of its complement

Here’s the demonstration:

if x > y,

    \[x - y = x - y + b^{n} - b^{n} + 1 - 1 = x + (b^{n} - 1 - y) + 1 - b^{n} = x + drc(y) + 1 - b^{n}\]

where x + drc(y) > b^{n} (and subtracting b^{n} is equivalent to dropping the overflowing bit).

If x < y, then b^{n}/2 < x + drc(y) < b^{n} and the above formula, after re-arranging the terms, becomes:

    \[x - y = -(b^{n} - 1 - (x + (b^{n} - 1 - y))) = -drc(x + drc(y)) \]

Binary system examples

Range of signed 2-byte integers: [-127, 127] = [10000000, 01111111]

    \[5 - 1 = 5 + (-1) = 00000101 + 11111110 =  (1)00000011 + 1 = 00000100 = 4\]

    \[5 - 6 = 5 + (-6) = 00000101 + 11111001 = -drc(11111110) = - 00000001 = -1\]

Invert operator

The unary \sim (invert) operator yields the bitwise inversion of its integer argument (in the binary system that is equivalent to calculate the diminished radix complement).
However, the number represented by the result is not well defined as it depends on the number of bits used to represent the original value:

5 = 101
\sim5 = 010 = 2

5 = 0101
\sim5 = 1010 = 10

5 = 00101
\sim5 = 11010 = 26

But if we calculate the radix complement of \sim5:

rc(\sim 101) = 2^{3} - 2 = 6
rc(\sim 0101) = 2^{4} - 10 = 6
rc(\sim 00101) = 2^{5} - 26 = 6

the resulting value is the same, irrespective of the number of bits. In other words, rc(\sim5) is the radix complement of 6 and therefore can be considered to represent -6.

Based on the above discussion, we can define \sim x as:

    \[\sim x = -rc(drc(x)) = -(b^{n} - (b^{n} - 1 - x)) = - (x + 1)\]