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.