Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

cnstrnd

Nearest power of 2

This topic is 5260 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

It probably has been raised earlier but I can''t find anything on how one does compute the nearest superior power of 2 elegantly (I mean not with a bunch of ''if'' tests) ? ie : 999 -> 1024 256 -> 256 33 -> 64 Thanks

Share this post


Link to post
Share on other sites
Advertisement
Take the log base 2 of the number, round up to the nearest integer, then exponentiate again.

shmoove

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

int pow2(int n)
{
int x = 1;

while(x < n) {
x <<= 1;
}

return 1;
}

Share this post


Link to post
Share on other sites
Thank you shmoove.

EDIT:
unsigned NearestSuperiorPowerOf2( unsigned n )
{
return (unsigned) pow( 2, ceil( log( n ) / log( 2 ) ) );
}

Right ?

[edited by - cnstrnd on June 7, 2004 7:10:55 AM]

Share this post


Link to post
Share on other sites
The fastest way to do is exploit the IEEE 754 representation of the floating point. This avoids any loop or any call to expensive math functions.

float y=float(x)*_fsqrt_2;
(*(int32*)&y) = (*(int32*)&y) & _clear_mantissa;
return (int32)y;

This might evn be improved. I just let you food for thoughts.

Share this post


Link to post
Share on other sites
Yay for recursion.


int NearestSuperiorPow2(int i)
{
int x = ((i - 1) & i);

return x ? NearestSuperiorPow2(x) : i << 1;
}

Share this post


Link to post
Share on other sites
@Charles :
unsigned NextPow2( unsigned n )
{
const int MantissaMask = (1<<23) - 1;

(*(float*)&n) = (float) n;
n = n + MantissaMask & ~MantissaMask;
n = (unsigned) (*(float*)&n);

return n;
}

Mmmmmhhhhh ... tasty !

[edited by - cnstrnd on June 7, 2004 8:28:47 AM]

Share this post


Link to post
Share on other sites
Cool too see you were capable to reach the answer alone

My _fsqrt_2 constant was meant to find the round to nearest (in logarithmic scale). You did it right by adding this bias to get the nearest higher power of two. I read your question too fast.
And it's faster to add an int than mul by a float.

Note that this solution is faster than any other proposed but it's not very good due to 2 store and load dependencies with the pointer casts. I suppose it runs in around 10-20 cycles.

However this can be done in great speed in SIMD, 3DNow or SSE. Because the integer representation of floating points is free. Well basically this would be something like (pseudo 3DNow asm):

// v2f32 nearsuppow2_2f(const v2f32)
// optionnally convert int to float for
// v2i32 nearsuppow2_2i(const v2i32)
// pi2fd n, n
// hacking the integer representation of the float
paddd n, _mantissa_mask
pandn n, _mantissa_mask
// pf2id n, n
That's all !!!!

Maybe a function I could add to my Virtual SIMD instruction set since it's only two or four instructions

Q : In which context do you use such a function. I just wonder if it's of general use. I thought of mem allocation algos, or putting arbitrary images into power of two texture chuncks, but that's not obvious.

PS : Maybe you could throw an eye to my "Horse power math lib(2)", thread, this may interest you. I also need guys able to understand such math tricks. Imagine this lib is already full of hundreds such things But I can't do everything alone. In the same scope of thinking, I plan to extend the SIMD instruction sets with some useful functions.

[edited by - Charles B on June 7, 2004 8:58:16 AM]

Share this post


Link to post
Share on other sites

This topic is 5260 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.

Guest
This topic is now closed to further replies.

  • 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!