/* ---------------------------------------------------------------- *\

  file    : highest_bit_set.c
  author  : m. gumz <akira at fluxbox dot org>
  copyr   : copyright (c) 2005 by m. gumz

  license : see LICENSE
  
  start   : Mo 13 Jun 2005 15:15:44 CEST

\* ---------------------------------------------------------------- */
/* ---------------------------------------------------------------- *\

  about :

    macros to find the highest bit set

\* ---------------------------------------------------------------- */
/* ---------------------------------------------------------------- *\
  includes
\* ---------------------------------------------------------------- */
#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <limits.h>

/* linear approach */
#define CHECK_BITS_BIT1(nr)  (  nr &  1      ? 1      : 0 )
#define CHECK_BITS_BIT2(nr)  ( (nr >> 1) & 1 ? 1 << 1 : CHECK_BITS_BIT1(nr) )
#define CHECK_BITS_BIT3(nr)  ( (nr >> 2) & 1 ? 1 << 2 : CHECK_BITS_BIT2(nr) )
#define CHECK_BITS_BIT4(nr)  ( (nr >> 3) & 1 ? 1 << 3 : CHECK_BITS_BIT3(nr) )
#define CHECK_BITS_BIT5(nr)  ( (nr >> 4) & 1 ? 1 << 4 : CHECK_BITS_BIT4(nr) )
#define CHECK_BITS_BIT6(nr)  ( (nr >> 5) & 1 ? 1 << 5 : CHECK_BITS_BIT5(nr) )
#define CHECK_BITS_BIT7(nr)  ( (nr >> 6) & 1 ? 1 << 6 : CHECK_BITS_BIT6(nr) )
#define CHECK_BITS_BIT8(nr)  ( (nr >> 7) & 1 ? 1 << 7 : CHECK_BITS_BIT7(nr) )
#define CHECK_BITS_BIT9(nr)  ( (nr >> 8) & 1 ? 1 << 8 : CHECK_BITS_BIT8(nr) )
#define CHECK_BITS_BIT10(nr) ( (nr >> 9) & 1 ? 1 << 9 : CHECK_BITS_BIT9(nr) )
#define CHECK_BITS_BIT11(nr) ( (nr >> 10) & 1 ? 1 << 10 : CHECK_BITS_BIT10(nr) )
#define CHECK_BITS_BIT12(nr) ( (nr >> 11) & 1 ? 1 << 11 : CHECK_BITS_BIT11(nr) )
#define CHECK_BITS_BIT13(nr) ( (nr >> 12) & 1 ? 1 << 12 : CHECK_BITS_BIT12(nr) )
#define CHECK_BITS_BIT14(nr) ( (nr >> 13) & 1 ? 1 << 13 : CHECK_BITS_BIT13(nr) )
#define CHECK_BITS_BIT15(nr) ( (nr >> 14) & 1 ? 1 << 14 : CHECK_BITS_BIT14(nr) )
#define CHECK_BITS_BIT16(nr) ( (nr >> 15) & 1 ? 1 << 15 : CHECK_BITS_BIT15(nr) )
#define CHECK_BITS_BIT17(nr) ( (nr >> 16) & 1 ? 1 << 16 : CHECK_BITS_BIT16(nr) )
#define CHECK_BITS_BIT18(nr) ( (nr >> 17) & 1 ? 1 << 17 : CHECK_BITS_BIT17(nr) )
#define CHECK_BITS_BIT19(nr) ( (nr >> 18) & 1 ? 1 << 18 : CHECK_BITS_BIT18(nr) )
#define CHECK_BITS_BIT20(nr) ( (nr >> 19) & 1 ? 1 << 19 : CHECK_BITS_BIT19(nr) )
#define CHECK_BITS_BIT21(nr) ( (nr >> 20) & 1 ? 1 << 20 : CHECK_BITS_BIT20(nr) )
#define CHECK_BITS_BIT22(nr) ( (nr >> 21) & 1 ? 1 << 21 : CHECK_BITS_BIT21(nr) )
#define CHECK_BITS_BIT23(nr) ( (nr >> 22) & 1 ? 1 << 22 : CHECK_BITS_BIT22(nr) )
#define CHECK_BITS_BIT24(nr) ( (nr >> 23) & 1 ? 1 << 23 : CHECK_BITS_BIT23(nr) )
#define CHECK_BITS_BIT25(nr) ( (nr >> 24) & 1 ? 1 << 24 : CHECK_BITS_BIT24(nr) )
#define CHECK_BITS_BIT26(nr) ( (nr >> 25) & 1 ? 1 << 25 : CHECK_BITS_BIT25(nr) )
#define CHECK_BITS_BIT27(nr) ( (nr >> 26) & 1 ? 1 << 26 : CHECK_BITS_BIT26(nr) )
#define CHECK_BITS_BIT28(nr) ( (nr >> 27) & 1 ? 1 << 27 : CHECK_BITS_BIT27(nr) )
#define CHECK_BITS_BIT29(nr) ( (nr >> 28) & 1 ? 1 << 28 : CHECK_BITS_BIT28(nr) )
#define CHECK_BITS_BIT30(nr) ( (nr >> 29) & 1 ? 1 << 29 : CHECK_BITS_BIT29(nr) )
#define CHECK_BITS_BIT31(nr) ( (nr >> 30) & 1 ? 1 << 30 : CHECK_BITS_BIT30(nr) )
#define CHECK_BITS_BIT32(nr) ( (nr >> 31) & 1 ? 1 << 31 : CHECK_BITS_BIT31(nr) )

