用位运算求 f(x, y) -> 2^y > x

gistfile1.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>

uint32_t slow(uint32_t b)
{
    int n, i;
    for(n=-1, i = 1; i <= b; i<<=1, n++);
    /* not optimal */
    return n;
}

uint32_t fast(uint32_t x)
{
    uint32_t n = 0, len = 16; //depend on sizeof()
    uint32_t tmp;
    while (len) {
        /* ..x. | xxxx */
        tmp = x >> len;
        if (tmp) {
            x = tmp;
            n += len;
        }
        else
            x = x & ( (1<<len) - 1);

        len >>= 1;
    }
    return n;
}

int main()
{
    uint32_t x;
    uint32_t a1, a2;
    /*printf("%d\n", sizeof(uint32_t));*/
#if 1 /* Correct */
    for (x = 1; x < 1000000; ++x){
        a1 = slow(x);
        a2 = fast(x);
        if (a1 != a2) {
            printf("Error when x = %u, answer = %u, got %u\n",
                    x, a1, a2);
            exit(1);
        }
    }
#endif

#if 0 /* time */
#define END 10000000
#define LARGE 100
    time_t t0, t1;
    t0 = clock();

    for (a2 = 0; a2 < LARGE; ++a2)
    for (x = 1; x < END; ++x)
        a1 = slow(x);
    t1 = clock();
    printf("old way: %u\n", t1 - t0);

    t0 = clock();

    for (a2 = 0; a2 < LARGE; ++a2)
    for (x = 1; x < END; ++x)
        a1 = fast(x);
    t1 = clock();
    printf("new way: %u\n", t1 - t0);

#endif
    return 0;
}