7.2. The Power of Two

There are only 10 kinds of people in the world—those who know binary, and those who don’t. If you happen to get this joke, you probably know that computers operate using the binary (base-2) number system. Instead of decimal digits 0-9, each bit (binary digit) has only two possible values: 0 and 1. Binary representation of numbers gives some interesting properties that are widely explored in practice and makes it an interesting topic to test in interviews.

Power of 2

How do you determine whether an integer is a power of 2?

Solution: Any integer $x=2^n$ ($n\geq0$) has a single bit (the $(n+1)th$ bit from the right) set to 1. For example, $8\ (=2^3)$ is expressed as $0\cdots01000$. It is also easy to see that $2^n-1$ has all the $n$ bits from the right set to 1. For example, 7 is expressed as $0\cdots00111$. So $2^n$ and $2^n-1$ do not share any common bits. As a result, $x\mathbin{\&}(x-1)\mathrel{==}0$, where $\&$ is a bitwise AND operator, is a simple way to identify whether the integer $x$ is a power of 2.

Multiplication by 7

Give a fast way to multiply an integer by 7 without using the multiplication (*) operator?

Solution: $(\mathrm{x}\mathbin{<<}3)-\mathrm{x}$, where $\mathbin{<<}$ is the bit-shift left operator. $\mathrm{x}\mathbin{<<}3$ is equivalent to $\mathrm{x}\text{*}8$. Hence $(\mathrm{x}\mathbin{<<}3)-\mathrm{x}$ is $\mathrm{x}\text{*}7$.⁸

Probability simulation

You are given a fair coin. Can you design a simple game using the fair coin so that your probability of winning is $p,\ 0<p<1$?⁹

Solution: The key to this problem is to realize that $p\in(0,1)$ can also be expressed as a binary number and each digit of the binary number can be simulated using a fair coin. First, we can express the probability $p$ as binary number:

Then, we can start tossing the fair coin, and count heads as 1 and tails as 0. Let $s_i\in\{0,1\}$ be the result of the $i$-th toss starting from $i=1$. After each toss, we compare $p_i$ with $s_i$. If $s_i<p_i$, we win and the coin tossing stops. If $s_i>p_i$, we lose and the coin tossing stops. If $s_i=p_i$, we continue to toss more coins. Some $p$ values (e.g., 1/3) are infinite series when expressed as a binary number ($n\to\infty$). In these cases, the probability to reach $s_i\neq p_i$ is 1 as $i$ increases. If the sequence is finite, (e.g., 1/4=0.01) and we reach the final stage with $s_n=p_n$, we lose (e.g., for 1/4, only the sequence 00 will be classified as a win; all other three sequences 01, 10 and 11 are classified as a loss). Such a simulation will give us probability $p$ of winning.

Poisonous wine

You’ve got 1000 bottles of wines for a birthday party. Twenty hours before the party, the winery sent you an urgent message that one bottle of wine was poisoned. You happen to have 10 lab mice that can be used to test whether a bottle of wine is poisonous. The poison is so strong that any amount will kill a mouse in exactly 18 hours. But before the death on the 18th hour, there are no other symptoms. Is there a sure way that you can find the poisoned bottle using the 10 mice before the party?

Solution: If the mice can be tested sequentially to eliminate half of the bottles each time, the problem becomes a simple binary search problem. Ten mice can identify the poisonous bottle in up to 1024 bottles of wines. Unfortunately, since the symptom won’t show up until 18 hours later and we only have 20 hours, we cannot sequentially test the mice. Nevertheless, the binary search idea still applies. All integers between 1 and 1000 can be expressed in 10-bit binary format. For example, bottle 1000 can be labeled as 1111101000 since $1000=2^9+2^8+2^7+2^6+2^5+2^3$.

Now let mouse 1 take a sip from every bottle that has a 1 in the first bit (the lowest bit on the right); let mouse 2 take a sip from every bottle with a 1 in the second bit; …; and, finally, let mouse 10 take a sip from every bottle with a 1 in the 10th bit (the highest bit). Eighteen hours later, if we line up the mice from the highest to the lowest bit and treat a live mouse as 0 and a dead mouse as 1, we can easily back track the label of the poisonous bottle. For example, if the 6th, 7th, and 9th mice are dead and all others are alive, the line-up gives the sequence 0101100000 and the label for the poisonous bottle is $2^8+2^6+2^5=352$.