Encoding Basics II

Conversion

Polynomial Expansion and Long Division

We have already seen how a base-2 number can be written into its base-10 form by this polynomial expansion:

101111.101*{(2)} = 1 * 2^{5} + 0 * 2^{4} + 1 * 2^{3} + 1 * 2^{2} + 1 * 2^{1} + 1 * 2^{0} + 1 * 2^{-1} + 0 * 2^{-2} + 1 * 2^{-3} = 47.625*{(10)}

This conversion is done by addition and multiplication - hence, we can imagine that its reverse process is done by subtraction and division. To convert a base-10 number into base-2, we do a long division:

Operation	Quotient	Reminder
(the original base-10 number)	47
÷2	23	1
÷2	11	1
÷2	5	1
÷2	2	1
÷2	1	0
÷2	0	1

What we do is to take out the reminder and divide the quotient by 2 again, until the original number becomes 0. The sequence of reminder in the reverse order of occurrence is the binary representation of the original base-number (47*{(10)}=101111*{(2)}).

For decimal places, we divide not by 2 but by 1/2 (or, multiply by 2). Each time, we takes out the integer part and multiply the decimal part by 2 again, until the decimal part became 0. The sequence of integer part number in the occurrence order (not reversed!) is the desired binary representation.

Operation	Decimal Part	Integer Part
(the original base-10 number)	0.625
×2	0.25	1
×2	0.5	0
×2	0	1

Hence, 0.625*{(10)}=0.101*{(2)}; overall, 47.625*{(10)}=101111.101*{(2)}.

Think about this for a second - although this division process looks strange, the polynomial expansion and the long division are really just reverse process of each other. The two process can be easily extended to numeral systems of other bases - simply replace 2 and 10 with other base values.

1F*{(16)} = 1*{(8)} _ 20*{(8)}^{1} + 17*{(8)} _ 20*{(8)}^{0} = 37*{(8)}

There are some useful heuristics:

base-2 and base-8: From lower to higher digits, every 3 base-2 digits correspond to 1 base-8 digit. Thus, 10010110110001010101 = (0)10/010/110/110/001/010/101 = 2266125. We just need to remember what 0 - 7 in octal are in binary.
base-2 and base-16: Similarly, from lower to higher digits, every 4 base-2 digits correspond to 1 base-8 digit.
base-8 and base-16: use base-2 as an intermediate base.
Know true value of small base-2 numbers at a mere glance: remember 2’s exponents first: 0001 = 1 0010 = 2 0100 = 4 1000 = 8 And thus you can know 1001 is 9 at a mere glance by mentally thinking about 1 + 8.

The Infinite Case

What if we want 0.626*{(10)} instead of 0.625*{(10)} to be written into binary form?

Operation	Decimal Part	Integer Part
(the original base-10 number)	0.626
×2	0.252	1
×2	0.504	0
×2	0.008	1
×2	0.016	0
×2	0.032	1
×2	0.064	0
×2	0.128	0
×2	0.256	0
×2	0.512	0
×2	0.024	1
×2	0.048	0
×2	0.096	0
×2	0.192	0
×2	0.384	0
×2	0.768	0
×2	0.436	1

…

This goes on and on, seemingly the decimal part will never gets to 0. Let’s try 0.1_{(10)} this time:

Operation	Decimal Part	Integer Part
(the original base-10 number)	0.1
×2	0.2	0
×2	0.4	0
×2	0.8	0
×2	0.6	1
×2	0.2	1
×2	0.4	0

…

We are back to 0.2 - 0.4 loop in its decimal part and the cycle will repeat indefinitely; that is, 0.1*{(10)} = 0.0001100110011…*{(2)}.

In fact, 0.625*{(10)} is really a special case. Most of the base-10 decimal numbers cannot be written into a finite binary form accurately. In practice, we usually take the first few digits only and write 0.1*{(10)} \approx 0.000110011001100110011*{(2)} - but if we convert this binary number back to base-10 decimals, we get 0.000110011001100110011*{(2)} = 0.099999904632568359375*{(10)} which is not exactly 0.1*{(10)} (This conversion is done by this website).

This causes a problem in computers as they uses binary numeral system. Read more about the famous computer science problem of 0.1 + 0.2 != 0.3 here.

Basic Operation

Four Basic Arithmetic Operations

How to perform addition, multiplication etc. on binary numbers? We of course can convert them into base-10, perform the operations with our usual method, and convert them back, but the easier method is just perform the operations the directly on binary numbers.

We just need to know that in binary, 0+0=0, 0+1=1, 1+1=10, 0 _ 0=0, 0_ 1=0, 1*1=1, and use the same rule for arithmetic operations as in base-10: in addition add bit by bit and for exceeding digits we carry forward to the next higher bit; in subtraction we subtract bit by bit and for insufficient minuend digit we borrow from the next higher bit; in multiplication we essentially just do a more complex addition; in division we just use the same long division procedure.

The only thing to take note is that if the binary dividend has decimal places, remove it by repeatedly multiplying the dividend and the divisor by 2. For example, convert 10.11 ÷ 1.1 to 101.1 ÷ 11. The quotient will be the same for both but to divide the resultant reminder by 2.

Bit operation

As suggested by its name, bit operation perform bit by bit. The result of one bit does not affect other bits - so, there is no carry or borrow.

Here is a table for common bit operations:

Bit Operations	Description	Example
AND (&)	The result bit is 1 only if the two bits that take the AND operation are 1	1 & 1 = 1; 101 & 011 = 001
OR (\|)	The result bit is 1 if at least of the two bits that take the OR operation is 1	1 \| 0 = 1; 101 \| 001 = 101
NOT (~)	The result is 1 if the original bit is 0, and vice versa	~1 = 0; ~111 = 000
XOR (^)	The result bit is 1 if one, and only one, of the two bits that take the OR operation is 1	1 ^ 1 = 0; 1 ^ 0 = 1; 110 ^ 100 = 010
Left Shift (<<)	Shift all bits to a higher position by the specified distance; discard the exceeding bits and fill in the undefined bits by 0.	10111 << 2 = 11100
Right Shift (>>)	Shift all bits to a lower position by the specified distance; discard the exceeding bits and fill in the undefined bits by 0.	10111 >> 3 = 00010

Take note:

Bit operations are only defined on binary numbers. Performing bit operations on base-10 number in programming languages are actually performing bit operation on their respective equivalent binary representations (e.g., 14 & 58 = 10 because in binary, 0000 1110 & 0011 1010 = 0000 1010).
Take note! Different programming languages have different implementation of the shift operation in terms of taking care of the exceeding and the undefined bits.
Try evaluate ~5 in most programming languages will give you -6, a negative number; this is -5 in base-10 is represented by 0000 0101 and -6 is 1111 1010 in computer - wait- should not 1111 1010 represent 250 in base-2? Well, yes and no. In the next post we will talk about it.
Left Shift and Right Shift on binary numbers essentially multiply / divide the original number by 2 (without remainder), if we ignore the discards.

Why bother doing bit operations? In computer architecture, what is really happening are bit operations (which are easily achieved by electronic circuit; in fact, every bit operation corresponds to a logic gate) instead of the four basic arithmetic operations. Addition of one-bit binary number, for example, can be made possible by an AND operation and an XOR operation, and more complex addition and subtraction behaviors originates from that set-up.

Conclusion

We talked about the basic conversions and operations related to binary numbers. This lays the foundation for our next post topic - how numerical values are represented in computers.