/* gcc pow_opt.c */
/* http://jeffreystedfast.blogspot.com/search/label/algorithms */
#include
#include
#include
typedef long uint32_t;
static uint32_t nearest_pow1(uint32_t num)
{ uint32_t n = 1;
while (n < num)
n <<= 1; return n;
}static uint32_t nearest_pow2(uint32_t num)
{ uint32_t n = num > 0 ? num - 1 : 0;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;
return n;
}
static uint32_t nearest_pow3(uint32_t num)
{
int bit;
__asm__("bsrl %1,%0\n\t" "jnz 1f\n\t" "movl $-1,%0\n" "1:": "=r"(bit):"rm"(num));
return (1 << (bit + 1));
}
static uint32_t nearest_pow4(uint32_t num)
{
uint32_t j, k;
(j = num & 0xFFFF0000) || (j = num);
(k = j & 0xFF00FF00) || (k = j);
(j = k & 0xF0F0F0F0) || (j = k);
(k = j & 0xCCCCCCCC) || (k = j);
(j = k & 0xAAAAAAAA) || (j = k);
return j << 1;
}
//A simple performance test might be:
int main(int argc, char **argv)
{
uint32_t i, n = 0;
uint32_t test_pow = atol(argv[1]);
switch ( test_pow ) {
case 1:
for (i = 0; i < INT_MAX / 10; i++)
n += nearest_pow1(i);
case 2:
for (i = 0; i < INT_MAX / 10; i++)
n += nearest_pow2(i);
case 3:
for (i = 0; i < INT_MAX / 10; i++)
n += nearest_pow2(i);
case 4:
for (i = 0; i < INT_MAX / 10; i++)
n += nearest_pow2(i);
}
return n > 0 ? 1 : 0;
}
[vuhung@aoclife g++]$ for i in 1 2 3 4; do time ./a.out $i; done
real 0m43.297s
user 0m42.969s
sys 0m0.318s
real 0m20.455s
user 0m20.343s
sys 0m0.109s
real 0m13.653s
user 0m13.566s
sys 0m0.082s
real 0m6.817s
user 0m6.769s
sys 0m0.048s
Monday, 11 August 2008
Finding nearest pow to 2
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment