Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Register Log in
  • Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Macro that returns the bit number of flagmask 1

Status
Not open for further replies.
RbgoWeb

RbgoWeb

Programmer
Apr 10, 2002
91
0
0
NL
I have setup this macro that returns the bit number of a given flag mask...
0x00000001 will result in 0
0x00001000 will result in 12
0x00008000 will result in 15
0x00010000 will result in 16
0x80000000 will result in 31
When a mask exceeds 32 bit or or any combination of flags are OR-ed together the result is 32.
Code: 
//Macro that results in a bitmask
#define BITNMASK(bitn)			((DWORD) (((DWORD) 1) << (bitn)) )
//Macro that results in a bit number
#define MASKBITN(mask)			((((DWORD)(mask)) == 0x00000001) ? ( 0 ) : ( (((DWORD)(mask)) == 0x00000002) ? ( 1 ) : ( (((DWORD)(mask)) == 0x00000004) ? ( 2 ) : ( (((DWORD)(mask)) == 0x00000008) ? ( 3 ) : ( (((DWORD)(mask)) == 0x00000010) ? ( 4 ) : ( (((DWORD)(mask)) == 0x00000020) ? ( 5 ) : ( (((DWORD)(mask)) == 0x00000040) ? ( 6 ) : ( (((DWORD)(mask)) == 0x00000080) ? ( 7 ) : ( (((DWORD)(mask)) == 0x00000100) ? ( 8 ) : ( (((DWORD)(mask)) == 0x00000200) ? ( 9 ) : ( (((DWORD)(mask)) == 0x00000400) ? ( 10 ) : ( (((DWORD)(mask)) == 0x00000800) ? ( 11 ) : ( (((DWORD)(mask)) == 0x00001000) ? ( 12 ) : ( (((DWORD)(mask)) == 0x00002000) ? ( 13 ) : ( (((DWORD)(mask)) == 0x00004000) ? ( 14 ) : ( (((DWORD)(mask)) == 0x00008000) ? ( 15 ) : ( (((DWORD)(mask)) == 0x00010000) ? ( 16 ) : ( (((DWORD)(mask)) == 0x00020000) ? ( 17 ) : ( (((DWORD)(mask)) == 0x00040000) ? ( 18 ) : ( (((DWORD)(mask)) == 0x00080000) ? ( 19 ) : ( (((DWORD)(mask)) == 0x00100000) ? ( 20 ) : ( (((DWORD)(mask)) == 0x00200000) ? ( 21 ) : ( (((DWORD)(mask)) == 0x00400000) ? ( 22 ) : ( (((DWORD)(mask)) == 0x00800000) ? ( 23 ) : ( (((DWORD)(mask)) == 0x01000000) ? ( 24 ) : ( (((DWORD)(mask)) == 0x02000000) ? ( 25 ) : ( (((DWORD)(mask)) == 0x04000000) ? ( 26 ) : ( (((DWORD)(mask)) == 0x08000000) ? ( 27 ) : ( (((DWORD)(mask)) == 0x10000000) ? ( 28 ) : ( (((DWORD)(mask)) == 0x20000000) ? ( 29 ) : ( (((DWORD)(mask)) == 0x40000000) ? ( 30 ) : ( (((DWORD)(mask)) == 0x80000000) ? ( 31 ) : ( 32 ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ))
The macro works fine, and after experimenting I thought it was the best solution;
A seeking loop with shifts and compares...
(a)Use 2-3 times more processing
(b)Cannot result in a value but must set an operand because it has more than one statement.

Still I wonder if a macro exist, that does the same, but in a smarter, shorter, more efficient and elegant way?
 
Sort by date Sort by votes
I think more useful and robust will be the inversed macros:
Code: 
#define BITMASK(i) (1<<(i))
 
Upvote 0 Downvote
How about this instead?

Code: 
#include <math.h>
#define MASKBITN(mask) ((mask & (mask - 1)) ? 32 :
                        floor (log(mask) / log(2) + 0.5))
 
Upvote 0 Downvote
If you are using a Motorola 680x0 look up the BFFFO instruction.
 
Upvote 0 Downvote
> (a)Use 2-3 times more processing
Really!?
A simple loop compiled with GCC (with or without optimisation) is at least as good as your huge macro.

If your compiler doesn't inline short static functions for you, perhaps it will respond better if you use the inline keyword (which new C compilers support, and C++ compilers support).

My test code
Code: 
#include <stdio.h>

/* read the pentium counter */
#define RDTSC(llptr) {     __asm__ __volatile__ (     "rdtsc"     : "=A" (llptr) ); }

