# Alternative solution: bitwise reconstruction. Fast and simple.

• This solution uses the guess API to build the solution bit by bit, starting from the most significant bit.

``````// Java/C++
int guessNumber(int n) {
int number = 0;
for (int bit = 1 << 30; true; bit >>= 1) {
switch (guess(bit | number)) {
case 0: return bit | number;
case 1: number |= bit; break;
default: break;
}
}
}
``````

Explanation:

• Even before the first iteration, iteration 1, it is certain that the first bit (sign) of the target is 0, since the target number is always positive.
• At the start of each iteration i, the first i bits of `number` correspond to the first i bits of the target number.
• At the end of each iteration i, the first i+1 bits of `number` correspond to the first i+1 bits of the target number.
• At some point in the loop, `bit` corresponds to the least significant 1 bit in the target number. At that point the function can return `number | bit`.
• This function requires at most a single shift, bitwise-or and assignment per iteration.

Benchmarks on my machine indicate that this approach is about twice as fast as an equivalent binary search implementation. Using n to determine the starting point of the loop only slowed it down, so I just ignored the parameter.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.