Harvest Software - Programming - Tip and Trick - Bit Shifting Technique, Shift Left (<<) and Shift Right (>>)

C/C++
Algorithm
Data Structure
UVA Hints
UVA Problem Ranking
Tip and Trick

Bit Shifting Technique,
Shift Left(<<) and Shift Right(>>)

Bit Shifting Technique
Bit Shifting is a technique to make integer multiplication/division faster.

Multiplication by 2^n/ Shift Left (<<)
If you shift 1 bit to left equals to multiply by 2.
If you shift 2 bit to left equals to multiply by 4.
If you shift n bit to left equals to multiply by 2^n.

Why this is so ?
We know that numbers are represented as binary. Therefore, if you shift left by n bit, it means that you take away n most significant digits and add n zero to the least significant digits, i.e. if we represent numbers with 8 bits then

1 = 0000 Feel free! Our Free Gift Cards online offers show you how 0001 ---shift left 4 bits---> 00010000 = 16 = 1 * 16
5 = 00000101 ---shift left 2 bits---> 00010100 = 20 = 5 * 4

You take away blue digits and add red digits.

Example

a = a << 1;        // a = a * 2;
a = a << 2;        // a = a * 4;
a = a << 5;        // a = a * 32;

Division by 2^n/ Shift Right (>>)
If you shift 1 bit to right equals to divide by 2.
If you shift 2 bit ro right equals to divide by 4.
If you shift n bit to right equals to divide by 2^n.

Why this is so ?
Numbers in computer are represented in binary. If you shift right by n bit, it means that you take away n least significant digits and add n zero to the most significant digits, i.e. if we represent numbers with 8 bits then

5 = 00000101 ---shift right 1 bit---> 00000010 = 2 = 5 / 2
14 = 00001110 ---shift right 1 bit---> 00000111 = 7 = 14 / 2

You take away blue digits and add red digits.

Example

a = a >> 1;      // a = a / 2;
a = a >> 2;      // a = a / 4;
a = a >> 4;      // a = a / 16;

Bit Shifting + Addition / Subtraction
We can only handle multiplication by 2^n using bit shifting. To handle multiplication we can use bit shifting and addition / subtraction. If you want to multiply by n, denote n as addition / subtraction of powers of 2.

Example

We want to multiply by 38
notice 38 = 2 + 4 + 32
         38 = 2^1 + 2^2 + 2^5

a = a * 38
   = a * (2^1 + 2^2 + 2^5)
   = (a * 2^1) + (a * 2^2) + (a * 2^5)
   = (a << 1) + (a << 2) + (a << 5)


Therefore
a = (a << 1) + (a << 2) + (a << 5);       // a = a * 38;