Intro in Binary Representations and Bit Manipulation

First of all, what is a bit (short for binary digit)? You can think of it as an atom which can be used to build information. In fact, a bit has only two unique states: zero or one. Sometimes you can find another definition like “yes/no”, “on/off” or  “true/false”. But, all this stuff boils down to the same thing.

none

To represent more meaningful information other than zero or one we need a
bunch of bits that can be grouped together. For example, eight bits are able to produce 256 (2^8) unique numbers:

11110100 = 244 or 10000100 = 132

Conversion to base 10 and vice versa

To convert a binary number to base 10 you can use a very simple method which multiplies bits in respective positions with 2 to the power of their position. For example, binary number 10000110 can be converted as follows:

10000110 = 
1 * 2^7 + 
0 * 2^6 + 
0 * 2^5 + 
0 * 2^4 + 
0 * 2^3 + 
1 * 2^2 + 
1 * 2^1 + 
0 * 2^0 = 134

A repeated division and reminder can be used to convert decimal to binary number. The method contains four steps:

  1. Divide the decimal by two.
  2. Append the reminder as the most significant bit.
  3. Go to step 1 if decimal number is greater than zero, otherwise go to 4.
  4. End.

Example:

134 / 2 = 67  reminder 0
67  / 2 = 33  reminder 1
33  / 2 = 16  reminder 1
16  / 2 = 8   reminder 0
8   / 2 = 4   reminder 0
4   / 2 = 2   reminder 0
2   / 2 = 1   reminder 0
1   / 2 = 1/2 reminder 1

Up to now we have been talking about only integer numbers. So, what can we do to convert the fractional part of the number to binary representation? The fractional part of the binary number works on the same principle as the fractional part in base 10. In base 10 all numbers followed the decimal point are multiplied by 10 to the negative power of the number’s position. For instance:

123.456 = 
1 * 10^2 +
2 * 10^1 +
3 * 10^0 +
4 * 10^-1 +
5 * 10^-2 +
6 * 10^-3

So we can use the same principle to convert 2.75 to the binary number:

10.11 = 
1 * 2^1 +
0 * 2^0 +
1 * 2^-1 +
1 * 2^-2

Bitwise Operations

Basically, it’s not good idea to use bitwise operations in routine applications because it makes code less readable and clear. But, in case if memory consumption and speed matters you can consider this as an optimization.

Another application of bitwise operations are graphics, encryption and compression.

Btw, here goes my utility class for bit manipulations: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/common/BitManipulation.java

NOT

The unary bitwise complement operator “~” inverts a bit pattern, making every “0” a “1” and every “1” a “0”. For instance:

~10101011 = 01010100
AND

The AND operator works just like multiplication and it also known as logical conjunction. It outputs 1 only if all inputs are 1.

A B Result
0 0 0
1 0 0
0 1 0
1 1 1
OR

The OR operator outputs 1 if at least one input is 1. This is why it’s also known as logical disjunction operator.

A B Result
0 0 0
1 0 1
0 1 1
1 1 1
XOR

The XOR operator or exclusive disjunction outputs 1 only if both inputs don’t match. Actually it’s the same as adding modulo 2.

A B Result
0 0 0
1 0 1
0 1 1
1 1 0

Some properties of XOR operation:

A^B = B^A
A^B^A = B
Shifting

The bitwise left shift operator moves all bits in the given number to the left and inserts 0 to vacated bit positions.

For instance, we can perform a left shift by 2 bits:

10010101 << 2 = 01010100

Shifting a number to the left by n bits has the effect of multiplying it by 2^n.

Likewise, the bitwise right shift operator moves all bits of the given number to the right.

Example,

10010101 >>> 2 = 00100101

Moving bits to the right is equivalent of dividing the number by 2^n.

In other words, bitwise shifting is an efficient way of performing multiplication or division by powers of two.

Two’s complement

Two’s complement is just a good and convenient way to represent negative numbers in base 2. If you are a Java developer you probably know that Integer values in java has 32 bits length. The leftmost bit is used for sign (in some sources it’s called the sign bit). In case the number is negative the sign bit will be equal to 1, otherwise to 0. Unfortunately we can’t simply toggle the sign bit to make a number positive or negative because in this case we will have two zero’s. One negative zero and one positive zero which is not possible in math.

To solve this problem with zero’s we can use two’s complement. For instance, let’s say we have 8 bits word and we want to represent a negative five.

The positive five in binary will look like this:

Screen Shot 2015-12-18 at 14.43.36

Please note that the left most bit is sign bit. To convert it to negative we need to do two things:

  1. Invert all bits:Screen Shot 2015-12-18 at 14.47.29
  2. Add one bit:Screen Shot 2015-12-18 at 14.48.45

That’s all. Now try to convert zero using the above algorithm and result will always be zero. Fascinating, wright?

Moreover, in case if you need to convert the negative five to positive five you can use the same algorithm.

Intro to IEEE 754

IEEE standard for floating point computations was established by the Institute of Electrical and Electronics Engineers (IEEE) in 1985.

A real number can be represented as follows:

N = a * q^n

Where a is significand, q is a base and n is an exponent.  As a result, the same number can be represented in many ways. For example, number 120:

120 = 120 * 10^0
120 = 12 * 10^1
120 = 1.2 * 10^2
...

All these representations are absolutely correct. But, to reduce the number of the representations to one a normalised notation is used. In this notation significand is always greater or equal to 1 and less than the base. In the above example the only normalised notation for 120 will be 1.2 * 10^2 because 1 <= 1.2 < 10.

Now let’s try to represent a binary number in normalised form. For instance, number 01111011 will look like 1.111011 * 2^6 and it might be represented in IEEE format in following way:

Screen Shot 2015-12-19 at 18.09.23

As you can see there are 32 bits in total. The most significant bit is reserved for sign. The sign bit is set to zero if number is positive, otherwise to 1.

Eight bits are allocated for exponent. But, it’s not that simple. Instead of using two’s complement it was decided to add 127 to the exponent and store it as unsigned number. If the stored value is greater than the bias, that means the value of the exponent is positive, if it’s lower than the bias, it’s negative, if it’s equal, it’s zero. In my example the exponent is equal to 10000101 = 01111111 + 110.

The rest of the bits are reserved for fractional part of mantissa. In other words, the integral part of the mantissa almost always (except zero) equals to 1 and we don’t need to store it.

Please note that in my post I described 32 bit IEEE 754 which is equivalent to float in Java. But, there is 64 bit IEEE 754 that is known as double in Java.

Leave a Reply