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 b 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 b 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}

x_{b} \mod b^{n} equates to keeping the n least significant digits:
121_{10} \mod 10 = 1_{10}
111_{2} \mod 2^{2} = 11_{2}
120_{3} \mod 3 = 0_{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}-1], the subinterval [0, b^{n}/2-1] corresponds to positive numbers and the subinterval [b^{n}/2, b^{n}-1] to negative numbers. Any x \in [b^{n}/2, b^{n}-1] 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}-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}-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}-1], 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

For the particular case of the binary system:

  • [-2^{n-1}, 2^{n-1}-1] in two’s complement
  • [-2^{n-1}-1, 2^{n-1}-1] in ones’ complement

Integer arithmetic

Let’s consider now how to add/subtract numbers in a given range. In general, given the range of unsigned numbers [0, b^{n}-1], the result x of adding up 2 numbers is in the range [0, 2b^{n}-2], that exceeds the original range. In order to avoid overflowing and keep x in the original range, it is necessary to calculate x \mod b^{n}.

For instance, with 4-bit integers, we can represent:

  • unsigned numbers in the range [0, 15]
  • signed numbers in two’s complement in the range [-8, 7]
  • signed numbers in ones’ complement in the range [-7, 7]

Unsigned integers

(10+13) \mod 16 = 7

unsigned integers

Signed integers in two’s complement

(5+5) \mod 16 = 10 \implies -6 (positive overflow)
-8-5 \implies (8+11) \mod 16 = 3 (negative overflow)

two's complement

Signed integers in ones’ complement

(5+5) \mod 16 = 10 \implies -5 (positive overflow)
-7-5 \implies (8+10) \mod 16 = 2 (negative overflow)

ones' complement

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 ones’ complement). The interpretation of the result depends on the number of bits used to represent the integer and whether it is signed or unsigned.

invert operator


unsigned integers: \sim 2 = 13
signed integers in two’s complement: \sim 2 = -3
signed integers in ones complement: \sim 2 = -2

Java examples

In Java, the byte data type is an 8-bit signed two’s complement integer. It has a minimum value of -128 and a maximum value of 127.

jshell> (byte)(-128-1)
$131 ==> 127

jshell> (byte)(127+3)
$132 ==> -126

jshell> ~127
$134 ==> -128