TAOCP 7.1.3 Exercise 44

Let $x = \sum_{j \ge 0} x_j 2^j$ with $x_j \in {0,1}$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 44. ▶ [23] (E. Freed, 1983.) What's a fast way to evaluate the weighted bit sum $\sum j x_j$?

Verified: yes
Solve time: 5m02s

Solution

Let $x = \sum_{j \ge 0} x_j 2^j$ with $x_j \in {0,1}$. Write the set of indices of 1-bits in increasing order as $e_1 < e_2 < \cdots < e_r$. Then

$\sum_j j x_j = \sum_{k=1}^r e_k.$

The goal is to compute this sum using bit operations faster than scanning all bit positions.

Consider the standard identity from 2-adic arithmetic,

$x ,&, (-x) = x ,&, (\bar{x} + 1),$

which isolates the lowest set bit of $x$. Let $t = x ,&, (-x)$. If $t \ne 0$, then $t = 2^k$ where $k$ is the smallest index such that $x_k = 1$.

To justify this, write $x = u 2^{k+1} + 2^k$ where $u$ is an integer representing higher bits. Then $\bar{x} + 1$ flips all bits below position $k$ and complements the prefix; multiplying bitwise with $x$ leaves only the $2^k$ position, since every lower bit of $x$ is $0$ and bit $k$ of both $x$ and $-x$ is $1$. Hence $x ,&, (-x) = 2^k$.

Define an iterative process:

$x^{(0)} = x,$

and for each step where $x^{(i)} \ne 0$,

$t_i = x^{(i)} ,&, (-x^{(i)}), \qquad x^{(i+1)} = x^{(i)} - t_i.$

Each $t_i$ is a distinct power of two corresponding to one 1-bit of $x$, since subtracting $t_i$ clears exactly the lowest set bit and leaves higher bits unchanged. This follows from $t_i \subseteq x^{(i)}$ and the identity $x - (x ,&, (-x))$ removes the least significant 1-bit while preserving all higher bits.

Let $t_i = 2^{k_i}$. Then $k_i$ must be recovered from $t_i$. Since $t_i - 1 = 2^{k_i} - 1$, its binary representation has exactly $k_i$ ones in the lowest positions and zeros elsewhere, hence

$\mathrm{popcount}(t_i - 1) = k_i.$

Therefore the weighted bit sum satisfies

$\sum_j j x_j = \sum_i k_i = \sum_i \mathrm{popcount}(t_i - 1).$

The algorithm becomes

$S \leftarrow 0,$

$\text{while } x \ne 0:\quad t \leftarrow x ,&, (-x),\quad S \leftarrow S + \mathrm{popcount}(t-1),\quad x \leftarrow x - t.$

Correctness follows because each iteration removes exactly one distinct 1-bit of $x$ and contributes exactly its index to $S$, so after all bits are removed, every term $j x_j$ has been accounted for exactly once, and no other contributions occur.

The result is

$\boxed{S = \sum_j j x_j}.$