Aug 12, 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