Rounding value to nearest power of two

Question

I am looking for the fastest way in C# to round a value to the nearest power of two. I've discovered that the fastest way to round a value to the next power of two if to use bitwise operators like this.

int ToNextNearest(int x)
{
    if (x < 0) { return 0; }
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x + 1;
}

But this gives the next nearest and not the nearest and I would like to only have the nearest power of two. Here is a simple way to do that.

int ToNearest(int x)
{
    Math.Pow(2, Math.Round(Math.Log(x) / Math.Log(2)));
}

But is there a better optimized version of finding the nearest power of two value ?

Thanks a lot.

possible duplicate: [Round to the nearest power of two](https://stackoverflow.com/q/4398711/995714) — phuclv, May 23 '22 at 05:24

score 10 · Accepted Answer · answered Aug 13 '15 at 20:30

10

Surely the best way is to use your bitwise routine to find the next power of two, then divide that result by two. This gives you the previous power of two. Then a simple comparison will tell you which of the two is closer.

int ToNearest(int x)
{
  int next = ToNextNearest(x);
  int prev = next >> 1;
  return next - x < x - prev ? next : prev;
}

Untested code but you get the idea.

answered Aug 13 '15 at 20:30

john

85,011
4
57
81

1

This does not behave the same as his ToNearest method. At least any boundary number will return different results. – Mark Peters Aug 13 '15 at 21:18
Could you ellaborate @MarkPeters ? – MaT Aug 14 '15 at 04:57
1

@Mat Try a 3, 6, or 12 in this method versus your log() based method. I believe one rounds up and one rounds down. – Mark Peters Aug 14 '15 at 12:06
@MarkPeters Yes, this is true but which one is mathematically right as for an example 6 is as close from 4 or 8. I think that I need to choose the higher or lower value by just changing the comparison method (< or <=). – MaT Aug 14 '15 at 13:12
1

@MaT Agreed. I was just pointing out the different behavior. You would have the best idea of what rounding behavior (and there are several) is appropriate here – Mark Peters Aug 14 '15 at 13:38

score 3 · Answer 2 · answered Jun 13 '20 at 22:52

On .Net Core, the fastest way to do this would probably to use the intrinsics operations:

private static int NearestPowerOf2(uint x)
{
    return 1 << (sizeof(uint) * 8 - BitOperations.LeadingZeroCount(x - 1));
}

On CPU supporting the LZCNT instructions, it is just 6 CPU instructions, without branching.

NesCafe Zos42 · Answer 3 · 2019-01-06T20:33:12.987

2

I'm using this:

public static int CeilPower2(int x)
{
    if (x < 2) {
        return 1;
    }
    return (int) Math.Pow(2, (int) Math.Log(x-1, 2) + 1);
}

public static int FloorPower2(int x)
{
    if (x < 1) {
        return 1;
    }
    return (int) Math.Pow(2, (int) Math.Log(x, 2));
}

edited Jan 06 '19 at 20:33

answered Jan 06 '19 at 20:23

NesCafe Zos42

69
4

score 2 · Answer 4 · edited Sep 16 '22 at 02:58

2

.Net6 has introduced a method for this

using System.Numerics;

var nearestPowOf2 = BitOperations.RoundUpToPowerOf2(100); //returns 128

edited Sep 16 '22 at 02:58

Lars Holm Jensen

1,645
1
12
14

answered Oct 25 '21 at 16:43

Vivek Nuna

25,472
25
109
197

score 1 · Answer 5 · answered Aug 13 '15 at 20:43

1

How about this:

int ToNearest(int val, int pow)
{
    if (pow < 0) return 0;
    if (pow == 0) return val;

    if (val & (1 << (pow - 1))) {
        return ((val >> pow) + 1) << pow;
    } else {
        return (val >> pow) << pow;
    }
}

answered Aug 13 '15 at 20:43

dbush

205,898
23
218
273

score 0 · Answer 6 · answered Aug 13 '15 at 20:46

Haven't tested but i think this could work

int ToNearest(value x)
{
    int num = 0;
    for(int i=1; i < 65; i++)
    {
        int cur = Math.Abs(value - 0<<i);
        if(Math.Abs(value - 0<<i) < Math.Abs(value - num))
            num = cur;
        else if(num != 0) break;
    }
    return num;
}

score 0 · Answer 7 · answered Aug 04 '17 at 16:12

This is the full implementation of the suggested solution of @john, with the change that it will round up if the value is exactly in between the next and previous power of two.

public static int RoundToNextPowerOfTwo(int a)
{
    int next = CeilToNextPowerOfTwo(a);
    int prev = next >> 1;
    return next - a <= a - prev ? next : prev;
}

public static int CeilToNextPowerOfTwo(int number)
{
    int a = number;
    int powOfTwo = 1;

    while (a > 1)
    {
        a = a >> 1;
        powOfTwo = powOfTwo << 1;
    }
    if (powOfTwo != number)
    {
        powOfTwo = powOfTwo << 1;
    }
    return powOfTwo;
}

Marcel · Answer 8 · 2017-08-05T07:21:54.783

Since C# requires IEEE754 floats there is probably a faster way on any platform that does not emulate the floating point functions:

int ToNearestPowerOf2(int x) =>
  1 << (int)(BitConverter.DoubleToInt64Bits(x + x/3) >> 52) - 1023;

Rationale:

x + x/3
nearest power of 2, basically *4/3
(BitConverter.DoubleToInt64Bits(x) >> 52) - 1023
take floating point exponent for floor(ln2(x))
1 << x
exponential function with base 2

The function obviously requires a positive value for x. 0 won't work because the closest power of 2 is -∞, and negative values have a complex logarithms.

Whether this is the fastest way will probably highly depend on what the JIT optimizer squeezes out of the code, more specifically how it handles the hard pointer cast in DoubleToInt64Bits. This may prevent other optimizations.

You do not have to use any comparison to get the nearest power of 2. Since all powers of two are separated by the same factor the rounding point is always at 3/4 of the next power of 2 (i.e. exactly the topmost 2 bits are set). So multiplication by the reciprocal followed by truncation will do the job.

Rounding value to nearest power of two

8 Answers8