CODEWITHSUNDEEP
cbit-manipulation
Subway
Subway

Reputation: 5716

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

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

Upvotes: 7

Views: 10693

Answers (7)

Subway
Subway

Reputation: 5716

OK, I'm taking up the gauntlet that @JohnZwinck has thrown towards me.

How about: return (to<32 ? (1<<to) : 0) - (1<<from);

Of course this is without fully checking for validity of from and to.

Edited according to @JosephQuinsey comments.

Upvotes: 4

abelenky
abelenky

Reputation: 64682

Here's my answer. (updated)

unsigned int SetBits(int from, int to)
{    
    return (UINT_MAX >> (CHAR_BIT*sizeof(int)-to)) & (UINT_MAX << (from-1));
}

SetBits(9,16); ==> 0b 1111 1111 0000 0000

SetBits(1,1); ==> 0b 0000 0001  // Just Bit #1
SetBits(5,5); ==> 0b 0001 0000  // Just Bit #5
SetBits(1,4); ==> 0b 0000 1111  // Bits #1, #2, #3, and #4 (low 4 bits) 
SetBits(1,32); ==> 0b 1111 1111 1111 1111  // All Bits

However, SetBits(0,0); does NOT work for turning all bits off.

My assumptions:

  • Bits are 1-based, starting from the right.
  • Bytes are 8-bits.
  • Ints can be any size (16, 32 or 64 bit). sizeof(int) is used.
  • No checking is done on from or to; caller must pass proper values.

Upvotes: 1

user207064
user207064

Reputation: 665

Can be done in this way as well, pow can be implemented using shift operations.

{
    unsigned int i =0;
    i = pow(2, (to-from))-1;
    i = i <<from;
    return i;
}

Upvotes: 0

user555045
user555045

Reputation: 64904

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.

Upvotes: 6

Lundin
Lundin

Reputation: 213573

A common way to do this somewhat efficiently would be this:

uint32_t set_bits_32 (uint32_t data, uint8_t offset, uint8_t n)
{
  uint32_t mask = 0xFFFFFFFF >> (32-n);

  return data | (mask << offset);
}

Upvotes: 5

Ferenc Deak
Ferenc Deak

Reputation: 35408

maybe: (( 1 << to ) - (1 << from)) | (1 << to)

This will also set the to and from bits as requested

Upvotes: 1

Aleksei Petrenko
Aleksei Petrenko

Reputation: 7168

I'd go with something like that:

int answer = 0;
unsigned i = from;
for (; i <= to; ++i)
  answer |= (1 << i);

return answer;

Easy to implement & readable.

I think that the fastest way would be to pre-calculate all possible values (from (0, 0) to (32, 32), if you know that you'll use this only for 32-bit integers). In fact there are about 1000 of them.

Then you'll end up with O(1) solution:

answer = precalcTable[from][to];

Upvotes: 3

Related Questions