binaryintegerbit-manipulation

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.


Solution

  • 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.