Right shift and left shift

In general dividing by 2 is equivalent to right shifting with 1. Also left shifting with 1 is equivalent to multiplication with 2.

(a)   Is a right shift equivalent to a division exactly by 2? For example shift 0x9A with 1, 2 and 3 and show what values you obtain.

(b)  Is sifthing towards right giving an number sammer or equal to the original number?

(c)  For a number 0 < n < 255, what is the number of right shifts r that make n >> r to be zero?

(d)   Please find 0x6 << n for when you shift with n = 1..8.

(e)  Is the left shift creating an integer twice as big for all n? Why?

(f)   Is 0x6 << n generate strange results for some n?  Why or why not?

Answer

a) Right shift with one unity divides EXACTLY by 2 only if the binary number ends in 0. If the binary number ends in 1, then right shift generates the truncated part of the number divided by 2.

0x9A >>1 = 154 >>1 =10011010 >>1 =01001101 = 77 (=154/2) =0x4D   therefore  division is exact

0x9A >>2 =154 >>2 =10011010 >>2 =00100110 =38 (= trunc(77/2)) = 0x26 therefore division is truncated

0x9A >>3 =154>>3 =10011010>>3 =00010011 = 19 (= 38/2) =0x13 therefore division is exact

Right shift

b) Yes it is true that right shift generates a number smaller or equal. The number is equal when one right shifts the zero number: 0 >>1 =0

c) The minimum number of right shifts necessary for the number to became 0 is equal to the number of bits of the binary representation of the given number.

for 0<n<255 n can be written as

$n= C1*2^0 +C2*2^1 +C3*2^2 +…+C8*2^7$   (thus C8..C1 are the binary representation of n)

The number of right shift is equal to the highest index of C that is nonzero.

The mathematical expression of number of shifts required N to zero the number n is

N = int(log(base 2) n)

where int is the ROUNDED integer part.

Left shift

d) 0x6 <<1 =110=6 decimal <<1 =1100 = 0xC (=2*6 decimal)

0x6 <<2 =11000 =11000=0x18 =4*6 decimal

0x6 <<3 =110000 =0x30 =8*6 decimal

0x6 << 4 =1100000 =0x60 =16*6 decimal = 96

0x6 << 5 =11000000 =0xC0=32*6 decimal = 96*2= 192

0x6 <<6 =10000000 =0x80= 128 decimal

0x6 <<7 =00000000=0x00 =0 decimal

0x6 <<8 =00000000=0x00 =0 decimal

e) The left shift generates a bigger number only if the shifted number is in the range 0<n<255 (for 6 bit representation) . Otherwise the result is less than (2^r)*n. This happens when the shifted (to the left) bits are came out of the number (they are outside of the 8 binary representation).

f) 0x6 <<n generates strange results for n= 6, 7

0x6(hex) = 00000110(binary)

For n=6 the leading bit is getting out of the 8 bits binary representation (it becomes the 9th bit in the representation), for n=7 the second bit of the number cames out and the number becomes 0

Observation

For n=8 we shift the number 0 to the left with 1 which is also 0 (0*2 =0) which is not a strange result.