CODEWITHSUNDEEP
binaryintegerbit-manipulation
Viktor Dahl
Viktor Dahl

Reputation: 1990

Setting all bits before first '1'

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.

Upvotes: 3

Views: 2414

Answers (5)

phuclv
phuclv

Reputation: 41764

In case of only one bit set like yours, you just need to take the two's complement

x = -x;

That works regardless of x is signed or unsigned. You can see it in your example: 00001000 = 8, 11111000 = -8. Some other examples:

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

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.

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 2N. 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

Upvotes: 0

David
David

Reputation: 1419

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.

Upvotes: 4

scky1
scky1

Reputation: 1

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;'

Upvotes: -1

user1655481
user1655481

Reputation: 376

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;
}

Upvotes: -1

Stu
Stu

Reputation: 109

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.

Upvotes: 1

Related Questions