Algorithm to generate bit mask

Alphaneo picture Alphaneo · Sep 8, 2009 · Viewed 55.8k times · Source

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

John Gietzen picture John Gietzen · Sep 8, 2009

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'.