Create a mask that marks the most significant set bit, using only bitwise operators

Question

This was part of a larger programming assignment that was due for me last night. Couldn't figure out this problem, but I'm curious as to how it could be solved.

The function int greatestBitPos(int x) should return an int mask that marks the position of the most significant bit. If x==0, return 0. No control structures (if, while, ?:) allowed.

Example: greatestBitPos(96) = 0x40

Legal operators: ! ~ & ^ | + << >> =

This website on bit twiddling is something I used as a starting point, especially the second algorithm. However, it uses < comparisons, something this problem doesn't allow.

All ideas are welcome, thanks!

Edit: Please assume 2's complement, 32-bit integers. For all negative numbers, they have their topmost bit set, so the return value should be 0x80000000.

Answer 1

I'm still interested to see what other people can come up with, but a friend has figured out the answer.

int greatestBitPos(int x) {
  int a = x | (x >> 1);
  a = a | (a >> 2);
  a = a | (a >> 4);
  a = a | (a >> 8);
  a = a | (a >> 16);
  return ((a ^ (a >> 1)) | 0x80 << 24) & a;
}

Knowing that if we can set all bits to the right of the MSB to 1, then it becomes easy to just set the MSB and no other bits. This answer also works with negatives (with regards to twos-complement).