TAOCP 7.1.3 Exercise 101

Let the word size be $64$ bits.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 101. ▶ [22] Two octabytes $x$ and $y$ contain amounts of time, represented in five fields that respectively signify days (3 bytes), hours (1 byte), minutes (1 byte), seconds (1 byte), and milliseconds (2 bytes). Can you add and subtract them quickly, without converting from this mixed-radix representation to binary and back again?

Verified: yes
Solve time: 2m23s

Solution

Let the word size be $64$ bits. Write the mixed-radix decomposition as five binary fields packed in one word:

$x = (d_x,|,h_x,|,m_x,|,s_x,|,ms_x),$

where

$ms_x \in [0,2^{16}), \quad s_x,m_x,h_x \in [0,2^8), \quad d_x \in [0,2^{24}).$

The same decomposition is used for $y$.

Define field extraction by bit masks:

$ms_x = x ,&, (2^{16}-1),$

$s_x = (x \gg 16),&,(2^8-1),$

$m_x = (x \gg 24),&,(2^8-1),$

$h_x = (x \gg 32),&,(2^8-1),$

$d_x = (x \gg 40),&,(2^{24}-1).$

Addition

Let

$t_0 = ms_x + ms_y.$

Define the carry into the seconds field by

$c_0 = t_0 \gg 16,$

and the reduced field value by

$ms = t_0 ,&, (2^{16}-1).$

Next define

$t_1 = s_x + s_y + c_0,$

$c_1 = t_1 \gg 8,$

$s = t_1 ,&,(2^8-1).$

Proceed similarly through the remaining byte fields:

$t_2 = m_x + m_y + c_1,$

$c_2 = t_2 \gg 8,$

$m = t_2 ,&,(2^8-1),$

$t_3 = h_x + h_y + c_2,$

$c_3 = t_3 \gg 8,$

$h = t_3 ,&,(2^8-1),$

$t_4 = d_x + d_y + c_3,$

$d = t_4 ,&,(2^{24}-1).$

The final result is reconstructed as

$x+y = (d \ll 40),|, (h \ll 32),|, (m \ll 24),|, (s \ll 16),|, ms.$

Each carry $c_i$ depends only on a single overflow test of a bounded binary addition, so each field boundary is handled exactly once by the shift-and-mask propagation above.

Subtraction

Define analogous borrow propagation. Let

$t_0 = ms_x - ms_y.$

Set

$b_0 = (ms_x < ms_y),$

and

$ms = t_0 ,&, (2^{16}-1).$

Then for each byte field:

$t_1 = s_x - s_y - b_0,$

$b_1 = (s_x < s_y + b_0),$

$s = t_1 ,&,(2^8-1),$

$t_2 = m_x - m_y - b_1,$

$b_2 = (m_x < m_y + b_1),$

$m = t_2 ,&,(2^8-1),$

$t_3 = h_x - h_y - b_2,$

$b_3 = (h_x < h_y + b_2),$

$h = t_3 ,&,(2^8-1),$

$t_4 = d_x - d_y - b_3,$

$d = t_4 ,&,(2^{24}-1).$

The reconstructed difference is

$x-y = (d \ll 40),|, (h \ll 32),|, (m \ll 24),|, (s \ll 16),|, ms.$

Each borrow test depends only on a comparison within a single fixed-width field together with the incoming borrow, so the propagation respects the mixed-radix structure without converting the representation.

This completes the construction. ∎