TAOCP 7.1.1 Exercise 29
Let v_1<v_2<\cdots<v_m be the given increasing sequence of $n$-bit integers, and let $j$ be fixed.
Exercise 29. [22] $[22]$ (The next several exercises are devoted to algorithms that deal with the implications of Boolean functions by representing points of the $n$-cube as $n$-bit numbers $(b_{n-1} \ldots b_1 b_0)$. Given a bit position $j$, and given $n$-bit values $v_1 < v_2 < \cdots < v_m$, explain how to find all pairs $(k, k')$ such that $0 \le k < k' \le m$, in increasing order of $k$. The running time of your procedure should be $O(m)$, if bitwise operations on $n$-bit words take constant time.
Verified: no
Solve time: 28s
Solution
Let
$$ v_1<v_2<\cdots<v_m $$
be the given increasing sequence of $n$-bit integers, and let $j$ be fixed. Write
$$ \operatorname{lo}(v)=v\bmod 2^j,\qquad \operatorname{hi}(v)=v\gg (j+1), $$
where $\gg$ denotes a right shift. Thus
$$ v=(\operatorname{hi}(v),b_j,\operatorname{lo}(v)), $$
where $b_j$ is the bit in position $j$.
The desired pairs are those for which $v_k$ and $v_{k'}$ differ only in bit $j$. Equivalently,
$$ \operatorname{hi}(v_k)=\operatorname{hi}(v_{k'}),\qquad \operatorname{lo}(v_k)=\operatorname{lo}(v_{k'}),\qquad b_j(v_k)\ne b_j(v_{k'}). $$
Define the key
$$ r(v)=\bigl(\operatorname{hi}(v),\operatorname{lo}(v)\bigr), $$
which is obtained by deleting bit $j$ from the binary representation of $v$.
Since the sequence $v_1,\ldots,v_m$ is increasing, the sequence of keys $r(v_1),\ldots,r(v_m)$ is nondecreasing. Indeed, deleting one bit from two binary numbers preserves their lexicographic order. Hence equal keys occur consecutively.
The algorithm scans the list once.
Set $k=1$.
While $k\le m$, let
$$ r=r(v_k). $$
If $b_j(v_k)=0$, store the index $k$; otherwise no such index is stored.
Advance through all consecutive entries having key $r$. If one entry with bit $0$ and one entry with bit $1$ occur, output their indices. Then continue with the next key.
The correctness proof is immediate from the structure of the keys. Every output pair has identical values of $\operatorname{hi}$ and $\operatorname{lo}$, hence the corresponding numbers differ only in bit $j$. Conversely, if two numbers differ only in bit $j$, they have the same key $r$, therefore they belong to the same consecutive block. A block can contain at most two elements, because fixing all bits except $j$ leaves exactly the two values obtained by setting bit $j$ to $0$ or $1$. Thus every valid pair is found exactly once.
The output order is increasing in $k$. The blocks are processed from left to right, and the first index of each block is the smaller member of its pair whenever the pair exists.
The running time is $O(m)$. Each element is examined exactly once, each key comparison is performed once while advancing through the scan, and each valid pair is output once. The assumption that bitwise operations on $n$-bit words take constant time makes the computation of $\operatorname{hi}(v)$, $\operatorname{lo}(v)$, and bit $j$ constant-time operations. Therefore the total running time is
$$ \boxed{O(m)}. $$