#### Archived

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

# Nearest power of 2

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

## 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 on other sites
Take the log base 2 of the number, round up to the nearest integer, then exponentiate again.

shmoove

##### Share on other sites
int pow2(int n){  int x = 1;  while(x < n) {    x <<= 1;  }  return 1;}

##### Share on other sites
Example:

log2(999) = 9.96 -> 10 -> 2^10 = 1024

##### 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 on other sites
If you need it FAST:

unsigned NextPow2( unsigned x ) {    --x;    x |= x >> 1;    x |= x >> 2;    x |= x >> 4;    x |= x >> 8;    x |= x >> 16;    return ++x;}

~nz

// Website // Google // GameDev // NeHe // MSDN // OpenGL Extensions //

##### 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 on other sites
Yay for recursion.

int NearestSuperiorPow2(int i){   int x = ((i - 1) & i);   return x ? NearestSuperiorPow2(x) : i << 1;}

##### 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 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
// 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 on other sites

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

This topic is now closed to further replies.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 18
• 13
• 14
• 43
• 63