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

1 comment:

Anonymous said...

Football is a nice game and online betting on it is an exciting way to enjoy the game. As a soccer crazy fan if you want to lay your hand on the football betting and make money, it is advised to take the help of football betting guide. This betting guide will not just provide you gaming strategies but help you make more successful bets. The football betting guide comes handy, helping you avoid loosing on too many bets. Generally a quality guide is usually written by someone who has spent years researching on the subject and has got vast knowledge. With this type of information there is a chance of achieving 98 percent results. nfl betting baseball betting basketball betting boxing betting cricket betting darts betting football betting golf betting handball betting hockey betting rugby betting snooker betting tennis betting Sportsbook betting volume differs all through the year. Patrons have more attention in certain types of sports, thus a raise in wagered money is apparent when those sports are in time. Some major sporting events that don't follow a certain schedule, like boxing, can create peaks of activity for sportsbooks all through the year. Football is the most admired sport of bet on today. [url=http://www.pulsebet.com/betting/American-Football]nfl betting[/url] [url=http://www.pulsebet.com/betting/Baseball-betting]baseball betting[/url] [url=http://www.pulsebet.com/betting/Basketball-betting]basketball betting[/url] [url=http://www.pulsebet.com/betting/Boxing-betting]boxing betting[/url] [url=http://www.pulsebet.com/betting/Cricket-betting]cricket betting[/url] [url=http://www.pulsebet.com/betting/Darts-betting]darts betting[/url] [url=http://www.pulsebet.com/betting/Football-betting]football betting[/url] [url=http://www.pulsebet.com/betting/Golf-betting]golf betting[/url] [url=http://www.pulsebet.com/betting/Handball-betting]handball betting[/url] [url=http://www.pulsebet.com/betting/Hockey-betting]hockey betting[/url] [url=http://www.pulsebet.com/betting/Rugby-betting]rugby betting[/url] [url=http://www.pulsebet.com/betting/Snooker-betting]snooker betting[/url] [url=http://www.pulsebet.com/betting/Tennis-betting]tennis betting[/url] • Bets with low value- Well, if you have ever come across large messages with tempting offers, give yourself a break. It is just a way to allure people and make them spend precious money .It is a poor value bets and should be avoided. http://www.pulsebet.com/betting/American-Football http://www.pulsebet.com/betting/Baseball-betting http://www.pulsebet.com/betting/Basketball-betting http://www.pulsebet.com/betting/Boxing-betting http://www.pulsebet.com/betting/Cricket-betting http://www.pulsebet.com/betting/Darts-betting http://www.pulsebet.com/betting/Football-betting http://www.pulsebet.com/betting/Golf-betting http://www.pulsebet.com/betting/Handball-betting http://www.pulsebet.com/betting/Hockey-betting http://www.pulsebet.com/betting/Rugby-betting http://www.pulsebet.com/betting/Snooker-betting http://www.pulsebet.com/betting/Tennis-betting