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 (6)

  1. Anonymous says:

    public static ulong ClearAllButHighestBit(ulong input) {

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

    }

  2. Anonymous says:

    public static double ClearAllButHighestBit2(ulong input) {

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

    }

  3. Anonymous says:

    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!

  4. Anonymous says:

    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;
    

    }

Skip to main content