Given a bit mask, how to compute bit shift count

Question

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;
}

score 2 · Answer 1 · answered Jul 24 '15 at 02:31

2

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;

answered Jul 24 '15 at 02:31

Sergey Kalinichenko

714,442
84
1,110
1,523

Alternatively, `v &= -signed(v);` could also be `v &= ~v + 1;` – Dmitri Jul 24 '15 at 03:08
@Dmitri: Rather it should just be `v &= -v;` Converting to `signed` at best does nothing and at worst breaks the code (on implementations with strange implementation-defined conversions from unsigned to signed). – R.. GitHub STOP HELPING ICE Jul 24 '15 at 03:11
@R.. but `v &= ~v + 1;` doesn't convert to signed (`v` was unsigned already) – Dmitri Jul 24 '15 at 03:14
@Dmitri: Indeed, for unsigned either form is identical. I prefer `-v`, but `~v+1` is the same thing. – R.. GitHub STOP HELPING ICE Jul 24 '15 at 03:14

score 1 · Answer 2 · edited May 23 '17 at 11:52

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.

score 1 · Answer 3 · answered Jul 05 '18 at 14:18

1

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.

answered Jul 05 '18 at 14:18

Hein Wessels

937
5
15

I am not sure this works for masks of all zero. That or I am using it incorrectly. – TafT Sep 25 '18 at 09:37
A mask requires `1`s, otherwise it is not a mask? For example placing `01` at mask `00110000` would result `00010000`. A mask of `00000000` would result in zero, which I'm sure this code will do. Or are using masks in other ways? – Hein Wessels Sep 25 '18 at 10:01
A mask of all 0 can be a suppression. I am using it in the way you state. I am starting to suspect an issue with either my test or make system as some of my unexpected behaviour seems to go away on a clean build. However a mask of 0b00000001 requires a shift of 0 and this seems to return 1 from BITS2SHIFT, which I think is what you are outlining in the answer but the MACRO name is confusing. – TafT Sep 25 '18 at 10:25
2

Yeah, that name is slightly ambigious. It's actually a multiplier, and 0 bitshift is multiplying by 1. And a zero mask should suppress, due to the `&mask` – Hein Wessels Sep 25 '18 at 10:35
1

I think the name + having a cold + having to think in binary and hex math for the first time in a few months is enough to throughly confuse me :-P Thank you for clarifying that what I think is going on is going on. – TafT Sep 25 '18 at 10:38

score 0 · Answer 4 · answered Feb 14 '23 at 10:44

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.

Given a bit mask, how to compute bit shift count

4 Answers4