Share via

Brain Teaser #2 Answer

  • Article

Have read the question yet? Read it here.

  1. The problem is pretty simple if you have 00111 (where all the bits after the first 1 are also 1’s.) You shift right, run the NOT operator, and then AND that result with the original. For example:

        ORIGINAL = 00111 
   SHIFT RIGHT = 00011 
    NOT = 11100 
    AND with ORIGINAL = 00100

  2. The question now becomes, how can I take a number like 001xxxxxx and make sure all those subsequent values are 1? Well if you take 001xxx, shift right 1 and OR, you’ll have 0011xxx. Then shift right two and OR and you’ll have 001111x. Make sense? Shift by 4, then 8, then 16, 32, 64 and you’re done.

Here's the code:

 // Clears all the bits on the given value except 
// the leftmost bit that was set
static ulong KeepHighestSetBit(ulong value)
{
 value |= value>>1;
    value |= value>>2;
    value |= value>>4;

    value |= value>>8;
    value |= value>>16;
   value |= value>>32;
   return value & ~(value>>1);
}

Congrats to Raj Kaimal for figuring this out!