typedef unsigned long DWORD;

/* some test data */
DWORD samples[] = {
    0x00000001,
    0x00001000,
    0x00008000,
    0x00010000,
    0x80000000,
};

#define BITNMASK(bitn)            ((DWORD) (((DWORD) 1) << (bitn)) )
#define MASKBITN(mask)            ((((DWORD)(mask)) == 0x00000001) ? ( 0 ) : ( (((DWORD)(mask)) == 0x00000002) ? ( 1 ) : ( (((DWORD)(mask)) == 0x00000004) ? ( 2 ) : ( (((DWORD)(mask)) == 0x00000008) ? ( 3 ) : ( (((DWORD)(mask)) == 0x00000010) ? ( 4 ) : ( (((DWORD)(mask)) == 0x00000020) ? ( 5 ) : ( (((DWORD)(mask)) == 0x00000040) ? ( 6 ) : ( (((DWORD)(mask)) == 0x00000080) ? ( 7 ) : ( (((DWORD)(mask)) == 0x00000100) ? ( 8 ) : ( (((DWORD)(mask)) == 0x00000200) ? ( 9 ) : ( (((DWORD)(mask)) == 0x00000400) ? ( 10 ) : ( (((DWORD)(mask)) == 0x00000800) ? ( 11 ) : ( (((DWORD)(mask)) == 0x00001000) ? ( 12 ) : ( (((DWORD)(mask)) == 0x00002000) ? ( 13 ) : ( (((DWORD)(mask)) == 0x00004000) ? ( 14 ) : ( (((DWORD)(mask)) == 0x00008000) ? ( 15 ) : ( (((DWORD)(mask)) == 0x00010000) ? ( 16 ) : ( (((DWORD)(mask)) == 0x00020000) ? ( 17 ) : ( (((DWORD)(mask)) == 0x00040000) ? ( 18 ) : ( (((DWORD)(mask)) == 0x00080000) ? ( 19 ) : ( (((DWORD)(mask)) == 0x00100000) ? ( 20 ) : ( (((DWORD)(mask)) == 0x00200000) ? ( 21 ) : ( (((DWORD)(mask)) == 0x00400000) ? ( 22 ) : ( (((DWORD)(mask)) == 0x00800000) ? ( 23 ) : ( (((DWORD)(mask)) == 0x01000000) ? ( 24 ) : ( (((DWORD)(mask)) == 0x02000000) ? ( 25 ) : ( (((DWORD)(mask)) == 0x04000000) ? ( 26 ) : ( (((DWORD)(mask)) == 0x08000000) ? ( 27 ) : ( (((DWORD)(mask)) == 0x10000000) ? ( 28 ) : ( (((DWORD)(mask)) == 0x20000000) ? ( 29 ) : ( (((DWORD)(mask)) == 0x40000000) ? ( 30 ) : ( (((DWORD)(mask)) == 0x80000000) ? ( 31 ) : ( 32 ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ))

/* use a BIG!!! macro */
static void t1 ( void ) {
    unsigned long long a, b;
    unsigned long res[5];
    int i;
    RDTSC(a);
    for ( i = 0 ; i < 5 ; i++ ) {
        res[i] = MASKBITN(samples[i]);
    }
    RDTSC(b);
    printf( "Time=%lld - ", b - a );
    for ( i = 0 ; i < 5 ; i++ ) {
        printf( "%d ", res[i] );
    }
    printf( "\n" );
}

static int maskbitn ( DWORD mask ) {
    int result = 0;
    while ( mask >>= 1 ) result++;
    return result;
}

/* use a function */
static void t2 ( void ) {
    unsigned long long a, b;
    unsigned long res[5];
    int i;
    RDTSC(a);
    for ( i = 0 ; i < 5 ; i++ ) {
        res[i] = maskbitn(samples[i]);
    }
    RDTSC(b);
    printf( "Time=%lld - ", b - a );
    for ( i = 0 ; i < 5 ; i++ ) {
        printf( "%d ", res[i] );
    }
    printf( "\n" );
}

static int table[256];
static void t3_setup ( void ) {
    int i;
    for ( i = 0 ; i < 256 ; i++ ) table[i] = maskbitn(i);
}
static int maskbitn_t3 ( DWORD mask ) {
    if ( mask & 0xff000000 ) {
        return 24 + table[ mask >>= 24 ];
    } else
    if ( mask & 0x00ff0000 ) {
        return 16 + table[ mask >>= 16 ];
    } else
    if ( mask & 0x0000ff00 ) {
        return 8 + table[ mask >>= 8 ];
    } else {
        return table[ mask ];
    }
}

