CODEWITHSUNDEEP
cmacrosc-preprocessor
user2162449
user2162449

Reputation: 183

Given a bit mask, how to compute bit shift count

I'd like to have a function or (preferably) a macro that calculates the number of shifts required to obtain a certain bit mask.

Currently I do something like:

#define CURRBITMASK 0x30
#define CURRBITSHIFT 4

What I want to do:

#define BITMASK1 0x10
#define BITSHIFT1 GETSHIFT(BITMASK1) // 4 ; 0x10 = (0x1 << 4)

#define BITMASK2 0x18
#define BITSHIFT2 GETSHIFT(BITMASK2) // 3 ; 0x18 = (0x3 << 3)

#define BITMASK3 0xC0
#define BITSHIFT3 GETSHIFT(BITMASK3) // 6 ; 0xC0 = (0x3 << 6)

#define BITMASK4 0x40
#define BITSHIFT4 GETSHIFT(BITMASK3) // 6 ; 0x40 = (0x1 << 6)

Is there any way to obtain the required shift from the mask using a macro only? If not, is there a more optimal way to do it as a function than this?:

int get_shift(int bitmask) {
    int count = 0;
    while (bitmask & 0x1) {
        bitmask >>= 1;
        count++;
    }
    return count;
}

Upvotes: 6

Views: 2798

Answers (4)

Billy
Billy

Reputation: 320

Another option is the GCC built-in "find first set" functions, which return one plus the index of the least significant 1-bit in the argument (or 0 if it's 0).

// int __builtin_ffs(int);
// int __builtin_ffsl(long);
// int __builtin_ffsll(long long);
#define GETSHIFT(x) (__builtin_ffsll(x) - 1)

Linux uses it in the implementation of the FIELD_GET/PREP macros.

This works in both GCC and Clang. Based on my tests, if the argument is a constant then the result:

  • is evaluated at compile time, even at O0
  • appears to be treated as constant expression by the compiler, so you can use it to dimension a local array without accidentally creating a VLA (I wouldn't rely on this as it doesn't seem to be explicitly documented)
  • is not treated as a constant expression by the preprocessor, so it can't be used in #if and #elif directives.

In the future you will be able do something similar in any compiler that supports C23 by using the new stdc_first_trailing_one function.

Upvotes: 0

Hein Wessels
Hein Wessels

Reputation: 947

I have created a quick solution which does not need iterative steps. However, you never know the amount of bits to shift, rather the nth power of the shift. The shift is then done through multiplication/division, which the compiler will optimize as bits shifts.

#define BITS2SHIFT(mask)                (mask&-mask)
#define MOV2MASK(val,mask)              (val*BITS2SHIFT(mask))&mask 
#define MASK2VAL(val,mask)              (val&mask)/BITS2SHIFT(mask)

See this example on how to use it.

Upvotes: 1

R.. GitHub STOP HELPING ICE
R.. GitHub STOP HELPING ICE

Reputation: 215191

This answer to a question of mine gives a macro solution:

/* Number of bits in inttype_MAX, or in any (1<<b)-1 where 0 <= b < 3E+10 */
#define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
                  + (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

or if you want simpler and don't care about integers >2040-bit:

/* Number of bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 2040 */
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))

For your usage, the m you want to pass in is (x&-x)-1. x&-x strips off all but the lowest bit of x, yielding a power of two, and then subtracting 1 puts it in the right form for these macros.

The linked answer links to a usenet post on how it works.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726499

Your implementation is equivalent to counting the number of trailing zeros in a number.

There are several ways of doing this described here. One of the examples does this in seven steps for a 32-bit number:

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

Upvotes: 2

Related Questions