29

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.

alecxe
  • 441,113
  • 110
  • 1,021
  • 1,148
abbs
  • 291
  • 1
  • 3
  • 3
  • 1
    "One line" in a programming language? Or mathematically? – Sven Marnach Dec 09 '10 at 13:33
  • 1
    What language are you trying to do this in? What have you tried? – Rowland Shaw Dec 09 '10 at 13:33
  • 2
    duplicate of http://stackoverflow.com/questions/466204/rounding-off-to-nearest-power-of-2 – Josh Dec 09 '10 at 13:33
  • 8
    In your example, the nearest power of two for 5 is actually 4 (or 2^2). For 6, the answer is ambiguous (may be either 2^2 or 2^3). Can you specify the question a little further? – Gerco Dries Dec 09 '10 at 13:34
  • @ Gerco Dries: It's legitimate to use a logarithmic scale when considering the nearest power of 2 to a number. On that basis 6 is closer to 2^3 than 2^2. Not saying you are wrong, just an alternate view point. – JeremyP Dec 09 '10 at 14:01
  • possible duplicate of [Given an integer, how do I find the next largest power of two using bit-twiddling?](http://stackoverflow.com/questions/1322510/given-an-integer-how-do-i-find-the-next-largest-power-of-two-using-bit-twiddlin) – Nathan Jan 16 '14 at 00:44
  • Possible duplicate of [Rounding up to nearest power of 2](http://stackoverflow.com/questions/466204/rounding-up-to-nearest-power-of-2) – phuclv Mar 04 '17 at 15:23
  • This is roughly equivalent to [counting leading zeros](https://stackoverflow.com/questions/376840/trailing-leading-zero-count-for-a-byte), since you're interested in the first non-zero bit. – Ringding Dec 09 '10 at 13:33

8 Answers8

32

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++;
phuclv
  • 32,499
  • 12
  • 130
  • 417
Jason S
  • 178,603
  • 161
  • 580
  • 939
20

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))
Ankit Bansal
  • 4,749
  • 1
  • 21
  • 40
9

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.

phuclv
  • 32,499
  • 12
  • 130
  • 417
maff
  • 827
  • 1
  • 8
  • 9
6

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.

High Performance Mark
  • 75,673
  • 7
  • 99
  • 152
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

El Ronnoco
  • 11,453
  • 5
  • 36
  • 65
2

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);
}
phuclv
  • 32,499
  • 12
  • 130
  • 417
Naveen Venkatesh
  • 21
  • 1
1

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;
}
phuclv
  • 32,499
  • 12
  • 130
  • 417
Stefan Reich
  • 910
  • 9
  • 12
  • For Java this should be the correct answer. While it does the same bit-twiddling under the hood, the implementation is annotated as `@HotSpotIntrinsicCandidate` which means that it can be replaced by a faster native method if the architecture allows for it. – andbi Feb 12 '21 at 22:58
0

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
phuclv
  • 32,499
  • 12
  • 130
  • 417
Cuinn Herrick
  • 187
  • 2
  • 6