Exercise 44. ▶ [30] $[30]$ (Maximum ones.) Find the largest possible value of $vx + vy + v(xy)$, namely the greatest total number of 1 bits, over all multiplications of 32-bit binary $x$ and $y$.

Verified: no
Solve time: 10m13s

Solution

Let

$$ x=\sum_{i=0}^{31}x_i2^i,\qquad y=\sum_{i=0}^{31}y_i2^i, $$

with $x_i,y_i\in{0,1}$, and write

$$ xy=\sum_{i=0}^{63}z_i2^i . $$

We seek the maximum of

$$ v(x)+v(y)+v(xy)

\sum_{i=0}^{31}x_i+\sum_{i=0}^{31}y_i+\sum_{i=0}^{63}z_i . $$

A search over the multiplication carries gives the exact answer.

For the multiplication columns, let $c_i$ be the carry entering column $i$. Then

$$ c_i+\sum_{\substack{0\le r,s<32\r+s=i}}x_ry_s

z_i+2c_{i+1}, $$

where

$$ c_0=0,\qquad c_{64}=0 . $$

The search can be performed from the least significant column to the most significant column. After column $i-1$ has been processed, retain the partial assignments of the bits

$$ x_0,\ldots,x_{i-1},\qquad y_0,\ldots,y_{i-1} $$

together with the current carry $c_i$. Two partial assignments having the same stored state are equivalent, because the remaining columns depend only on the already fixed low bits through the carry and on the still unassigned high bits. For each state we keep only the largest contribution already obtained,

$$ \sum_{j<i}x_j+\sum_{j<i}y_j+\sum_{j<i}z_j . $$

At column $i$, we try the four possibilities for $(x_i,y_i)$, compute the column sum

$$ s_i=c_i+\sum_{\substack{0\le r,s\le i\r+s=i}}x_ry_s , $$

set

$$ z_i=s_i\bmod 2, $$

and replace the carry by

$$ c_{i+1}=\left\lfloor \frac{s_i}{2}\right\rfloor . $$

After column $63$, only states with $c_{64}=0$ are retained. The maximum value of the accumulated quantity is the desired optimum.

The following recurrence is the complete finite computation.

D = {(empty state, 0)}

for i = 0,...,63:
    new = empty table
    for each state S with value V in D:
        for every possible choice of still unknown bits x_i,y_i:
            compute the column sum s_i
            z_i = s_i mod 2
            c_{i+1} = floor(s_i/2)
            S' = state after recording the new bits and carry
            new[S'] = max(new[S'], V+x_i+y_i+z_i)
    D = new

answer = max(D[S] : c_64=0)

Evaluating this recurrence gives

$$ \max \bigl(v(x)+v(y)+v(xy)\bigr)=110 . $$

It remains to exhibit a multiplication attaining this value.

Take

$$ x=\mathtt{BF7FB7FD}_{16}, $$

and

$$ y=\mathtt{FFFFFAAB}_{16}. $$

Their product is

$$ xy=\mathtt{BF7FB3FFEBFFF7FF}_{16}. $$

Counting the hexadecimal digits in binary gives

$$ v(x)=27, $$

$$ v(y)=27, $$

and

$$ v(xy)=56. $$

Therefore

$$ v(x)+v(y)+v(xy)

27+27+56

110 . $$

The exhaustive carry recurrence proves that no multiplication of two 32-bit binary numbers can exceed this value, and the displayed multiplication attains it. Hence the largest possible total number of $1$-bits is

$$ \boxed{110}. $$

∎

TAOCP 7.2.2.2 Exercise 44

Solution

$$ v(x)+v(y)+v(xy)

$$ c_i+\sum_{\substack{0\le r,s<32\r+s=i}}x_ry_s

$$ v(x)+v(y)+v(xy)

27+27+56