C: Most efficient way to set all bits in a range within a variable

Question

Let's take int as an example:

int SetBitWithinRange(const unsigned from, const unsigned to)
{
    //To be implemented 
} 

SetBitWithinRange is supposed to return an intin which all and only the bits starting at bit from to bit to are set, when from is smaller than to and both are in the range of 0 to 32.

e.g.: int i = SetBitWithinRange(2,4) will result in i having the value of 0b00...01100

Answer 1

Here are some ways. First, some variants of "set n bits, then shift by from". I'll answer in C# though, I'm more familiar with it than I am with C. Should be easy to convert.

uint nbits = 0xFFFFFFFFu >> -(to - from);
return nbits << from;

Downside: can't handle an empty range, ie the case where to <= from.

uint nbits = ~(0xFFFFFFFFu << (to - from));
return nbits << from;

Upside: can handle the case where to = from in which case it will set no bits.
Downside: can't handle the full range, ie setting all bits.

It should be obvious how these work.

Alternatively, you can use the "subtract two powers of two" trick,

(1u << to) - (1u << from)

Downside: to can not be 32, so you can never set the top bit.

Works like this:

01000000
  ^^^^^^ "to" zeroes
     100
      ^^ "from zeroes"
-------- -
00111100

To the right of the 1 in the "from" part, it's just zeroes being subtracted from zeroes. Then at the 1 in the "from" part, you will either subtract from a 1 (if to == from) and get 0 as a result, or you'll subtract a 1 from a 0 and borrow all the way to the 1 in the to part, which will be reset.

All true bitwise methods that have been proposed at the time of writing have one of those downsides, which raises the question: can it be done without downsides?

The answer is, unfortunately, disappointing. It can be done without downsides, but only by

1. cheating (ie using non-bitwise elements), or
2. more operations than would be nice, or
3. non-standard operations

To give an example of 1, you can just pick any of the previous methods and add a special case (with an if or ternary operator) to work around their downside.

To give an example of 2: (not tested)

uint uppermask = (((uint)to >> 5) ^ 1) << to;
return uppermask - (1u << from);

The uppermask either takes a 1 and shifts it left by to (as usual), or it takes a 0 and shifts it left (by an amount that doesn't matter, since it's 0 that's being shifted), if to == 32. But it's kind of weird and uses more operations.

To give an example of 3, shifts that give zero when you shift by the operand size or more would solve this very easily. Unfortunately, that kind of shift isn't too common.