perror - 1 year ago 65
C Question

Most efficient way to set n consecutive bits to 1?

I want to get a function that will set the

`n`
last bits of a numerical type to
`1`
. For example:

``````bitmask (5) = 0b11111 = 31
``````

I, first, had this implementation (
`mask_t`
is just a
`typedef`
around
`uint64_t`
):

``````mask_t bitmask (unsigned short n) {
return ((((mask_t) 1) << n) - 1;
}
``````

Everything is fine except when the function hit
`bitmask (64)`
(the size of
`mask_t`
), then I get
`bitmask (64) = 0`
in place of 64 bits set to
`1`
.

So, I have two questions:

1. Why do I have this behavior ? Pushing the
`1`
by 64 shifts on the left should clear the register and remain with
`0`
, then applying the
`-1`
should fill the register with
`1`
s...

2. What is the proper way to achieve this function ?

Yes this is a well known problem. There are easy ways to implement this function over the range 0..63 and over the range 1..64 (see below, #1), but 0..64 is more difficult (see even further below, #2)

#1

Based on inverting, shifting, and inverting again:

``````mask_t bitmask (unsigned short n) {
// pre: n in [1..64], n=0 acts like n=64
return ~(full << (n & 63));
}
``````

#2

Well of course you can just take either the "straight" or "inverted" mask generation and then special-case the "missing" `n`,

``````mask_t bitmask (unsigned short n) {
if (n == 64) return -((mask_t)1);
return (((mask_t) 1) << n) - 1;
}
``````

This tends to compile to a branch, though it technically doesn't have to.

You can do it without `if` (not tested)

``````mask_t bitmask (unsigned int n) {
mask_t x = (n ^ 64) >> 6;
return (x << (n & 63)) - 1;
}
``````

The idea here is that we're going to either shift 1 left by some amount the same as in your original code, or 0 in the case that `n = 64`. Shifting 0 left by 0 is just going to be 0 again, subtracting 1 sets all 64 bits.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download