Archived

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

tool_2046

nearest power of 2

Recommended Posts


//pseudo-code, largeint is arbitrary
largeint findNextPowerOfTwo(largeint n) {
largeint i = 1;
while(i < n)
i *= 2;
return i;
}


cyn

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;


there you go. if you have v is a power of two then it will just result in the same number. =)

Share this post


Link to post
Share on other sites
Assuming an x86 processor is the target:


_asm
{
bsr ecx, n
mov result, 2
shl result, cl
}


[edited by - Mastaba on October 17, 2003 2:34:29 PM]

Share this post


Link to post
Share on other sites
For non integers:

ceil(ln(x)/ln(2))

would be the power of 2 greater than x (ie for 7 it would return 3, since 2^3=8). Obviously you could precalc 1/(ln(2)) as 1.4426950408889634073599246810019, then just do:

ceil(ln(x)*1.4426950408889634073599246810019);

This is calculating the base 2 logarithm of x btw, and rounding up, so can be used in other circulstances too.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Transform the number in base 2. Count the number of 1''s and 0''s that you have in the number. This number is the exponent of the smallest power of 2 that is greater than the number given.

Share this post


Link to post
Share on other sites