Setting all bits before first '1'

Question

Assume a 32-bit unsigned integer (answers generalizable to any size are of course better).

This integer can be assumed to be a power of 2, so only one bit is set. I want to set all bits in the integer, except those lower than the set bit. So (using 8-bit integers for brevity) 00001000 would become 11111000.

This could of course be accomplished by finding the one set bit and then iterating through the higher bits, setting them also. Assuming highest_set return the position of the highest set bit:

uint32_t f(uint32_t x)
{
  int n = highest_set(x);
  for (int i = 31; i != n; --i) {
      x |= 1 << i;
  }
  return x;
}

The runtime of f does however depend on the value of x, and I feel that there is a cleverer way of doing this.

Answer 1

Conceptually, an easy thing to do would be to take x-1 and then XOR it with 0xffffffff. Writing it as ~(x-1) as harold did in the comments below will handle different sized integers without having to change what you're XORing with.

Answer 2

shift right log(value), OR with Bitmask of 1's, shift left log(value). This should be a general solution with same running time for any input, no guarantees though.

Answer 3

You just need to take the two's complement

x = -x;

That works regardless of x is signed or unsigned

Why? Because what you're doing is essentially a quick way to convert a number to it's 2's complement

A shortcut to manually convert a binary number into its two's complement is to start at the least significant bit (LSB), and copy all the zeros (working from LSB toward the most significant bit) until the first 1 is reached; then copy that 1, and flip all the remaining bits

https://en.wikipedia.org/wiki/Two%27s_complement#Working_from_LSB_towards_MSB

You have only one bit set, so when you copy all the zero bits and invert the remaining zero bits you get its 2's complement. You can see it in your example: 00001000 = 8, 11111000 = -8. Some other examples:

00010000 = 16, 11110000 = -16
00100000 = 32, 11100000 = -32
01000000 = 64, 11000000 = -64

---

If x is a signed type then it's easy to understand. In case of unsigned types then there are obviously no negative values, so it works based on how the C standard defined unsigned operations

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

which is just another definition of 2's complement, because one greater than the largest value that can be represented by the resulting type (i.e. UINTN_MAX + 1 in this case) is 2^N. Negating an unsigned value always produce its two's complement in C even when the signed type is sign-magnitude or one's complement

Of course you can also cast it to a signed type x = -(int32_t)x; if you want to type more. You have another solution as well

x = ~x + 1; // by 2's complement definition

---

An easy to understand solution

while (!(x & 0x80000000))
    x |= x << 1;

This code doesn't need to loop constantly 32 times all the time as many of the solutions above

Answer 4

not sure how relevant this anser is, but have had luck with these ops... (!!n << 31) >> (n + ~0); left most bits set to 1 and right most 0, just depends on n, assuming 32 bit. could shift line by line for desired results too I think...

'int x=1;'
'x=x|(x<<4);'
'x=x|(x<<8);'
'x=x|(x<<16);'
'return x;'

Answer 5

uint32_t f(uint32_t x)
{
  bool bitset=false; //C++
  for (int i =0; i<sizeof(int); i++) {
     if(bitset) //After the first 1
        {  x |= 1 << i; } 
      else
        {
          if(x&(1<<i))
            bitset=true; //if 1 found then the flag is raised
        }

  }
  return x;
}