Algorithm to generate bit mask

Question

I was facing this unique problem of generating a bit-mask based on the input parameter. For example,

if param = 2, then the mask will be 0x3 (11b) if param = 5, then the mask will be 0x1F (1 1111b)

This I implemented using a for-loop in C, something like

int nMask = 0;
for (int i = 0; i < param; i ++) {

    nMask |= (1 << i);
}

I would like to know if there is a better algorithm ~~~

Answer 1

One thing to notice about bitmasks like that is that they are always one less than a power of two.

The expression 1 << n is the easiest way to get the n-th power of two.

You don't want Zero to provide a bitmask of 00000001, you want it to provide zero. So you need to subtract one.

mask = (1 << param) - 1;

Edit:

If you want a special case for param > 32:

int sizeInBits = sizeof(mask) * BITS_PER_BYTE; // BITS_PER_BYTE = 8;
mask = (param >= sizeInBits ? -1 : (1 <<  param) - 1);

This method should work for 16, 32, or 64 bit integers, but you may have to explicitly type the '1'.

Answer 2

Efficient, Branch-Free, Portable and Generic (but Ugly) Implementation

C:

#include <limits.h>     /* CHAR_BIT */

#define BIT_MASK(__TYPE__, __ONE_COUNT__) \
    ((__TYPE__) (-((__ONE_COUNT__) != 0))) \
    & (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__)))

C++:

#include <climits>

template <typename R>
static constexpr R bitmask(unsigned int const onecount)
{
//  return (onecount != 0)
//      ? (static_cast<R>(-1) >> ((sizeof(R) * CHAR_BIT) - onecount))
//      : 0;
    return static_cast<R>(-(onecount != 0))
        & (static_cast<R>(-1) >> ((sizeof(R) * CHAR_BIT) - onecount));
}

Usage (Producing Compile Time Constants)

BIT_MASK(unsigned int, 4) /* = 0x0000000f */

BIT_MASK(uint64_t, 26) /* = 0x0000000003ffffffULL */

Example

#include <stdio.h>

int main()
{
    unsigned int param;
    for (param = 0; param <= 32; ++param)
    {
        printf("%u => 0x%08x\n", param, BIT_MASK(unsigned int, param));
    }
    return 0;
}

Output

0 => 0x00000000
1 => 0x00000001
2 => 0x00000003
3 => 0x00000007
4 => 0x0000000f
5 => 0x0000001f
6 => 0x0000003f
7 => 0x0000007f
8 => 0x000000ff
9 => 0x000001ff
10 => 0x000003ff
11 => 0x000007ff
12 => 0x00000fff
13 => 0x00001fff
14 => 0x00003fff
15 => 0x00007fff
16 => 0x0000ffff
17 => 0x0001ffff
18 => 0x0003ffff
19 => 0x0007ffff
20 => 0x000fffff
21 => 0x001fffff
22 => 0x003fffff
23 => 0x007fffff
24 => 0x00ffffff
25 => 0x01ffffff
26 => 0x03ffffff
27 => 0x07ffffff
28 => 0x0fffffff
29 => 0x1fffffff
30 => 0x3fffffff
31 => 0x7fffffff
32 => 0xffffffff

Explanation

