Here's another one, using inline x86-gas.
#include <stdint.h>
// One minor difference: will give 1 for x == 0.
static __inline__ uint32_t nextPowerOfTwo_asm (uint32_t x)
{
uint32_t r;
__asm__ (
"dec %1 \n\t"
"bsrl %1,%%ecx \n\t"
"jz end \n\t"
"inc %%ecx \n\t"
"shll %%cl, %0 \n\t"
"end: "
: "=r" (r)
: "r"(x), "0" (1)
: "ecx"
);
return r;
}
I have to admit it's not nearly as elegant as the previous
solution but... hey, it's my first inline-gas-hack. :)
I'm not even sure if this will run any faster than
nextPowerOfTwo() with -O2 turned on...
The idea basically is to find the highest set bit with bsr (Bit
Scan Reverse), add one to that and return 1 shifted left by the
number.
The include/asm* headers in kernel-source and/or /usr are a very
good place to get inspired on these things, btw.
Nice online-places to look are
http://www-106.ibm.com/developerworks/linux/library/l-ia.html
http://www.delorie.com/djgpp/doc/brennan/brennan_att_inline_djgpp.html
cheers,
Björn
On Wed, Sep 17, 2003 at 02:21:32PM +0200, Maarten de Boer wrote:
Hi,
A colleague of mine found this very clever algoritm to calculate the
next power of two for a given number. It comes from the Prophecy SDK for
3d game development
http://www.twilight3d.com/modules.php?op=modload&name=Downloads&fil…
Since this is a kind of thing often needed in audio processing, I wanted
to share it with you. I certainly can not think of a faster (or more
elegant) way of doing it.
Maarten
//////
/// Returns the closest power-of-two number greater or equal
/// to n for the given (unsigned) integer n.
/// Will return 0 when n = 0 and 1 when n = 1.
//////
inline uint32_t nextPowerOfTwo(uint32_t n)
{
--n;
n |= n >> 16;
n |= n >> 8;
n |= n >> 4;
n |= n >> 2;
n |= n >> 1;
++n;
return n;
}