CareerCup

Odd powers of 3 means multiplying by 9. Hence 1001(base2). Thus we can Shift left 3 positions and add the number.

Num = (Num<<3) + Num

This will reduce the overhead of multiplication of a huge number by 9.

gawk 'BEGIN {
  No=3; 
  power=1; 
  print "1 " No;
} { 
  No = lshift(No,3) + No ;
  power += 2;
  print power " " No;
  }'

That is right shift what you are talking about.

100(base 2) >> 1 = 10(base 2)
i.e. when 4 is right shifted by 1 place it becomes half.

Thus if you are doing a left shift it will become double.