Algorithm to generate bit mask

user_70702 0
Viewed 76538

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 ~~~

bit-manipulation c algorithm
9 Answers

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.

user_4153070

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

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.

user_9095650

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

user_27789210
Related