Next Power of 2 | GeeksforGeeks

Next Power of 2 | GeeksforGeeks
Write a function that, for a given no n, finds a number p which is greater than or equal to n and is a power of 2.

Method 4(Customized and Fast)

1. Subtract n by 1
   n = n -1
2. Set all bits after the leftmost set bit.
/* Below solution works only if integer is 32 bits */
     n = n | (n >> 1);
     n = n | (n >> 2);
     n = n | (n >> 4);
     n = n | (n >> 8);
     n = n | (n >> 16);
3. Return n + 1

unsigned int nextPowerOf2(unsigned int n)

{

    n--;

    n |= n >> 1;

    n |= n >> 2;

    n |= n >> 4;

    n |= n >> 8;

    n |= n >> 16;

    n++;

    return n;

}

Method 2 (By getting the position of only set bit in result )

/* If n is a power of 2 then return n */
1  If (n & !(n&(n-1))) then return n 
2  Else keep right shifting n until it becomes zero 
     and count no of shifts
     a. Initialize: count = 0
      b. While n ! = 0
            n = n>>1
            count = count + 1
/* Now count has the position of set bit in result */
3  Return (1 << count)  

unsigned int nextPowerOf2(unsigned int n)

{

  unsigned count = 0;

  /* First n in the below condition is for the case where n is 0*/

  if (n && !(n&(n-1)))

    return n;

  while( n != 0)

  {

    n  >>= 1;

    count += 1;

  }

  return 1<<count;

}

Method 3(Shift result one by one)
This method is a variation of method 2 where instead of getting count, we shift the result one by one in a loop.

unsigned int nextPowerOf2(unsigned int n)

{

    unsigned int p = 1;

    if (n && !(n & (n - 1))) // java code: n != 0 && ((n & (n - 1)) == 0)

        return n;

    while (p < n) {

        p <<= 1;

    }

    return p;

}

Read full article from Next Power of 2 | GeeksforGeeks