Search code examples
c#bit-shiftbitunset

Unset All Bits Except Most Significant Bit C#

Is there a quick and easy way to unset all the bits in a number except the most significant bit? In other words I would like to take an integer x and apply & operator to it where the operand is 1 left-shifted by total number of bits in x. Example:

return UnsetAllBitsExceptMSB(400);

should return 256

Solution

  • Yes, there is a trick:

    private int UnsetAllBitsExceptMSB(int x)
{
  x |= x >> 16;
  x |= x >> 8;
  x |= x >> 4;
  x |= x >> 2;
  x |= x >> 1;
  x ^= x >> 1;
  return x;
}

    This works by first turning on all the bits to the right of the most significant set bit (00110000 becomes 001111111). It then uses XOR with the result right shifted one to turn all but the first bit off. (00111111 XOR with 00011111 = 00100000)

    There are other ways of doing this that will perform better in some circumstances, but this has a predictable performance no matter the input. (5 OR, 6 right shifts, and an XOR).