# [.net] Next power of 2

This topic is 4892 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi How do you calculate the next power of 2 up or down in .NET? I'm sure this is quite a common thing. Of course I can go through a loop comparing but I'm just morbidly curious [grin] From 'Real-Time Terrain Engines using C++ and DirectX 9' [Greg Snook] I have the following: (But I'm using this for textures - so more interested in integer powers of two at the moment [grin])

//I believe I can use Marshal for this?

// reinterpret a float as an int32
#define fpBits(f) (*reinterpret_cast<const int32*>(&(f)))

// reinterpret an int32 as a float
#define intBits(i) (*reinterpret_cast<const float*>(&(i)))

//highestBitSet uses assembler with bsr which I obviously don't want

//:	nearestPowerOfTwo
//----------------------------------------------------------------------------------------
//
//	Rounds the input value to the nearest power-of-two.
//  All values below 1 generate a result of 1
//
//-------------------------------------------------------------------------------------://
template<class T>
inline T nearestPowerOfTwo(T input)
{

// the least possible power-of-two value is 1
if (input <= 1) return 1;

int highestBit = highestBitSet(input);
int roundingTest = input & (1<< (highestBit-1));
if (roundingTest) ++highestBit;
return static_cast<T>(1<<highestBit);
}

template<>
inline float nearestPowerOfTwo(float input)
{
// convert the value to an int
int result = fpBits(input);

// if the value is negative, or less than 1.0f, return 1.0f
if (result & 0xc0000000) return 1.0f;

// if anything is in the high bit of the mantissa,
// use it to add one to the exponent
result += (result & 0x800000)<<1;

// trim away the mantissa
result &= ~((1<<23)-1);

// convert back to floating-point as we return
return (intBits(result));
}

//:	ceilingPowerOfTwo
//----------------------------------------------------------------------------------------
//
//	Rounds the next-highest power-of-two value.
//  All values below 1 generate a result of 1
//
//-------------------------------------------------------------------------------------://
template<class T>
inline T ceilingPowerOfTwo(T input)
{
// the least possible power-of-two value is 1
if (input <= (T)1) return 1;

int highestBit = highestBitSet(index);
int mask = input & ((1<< highestBit)-1);
return static_cast<T>(1<<highestBit);
}

template<>
inline float ceilingPowerOfTwo(float input)
{
// convert the value to an int
int result = fpBits(input);

// if the value is negative, or less than 1.0f, return 1.0f
if (result & 0xc0000000) return 1.0f;

// if anything is in the mantissa, round up
result += 0x7fffff;

// trim away the mantissa
result &= ~((1<<23)-1);

// convert back to floating-point as we return
return (intBits(result));
}

//:	floorPowerOfTwo
//----------------------------------------------------------------------------------------
//
//	Rounds the next-least power-of-two value.
//  All values below 1 generate a result of 1
//
//-------------------------------------------------------------------------------------://
template<class T>
inline T floorPowerOfTwo(T input)
{
// the least possible power-of-two value is 1
if (input <= (T)1) return 1;

int highestBit = highestBitSet(input);
return static_cast<T>(1<<highestBit);
}

template<>
inline float floorPowerOfTwo(float input)
{
// convert the value to an int
int result = fpBits(input);

// if the value is negative, or less than 1.0f, return 1.0f
if (result & 0xc0000000) return 1.0f;

// trim away the mantissa
result &= ~((1<<23)-1);

// convert back to floating-point as we return
return (intBits(result));
}


Thanks you clever people!

##### Share on other sites
double nextPowerOfTwo = Math.Pow(2.0, Math.Floor(Math.Log(number)/Math.Log(2.0)));

##### Share on other sites
This looks like a job for bit twiddling!

Quote:
 Round up to the next highest power of 2 unsigned int v; // compute the next highest power of 2 of 32-bit vv--;v |= v >> 1;v |= v >> 2;v |= v >> 4;v |= v >> 8;v |= v >> 16;v++;In 12 operations, this code computes the next highest power of 2 for a 32-bit integer. The result may be expressed by the formula 1 << (lg(v - 1) + 1). It would be faster by 2 operations to use the formula and the log base 2 methed that uses a lookup table, but in some situations, lookup tables are not suitable, so the above code may be best. It works by copying the highest set bit to all of the lower bits, and then adding one, which results in carries that set all of the lower bits to 0 and one bit beyond the highest set bit to 1. If the original number was a power of 2, then the decrement will reduce it to one less, so that we round up to the same original value. Devised by Sean Anderson, Sepember 14, 2001.

I love that page.

Also I was looking at the methods you are using for floats, I think something similar would work fine for ints. You can find the "highest bit set" like this:

int num;int highest_bit_set = 0;for (int i=0; i < 32; i++)  if (num & (1 << i))    highest_bit_set = i;

and from there it's easy:
if (num == 0)  // blah blahelse{  power_of_2_rounded_up = 1 << (highest_bit_set + 1);  power_of_2_rounded_down = 1 << highest_bit_set;}

The added benefit to using the second method is that your friends won't think you're a hacker =D

##### Share on other sites
Thanks a lot guys!

(capn_midnight, suspended?)

I'll just go and test it...

Haven't tested yet, but I have implemented.

I optimized HighestSetBit so it can return straight away when it finds a bit. I haven't been taught about algorithmic complexity yet (probably be doing that next year or year after in AS or A level maths or further maths) but I think that makes it O(n/2) on average rather than always O(n). Integers are usually smaller than full capacity so there won't be that much difference.

Don't say I'm microoptimizing too much - I thought all of that while typing out the function!

/// <summary>/// Returns the highest set bit of <paramref name="value"/>, in the range of 0 to 31, and -1 if/// <paramref name="value"/> equals 0./// </summary>/// <param name="value">The value to find the highest set bit of.</param>/// <returns>/// The highest set bit of <paramref name="value"/>, in the range of 0 to 31, and -1 if/// <paramref name="value"/> equals 0.</returns>public static int HighestBitSet(System.Int32 value){	for (int i = 31; i >= 0; i--)		if ((value & (1 << i)) != 0)			return i;	return -1;}

[Edited by - DrGUI on October 24, 2005 6:33:07 AM]

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633755
• Total Posts
3013706
×