Share via

Brain Teaser #2

  • Article

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!