Welcome to MSDN Blogs Sign in | Join | Help

System.Blog.Martens.Ben

The Tech Blog of Ben Martens
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
…

Posted: Wednesday, April 30, 2008 4:27 PM by benmartens
Filed under:

Comments

Microsoft news and tips » Brain Teaser #2 said:

PingBack from http://microsoftnews.askpcdoc.com/brainteaser/brain-teaser-2

# April 30, 2008 8:33 PM

Raj Kaimal said:

public static ulong ClearAllButHighestBit(ulong input) {

ulong output = (input != 0)? 1UL : 0UL;

while (input > 1) {

input >>= 1;

output <<= 1;

};

return output;

}

# May 1, 2008 12:17 AM

Raj Kaimal said:

public static double ClearAllButHighestBit2(ulong input) {

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

}

# May 1, 2008 2:31 AM

BenM said:

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!

# May 5, 2008 12:53 AM

Raj Kaimal said:

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;

}

# May 5, 2008 10:17 PM

benmartens said:

You got it!

# May 6, 2008 12:20 PM
Leave a Comment

(required) 

(required) 

(optional)

(required) 

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Page view tracker