Jump to content
  • Advertisement
Sign in to follow this  
DrGUI

[.net] Next power of 2

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

If you intended to correct an error in the post then please contact us.

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
	// this mask test for the sign bit and the exponents sign in one step
	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); 
    highestBit += mask & 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
	// this mask test for the sign bit and the exponents sign in one step
	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
	// this mask test for the sign bit and the exponents sign in one step
	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 this post


Link to post
Share on other sites
Advertisement
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 v

v--;
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 blah
else
{
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!