Brain Teaser #2

This brain teaser comes courtesy of a co-worker named Simeon Cran.

Using C# and no branches, and no method calls, no allocations, and no unsafe code, write a method that takes a ulong and clears all the bits in it except the highest bit that was set. Use as few operations as possible.

e.g.:
0 -> 0
1 -> 1
2 -> 2
3 -> 2
4 -> 4
5 -> 4
6 -> 4
7 -> 4
8 -> 8
9 -> 8
10 -> 8
…

Comments

• Anonymous
  April 30, 2008
  The comment has been removed
• Anonymous
  April 30, 2008
  public static ulong ClearAllButHighestBit(ulong input) {

  ulong output = (input != 0)? 1UL : 0UL;while (input > 1) {    input >>= 1;    output <<= 1;};return output;

  }
• Anonymous
  April 30, 2008
  public static double ClearAllButHighestBit2(ulong input) {

  return Math.Pow(2, Math.Floor(Math.Log(input) / Math.Log(2)));

  }
• Anonymous
  May 04, 2008
  Thanks for the comments, but these are both incorrect. The first answer uses a branch for the while loop and the second one uses method calls. The instructions say no branches and no method calls. Keep trying!
• Anonymous
  May 05, 2008
  Grr..are we there yet?public static ulong ClearAllButHighestBit3(ulong input) {

  input |= input >> 1;input |= input >> 2;input |= input >> 4;input |= input >> 8;input |= input >> 16;input |= input >> 32;input ^= input >> 1; // :-)return input;

  }
• Anonymous
  May 06, 2008
  You got it!