In my booklet, *Algorithms via C#*, a way to make the computer guess the numbers more efficiently is presented (see pp. 12-13). Let’s quickly remind ourselves about the problem: we want to make the computer guess a number, between 0 to 100, with minimal amount of questions. It is concluded that we should start with **50**, then **25**, then** 12**, etc., that is, divide **100** by **2^k ** and depending on if the number is less than what computer guessed, we should either add or subtract this *factor*.

Everything is correct, but I would like to emphasize that this value can be computed without division.

**⌊100/2^1⌋ = 50 = (110010) _{2}**

**⌊100/2^2⌋ = 25 = (11001)**

_{2}**⌊100/2^3⌋= 12 = (1100)**

_{2}**⌊100/2^4⌋= 6 = (110)**

_{2}**⌊100/2^5⌋= 3 = (11)**

_{2}**⌊100/2^6⌋= 1 = (1)**

_{2}As you can see, in base 2, you simply remove the least significant bit each time. This might save time if you work in radix 2.

## Leave a Reply