/* use a lookup table */
static void t3 ( void ) {
    unsigned long long a, b;
    unsigned long res[5];
    int i;
    t3_setup();
    RDTSC(a);
    for ( i = 0 ; i < 5 ; i++ ) {
        res[i] = maskbitn_t3(samples[i]);
    }
    RDTSC(b);
    printf( "Time=%lld - ", b - a );
    for ( i = 0 ; i < 5 ; i++ ) {
        printf( "%d ", res[i] );
    }
    printf( "\n" );
}

#include <math.h>
#define MASKBITN_V(mask) ((mask & (mask - 1)) ? 32 : floor (log(mask) / log(2) + 0.5))
static void t4 ( void ) {
    unsigned long long a, b;
    unsigned long res[5];
    int i;
    t3_setup();
    RDTSC(a);
    for ( i = 0 ; i < 5 ; i++ ) {
        res[i] = MASKBITN_V(samples[i]);
    }
    RDTSC(b);
    printf( "Time=%lld - ", b - a );
    for ( i = 0 ; i < 5 ; i++ ) {
        printf( "%d ", res[i] );
    }
    printf( "\n" );
}

int main ( void ) {
    int i;
    /* run all tests a few times */
    for ( i = 0 ; i < 5 ; i++ ) {
        t1();
        t2();
        t3();
        t4();
        printf("\n");
    }
    return 0;
}

And results
Code: 
+ gcc hello.c -lm
+ ./a.out
Time=3216 - 0 12 15 16 31
Time=2200 - 0 12 15 16 31
Time=1112 - 0 12 15 16 31
Time=102668 - 0 12 15 16 31

Time=2756 - 0 12 15 16 31
Time=1916 - 0 12 15 16 31
Time=708 - 0 12 15 16 31
Time=13864 - 0 12 15 16 31

Time=2156 - 0 12 15 16 31
Time=1856 - 0 12 15 16 31
Time=708 - 0 12 15 16 31
Time=10680 - 0 12 15 16 31

Time=2088 - 0 12 15 16 31
Time=1988 - 0 12 15 16 31
Time=744 - 0 12 15 16 31
Time=11544 - 0 12 15 16 31

Time=1908 - 0 12 15 16 31
Time=1808 - 0 12 15 16 31
Time=496 - 0 12 15 16 31
Time=12496 - 0 12 15 16 31

+ gcc hello.c -O2 -lm
+ ./a.out
Time=1484 - 0 12 15 16 31
Time=1364 - 0 12 15 16 31
Time=612 - 0 12 15 16 31
Time=80648 - 0 12 15 16 31

Time=1220 - 0 12 15 16 31
Time=772 - 0 12 15 16 31
Time=452 - 0 12 15 16 31
Time=11812 - 0 12 15 16 31

Time=1312 - 0 12 15 16 31
Time=824 - 0 12 15 16 31
Time=448 - 0 12 15 16 31
Time=11572 - 0 12 15 16 31

Time=1216 - 0 12 15 16 31
Time=736 - 0 12 15 16 31
Time=448 - 0 12 15 16 31
Time=11084 - 0 12 15 16 31

Time=1324 - 0 12 15 16 31
Time=752 - 0 12 15 16 31
Time=432 - 0 12 15 16 31
Time=11728 - 0 12 15 16 31

If you're looking for outright performance, the look up table is the best approach.

Unless you want to go to ASM and use a BSF instruction :)

--
 
Upvote 0 Downvote
Thanks a lot for the effort. Indeed that t3() function with the lookup table is fastest. Especially the way t3() searches is very efficient.
Thanks for that BSF processor instruction, just looked it up in TASM reference; if only I knew that before :)
 
Upvote 0 Downvote
Status
Not open for further replies.

Similar threads

cloudytechi147
  • Locked
  • Question
How to solve the Sort and Combine problem
Replies
1
Views
107
mikrom
mikrom
Ethan1812
  • Locked
  • Question
Reading a number from a file and adding another number onto the file. 1
Replies
2
Views
116
Ethan1812
Ethan1812
negru
  • Locked
  • Question
C: Dynamic string using variable number of arguments
Replies
1
Views
117
xwb
xwb
fixerz
  • Locked
  • Question
how to read strings from the console ? 2
Replies
3
Views
148
tomdacat
tomdacat
borkut
  • Locked
  • Question
receiving strings from keyboard and storing base address in array of pointers...
Replies
9
Views
132
xwb
xwb

Part and Inventory Search

Sponsor

Back
Top