/* 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
Aug 12, 2008
Finding nearest pow to 2
Subscribe to:
Posts (Atom)