Round to the nearest power of two

Question

Is there a one line expression (possibly boolean) to get the nearest 2^n number for a given integer?

Example: 5,6,7 must be 8.

Answer 1

Round up to the next higher power of two: see bit-twiddling hacks.

In C:

unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

Answer 2

I think you mean next nearest 2^n number. You can do a log on the mode 2 and then determine next integer value out of it.

For java, it can be done like:

Math.ceil(Math.log(x)/Math.log(2))

Answer 3

Since the title of the question is "Round to the nearest power of two", I thought it would be useful to include a solution to that problem as well.

int nearestPowerOfTwo(int n)
{
    int v = n; 

    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++; // next power of 2

    int x = v >> 1; // previous power of 2

    return (v - n) > (n - x) ? x : v;
}

It basically finds both the previous and the next power of two and then returns the nearest one.

Answer 4

Your requirements are a little confused, the nearest power of 2 to 5 is 4. If what you want is the next power of 2 up from the number, then the following Mathematica expression does what you want:

2^Ceiling[Log[2, 5]] => 8

From that it should be straightforward to figure out a one-liner in most programming languages.

Answer 5

For next power of two up from a given integer x

2^(int(log(x-1,2))+1)

or alternatively (if you do not have a log function accepting a base argument

2^(int(log(x-1)/log(2))+1)

Note that this does not work for x < 2

Answer 6

This can be done by right shifting on the input number until it becomes 0 and keeping the count of shifts. This will give the position of the most significant 1 bit. Getting 2 to the power of this number will give us the next nearest power of 2.

public int NextPowerOf2(int number) {
    int pos = 0;
    
    while (number > 0) {
        pos++;
        number = number >> 1; 
    }
    return (int) Math.pow(2, pos);
}

Answer 7

For rounding up to the nearest power of 2 in Java, you can use this. Probably faster for longs than the bit-twiddling stuff mentioned in other answers.

static long roundUpToPowerOfTwo(long v) {
  long i = Long.highestOneBit(v);
  return v > i ? i << 1 : i;
}

Answer 8

Round n to the next power of 2 in one line in Python:

next_power_2 = 2 ** (n - 1).bit_length()

Answer 9

Modified for VBA. NextPowerOf2_1 doesn't seem to work. So I used loop method. Needed a shift right bitwise operator though.

Sub test()
    NextPowerOf2_1(31)
    NextPowerOf2_2(31)
    NextPowerOf2_1(32)
    NextPowerOf2_2(32)
End Sub

Sub NextPowerOf2_1(ByVal number As Long) ' Does not work
    Debug.Print 2 ^ (Int(Math.Log(number - 1) / Math.Log(2)) + 1)
End Sub

Sub NextPowerOf2_2(ByVal number As Long)
    Dim pos As Integer
    pos = 0
    While (number > 0)
        pos = pos + 1
        number = shr(number, 1)
    Wend
    
    Debug.Print 2 ^ pos
End Sub
Function shr(ByVal Value As Long, ByVal Shift As Byte) As Long
    Dim i As Byte
    shr = Value
    If Shift > 0 Then
        shr = Int(shr / (2 ^ Shift))
    End If
End Function

Answer 10

Here is a basic version for Go

// Calculates the next highest power of 2.
// For example: n = 15, the next highest power of 2 would be 16
func NearestPowerOf2(n int) int {
    v := n
    v--
    v |= v >> 1
    v |= v >> 2
    v |= v >> 4
    v |= v >> 8
    v |= v >> 16
    v++
    return v
}