Binary system - Tech Ideas that Click

Conversions

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$

Binary	Hex
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	A
1011	B
1100	C
1101	D
1110	E
1111	F

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$

Powers of 2 in hex

Powers of 2	Hex
2^0	1
2^1	2
2^2	4
2^3	8
2^4	10
2^5	20
2^6	40
2^7	80
2^8	100
2^9	200
2^10	400
2^11	800
2^12	1000
2^13	2000
2^14	4000

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 $b-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}$
$1011_{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)

Bitwise operators

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.

unsigned integers: $\sim 2 = 13$
signed integers in two’s complement: $\sim 2 = -3 => -x = \sim x + 1 => x = - (-x) = \sim (\sim x + 1) + 1$
signed integers in ones complement: $\sim 2 = -2 => -x = \sim x$

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

Xor operator

The $xor$ operator, $^\wedge$ , is an exclusive or and verifies the following identities:

$x ^\wedge x = 0$
$x ^\wedge 0 = x$

Therefore:

$x ^\wedge x ^\wedge ...^{(n)}...^\wedge x =\begin{cases}0, & \text{if n is even} \\x, & \text{if n is odd}\end{cases}$

This property, plus the fact that $xor$ is associative, allows to solve the following problem with a single loop:

Given an array of integers, find the one that appears an odd number of times.
There will always be only one integer that appears an odd number of times

from operator import xor
from functools import reduce

def find(seq):    
    return reduce(xor, seq)

$xor$ also verifies these identities (provided 2’s complement is used to represent negative integers):

$x ^\wedge (\sim x) = -1$
$x ^\wedge (-1) = \sim x$