Monday, 11 August 2008

Finding nearest pow to 2



/* 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

No comments:

Post a Comment