First of all, as already discussed in other answers, >> is used instead of << in order to prevent the problem when the shift count is equal to the number of bits of the storage type of the value. (Thanks Julien's answer above for the idea)

For the ease of discussion, let's "instantiate" the macro with unsigned int as __TYPE__ and see what happens (assuming 32-bit for the moment):

((unsigned int) (-((__ONE_COUNT__) != 0))) \
& (((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))

Let's focus on:

((sizeof(unsigned int) * CHAR_BIT)

first. sizeof(unsigned int) is known at compile time. It is equal to 4 according to our assumption. CHAR_BIT represents the number of bits per char, a.k.a. per byte. It is also known at compile time. It is equal to 8 on most machines on the Earth. Since this expression is known at a compile time, the compiler would probably do the multiplication at compile time and treat it as a constant, which equals to 32 in this case.

Let's move to:

((unsigned int) -1)

It is equal to 0xFFFFFFFF. Casting -1 to any unsigned type produces a value of "all-1s" in that type. This part is also a compile time constant.

Up to now, the expression:

(((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))

is in fact the same as:

0xffffffffUL >> (32 - param)

which is the same as Julien's answer above. One problem with his answer is that if param is equal to 0, producing the expression 0xffffffffUL >> 32, the result of the expression would be 0xffffffffUL, instead of the expected 0! (That's why I name my parameter as __ONE_COUNT__ to emphasize its intention)

To solve this problem, we could simply add a special case for __ONE_COUNT equals 0 using if-else or ?:, like this:

#define BIT_MASK(__TYPE__, __ONE_COUNT__) \
    (((__ONE_COUNT__) != 0) \
    ? (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__)))
    : 0)

But branch-free code is cooler, isn't it?! Let's move to the next part:

((unsigned int) (-((__ONE_COUNT__) != 0)))

Let's start from the innermost expression to the outermost. ((__ONE_COUNT__) != 0) produces 0 when the parameter is 0, or 1 otherwise. (-((__ONE_COUNT__) != 0)) produces 0 when the parameter is 0, or -1 otherwise. For ((unsigned int) (-((__ONE_COUNT__) != 0))), the type-cast trick ((unsigned int) -1) is already explained above. Do you notice the trick now? The expression:

((__TYPE__) (-((__ONE_COUNT__) != 0)))

equals to "all-0s" if __ONE_COUNT__ is zero, and "all-1s" otherwise. It acts as a bit-mask for the value we calculated in the first step. So, if __ONE_COUNT__ is non-zero, the mask as no effect and it is the same as Julien's answer. If __ONE_COUNT__ is 0, it mask away all bits of Julien's answer, producing a constant zero. To visualize, watch this:

__ONE_COUNT__ :                           0                Other
                                          -------------    --------------
(__ONE_COUNT__)                           0 = 0x000...0    (itself)
((__ONE_COUNT__) != 0)                    0 = 0x000...0     1 = 0x000...1
((__TYPE__) (-((__ONE_COUNT__) != 0)))    0 = 0x000...0    -1 = 0xFFF...F

Answer 3

Alternatively, you can use a right shift to avoid the issue mentioned in the (1 << param) - 1 solution.

unsigned long const mask = 0xffffffffUL >> (32 - param);

assuming that param <= 32, of course.

Answer 4

For those interested, this is the lookup-table alternative discussed in comments to the other answer - the difference being that it works correctly for a param of 32. It's easy enough to extend to the 64 bit unsigned long long version, if you need that, and shouldn't be significantly different in speed (if it's called in a tight inner loop then the static table will stay in at least L2 cache, and if it's not called in a tight inner loop then the performance difference won't be important).

unsigned long mask2(unsigned param)
{
    static const unsigned long masks[] = {
        0x00000000UL, 0x00000001UL, 0x00000003UL, 0x00000007UL,
        0x0000000fUL, 0x0000001fUL, 0x0000003fUL, 0x0000007fUL,
        0x000000ffUL, 0x000001ffUL, 0x000003ffUL, 0x000007ffUL,
        0x00000fffUL, 0x00001fffUL, 0x00003fffUL, 0x00007fffUL,
        0x0000ffffUL, 0x0001ffffUL, 0x0003ffffUL, 0x0007ffffUL,
        0x000fffffUL, 0x001fffffUL, 0x003fffffUL, 0x007fffffUL,
        0x00ffffffUL, 0x01ffffffUL, 0x03ffffffUL, 0x07ffffffUL,
        0x0fffffffUL, 0x1fffffffUL, 0x3fffffffUL, 0x7fffffffUL,
        0xffffffffUL };

    if (param < (sizeof masks / sizeof masks[0]))
        return masks[param];
    else
        return 0xffffffffUL; /* Or whatever else you want to do in this error case */
}

It's worth pointing out that if you need the if() statement (because are worried that someone might call it with param > 32), then this doesn't win you anything over the alternative from the other answer:

unsigned long mask(unsigned param)
{
    if (param < 32)
        return (1UL << param) - 1;
    else
        return -1;
}

The only difference is that the latter version has to special case param >= 32, whereas the former only has to special case param > 32.

Answer 5

How about this (in Java):

int mask = -1;
mask = mask << param;
mask = ~mask;

This way you can avoid lookup tables and hard coding the length of an integer.

Explanation: A signed integer with a value of -1 is represented in binary as all ones. Shift left the given number of times to add that many 0's to the right side. This will result in a 'reverse mask' of sorts. Then negate the shifted result to create your mask.

This could be shortened to:

int mask = ~(-1<<param);

An example:

int param = 5;
int mask = -1;        // 11111111 (shortened for example)
mask = mask << param; // 11100000
mask = ~mask;         // 00011111

Answer 6

From top of my head. Sorry, I'm on mobile. I assume a 64 bit type for clarity, but this can be easily generalized.

(((uint64_t) (bits < 64)) << (bits & 63)) - 1u

It's the typical (1 << bits) - 1 but branchless, with no undefined behavior, with the & 63 optimizable away on some platforms and with correct results for the whole range of values.

The left (left) shift operand becomes 0 for shifts bigger or equal than the type width.

The right (left) shift operand is masked to avoid undefined behavior, the value will never get bigger than 63. This is just to make compilers and language lawyers happy, as no platform will be adding ones when the left operand is already zero (for values bigger than 63). A good compiler should remove the & 63 masking on platforms where this is already the behavior of the underlying instruction (e.g. x86).

As we have seen, values bigger than 63 get a result of 0 from the shift, but there is a substraction by one afterwards leaving all bits set by an unsigned integer underflow, which is not undefined behavior on unsigned types.

Answer 7

If you're worried about overflow in a C-like language with (1 << param) - 1 (when param is 32 or 64 at the max size type the mask becomes 0 since bitshift pushes past the bounds of type), one solution I just thought of:

const uint32_t mask = ( 1ul << ( maxBits - 1ul ) ) | ( ( 1ul << ( maxBits - 1ul ) ) - 1ul );

Or another example

const uint64_t mask = ( 1ull << ( maxBits - 1ull ) ) | ( ( 1ull << ( maxBits - 1ull ) ) - 1ull );

Here's a templatized version, keep in mind that you should use this with an unsigned type R:

#include <limits.h>     /* CHAR_BIT */

// bits cannot be 0
template <typename R>
static constexpr R bitmask1( const R bits )
{
    const R one = 1;
    assert( bits >= one );
    assert( bits <= sizeof( R ) * CHAR_BIT );
    const R bitShift = one << ( bits - one );
    return bitShift | ( bitShift - one );
}

Let's say max bits is 8 with a byte, with the first overflowing function we'd have 1 << 8 == 256, which when cast to byte becomes 0. With my function we have 1 << 7 == 128, which a byte can contain, so becomes 1<<7 | 1<<7 - 1.

I haven't compiled the function, so it may contain typos.

---

And for fun here's Julien Royer's fleshed out:

// bits can be 0
template <typename R>
static constexpr R bitmask2( const R bits )
{
    const R zero = 0;
    const R mask = ~zero;
    const R maxBits = sizeof( R ) * CHAR_BIT;
    assert( bits <= maxBits );
    return mask >> ( maxBits - bits );
}

Answer 8

For a 32-bit mask you can use this (use uint64_t for a 64-bit mask):

#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int
main()
{
    size_t n = 8;
    assert(n <= 32);
    uint32_t mask = ~(uint32_t)0 >> (32 - n);

    printf("mask = %08" PRIX32 "\n", mask);
}

I know it's an answer to a very old post. But in case some human being actually reads this: I would welcome any feedback.

Answer 9

Just for reference (google), I used the following to get an all 1 mask for for integral types.
In C++ one might simply use:

std::numeric_limits<uint_16t>::max() // 65535