How can we find the next power of 2?

Approach 1:we can use the knowledge of binary numbers.A well known property of numbers that are a power of 2 is that in binary representation they are represented by a single set bit , followed by some zeros.So if we are given a number , if we can determine , the leftmost bit that is set ( let that be in position x ) , then a 1 followed by x zeros is the required number .For ex :Number = 103 ( binary equivalent : 1100111 )Now counting from right to left , we find out that 7th bit is the last one that is set .So the number 1 followed by 7 zeros … i.e. 10000000 = 128 is the required solution .Code:int nextPower_2 ( unsigned int x )

{

int counter = 0 ;

while ( x > 0 )

{

count ++ ;

x = x >> 1 ;

}

return (1 << counter) ;

}Approach 2:Another much easier approach exists to solve the above problem:Start with some variable and initialize it with value 1.Compare the variable with given number.If variable is smaller than the number, do left shift.Do the above step, until the variable becomes larger than the given number.Code:int nextPower_2 ( unsigned int x )

{

int value = 1 ;

while ( value <= x)

{

value = value << 1 ;

}

return value ;

}Approach 3:Use of the functions implemented in Math library.Find log2X , this would give us the power P , such that 2 ^ P = X.Use the ceil function to get thenext number.Then, perform2 ^ next numberand that’s the required result.Code:int nextPower_2 ( unsigned int x)

{

double nextnum = ceil ( log2 x) ;

double result = pow (2.0 , nextnum) ;

return int ( result ) ;

}

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *