Home > Net >  Please suggest an optimization in this code without using pow() function ? This question was asked t
Please suggest an optimization in this code without using pow() function ? This question was asked t

Time:06-14

  1. when I give input as num=1, output should be 8

  2. when I give input as num=2, output should be 16

  3. when I give input as num=3, output should be 32

  4. when I give input as num=4, output should be 64 and so on Here is the code

     #include <stdio.h>
     #include <stdlib.h> 
    
    
     int main()
     {
         int num,b;
         scanf("%d",&num);
         num=num 2;
         b=pow(2,num);
         printf("%d",b);
         return 0;
     }
    

I tried writing my own pow() function, but interviewer did not accept the solution.

CodePudding user response:

You can use bit shifting.

Firstly, let's idenitfy the pattern (which you already have, it seems): for any given num, we should print out 2 to the power of num 2.

Consider that we are working in base 2. (Most) Computers nowadays store numbers in binary. Consider the binary representation of 1, 2, 4, 8 and 16.

1 = 0b00001
2 = 0b00010
4 = 0b00100
8 = 0b01000
16 = 0b10000

Notice that for each power of 2, there is only one bit set to 1. For increasing powers of 2, this bit moves to the left. With C, we can achieve getting something like this with the left shift operator in O(1), computationally faster than the O(log num) or O(num) implementations of pow as a library function and your own implementation of pow.

Instead of b=pow(2, num), you can try b=1<<num instead. This way, when num = 3 for example, the bit will be shifted three times to get 0b01000 = 8.

CodePudding user response:

A straightforward approach can look for example the following way using the bitwise left shift operator.

Pay attention to that you should define the result when the value of num (that should be of unsigned integer type) is equal to 0.

#include <stdio.h>

unsigned long long f( unsigned int n )
{
    return n == 0 ? 1 : 8llu << ( n - 1 );    
}

int main( void )
{
    const unsigned int N = 5;

    for ( unsigned int i = 0; i < N; i   )
    {
        printf( "%llu ", f( i ) );
    }

    putchar( '\n' );
}

The program output is

1 8 16 32 64 
  • Related