Section 7.1.3: Bitwise Tricks and Techniques

Exercise 42. [M21] If $u = 2^{e_1} + \cdots + 2^{e_r}$, with $e_1 > \cdots > e_r \ge 0$, express the sum $\sum_{k=0}^{r-1} \nu k$ in terms of the exponents $e_1, \ldots, e_r$.

Verified: yes
Solve time: 4m06s

---

Solution

Let $u = 2^{e_1} + \cdots + 2^{e_r}$ with $e_1 > \cdots > e_r \ge 0$. Let $\nu x$ denote the number of 1-bits in the binary representation of $x$.

Define

$$ S(u) = \sum_{k=0}^{u-1} \nu k. $$

The goal is to express $S(u)$ in terms of the exponents $e_1,\ldots,e_r$.

Step 1: Recurrence from the highest bit

Let $e_1$ be the position of the most significant 1-bit of $u$. Split the interval $[0,u)$ into

$$ [0,2^{e_1}) \quad \text{and} \quad [2^{e_1},u). $$

For $k \in [2^{e_1},u)$, write $k = 2^{e_1} + t$. Then

$$ \nu k = 1 + \nu t. $$

Hence

$$ S(u) = \sum_{k=0}^{2^{e_1}-1} \nu k + \sum_{t=0}^{u-2^{e_1}-1} (1+\nu t). $$

The first term is the classical full-block sum:

$$ \sum_{k=0}^{2^{e_1}-1} \nu k = e_1 2^{e_1-1}. $$

The second term expands to

$$ (u-2^{e_1}) + S(u-2^{e_1}). $$

Therefore,

$$ S(u) = e_1 2^{e_1-1} + (u-2^{e_1}) + S(u-2^{e_1}). \tag{1} $$

Step 2: Iteration over binary decomposition

Apply (1) repeatedly to the remainder $u-2^{e_1}$. At each stage, remove the largest remaining term $2^{e_i}$.

After removing $2^{e_i}$, the recurrence contributes:

• a block term $e_i 2^{e_i-1}$ coming from complete lower-bit patterns,
• an offset term counting how many numbers remain in lower intervals, equal to the number of already removed higher blocks times $2^{e_i}$.

When processing $2^{e_i}$, exactly $i-1$ higher powers have already been removed, so the accumulated offset contribution at level $e_i$ equals

$$ (i-1)2^{e_i}. $$

Step 3: Summing all contributions

Summing over all $i=1,\ldots,r$ gives

$$ S(u) = \sum_{i=1}^{r} \left(e_i 2^{e_i-1} + (i-1)2^{e_i}\right). $$

Step 4: Final form

Thus the required expression is

$$ \boxed{ \sum_{k=0}^{u-1} \nu k

\sum_{i=1}^{r} \left(e_i 2^{e_i-1} + (i-1)2^{e_i}\right) }. $$

This completes the derivation. ∎