/* divide N conquer */
#define CHECK_BITS2(nr)  ( nr & 0x2 ? 2 : (nr & 0x1 ? 1 : 0 ))
#define CHECK_BITS4(nr)  ( nr & 0xc ? CHECK_BITS2(nr >> 2) << 2 : CHECK_BITS2(nr) )
#define CHECK_BITS8(nr)  ( nr & 0xf0 ? CHECK_BITS4(nr >> 4) << 4 : CHECK_BITS4(nr) )
#define CHECK_BITS16(nr) ( nr & 0xff00 ? CHECK_BITS8(nr >> 8) << 8 : CHECK_BITS8(nr) )
#define CHECK_BITS32(nr) ( nr & 0xffff0000 ? CHECK_BITS16(nr >> 16) << 16 : CHECK_BITS16(nr) )



#define CHECK(a) a, CHECK_BITS32(a), CHECK_BITS_BIT32(a)

float timediff(struct timeval* start, struct timeval* end) {
    return (end->tv_sec + 0.0000001 * end->tv_usec) - 
           (start->tv_sec + 0.0000001 * start->tv_usec);
}

int main() {

    printf("%x => %x %x\n", CHECK(0x00000000));
    printf("%x => %x %x\n", CHECK(0x00000001));
    printf("%x => %x %x\n", CHECK(0x00000002));
    printf("%x => %x %x\n", CHECK(0x00000004));
    printf("%x => %x %x\n", CHECK(0xffffffff));
    printf("%x => %x %x\n", CHECK(0xff000000));
    printf("%x => %x %x\n", CHECK(0x00000031));
    printf("%x => %x %x\n", CHECK(0x000000ff));
    printf("%x => %x %x\n", CHECK(0x00000100));

    {
        struct timeval start;
        struct timeval end;
        struct timezone tz;
        unsigned int i;

        gettimeofday(&start, &tz);
        for (i = 0; i < UINT_MAX; ++i) {
            CHECK_BITS32(i);
        }
        gettimeofday(&end, &tz);

        printf("CHECK_BITS32 fuer %u: %f\n", UINT_MAX, timediff(&start, &end));
    }
    
    {
        struct timeval start;
        struct timeval end;
        struct timezone tz;
        unsigned int i;

        gettimeofday(&start, &tz);
        for (i = 0; i < UINT_MAX; ++i) {
            CHECK_BITS_BIT32(i);
        }
        gettimeofday(&end, &tz);

        printf("CHECK_BITS_BIT32 fuer %u: %f\n", UINT_MAX, timediff(&start, &end));
    }

    {
        struct timeval start;
        struct timeval end;
        struct timezone tz;
        unsigned int i;

        gettimeofday(&start, &tz);
        for (i = 0; i < UINT_MAX; ++i) {
            CHECK_BITS32(i);
        }
        gettimeofday(&end, &tz);

        printf("CHECK_BITS32 fuer %u: %f\n", UINT_MAX, timediff(&start, &end));
    }
 
    {
        struct timeval start;
        struct timeval end;
        struct timezone tz;
        unsigned int i;

        gettimeofday(&start, &tz);
        for (i = 0; i < UINT_MAX; ++i) {
            CHECK_BITS_BIT32(i);
        }
        gettimeofday(&end, &tz);

        printf("CHECK_BITS_BIT32 fuer %u: %f\n", UINT_MAX, timediff(&start, &end));
    }
    
    return 0;
}