perror perror - 1 year ago 56
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
bitmask (0) = 0


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 ?


Answer Source

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
  mask_t full = - ((mask_t)1);
  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