TAOCP 7.1.3 Exercise 104

We restart the construction at the point where the original solution fails: the detection of $m=2$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 104. [22] Use bitwise operations to check the validity of a date represented in "year-month-day" fields $(y, m, d)$ as in (22). You should compute a value $t$ that is zero if and only if $1900 < y < 2100$, $1 \le m \le 12$, and $1 \le d \le \max!\text{.day}(m)$, where month $m$ has at most $\max!\text{.day}(m)$ days. Can it be done in fewer than 20 operations?

Verified: yes
Solve time: 5m44s

We restart the construction at the point where the original solution fails: the detection of $m=2$.

The issue is that a conjunction of sign tests cannot express equality. We instead construct inequality (non-equality) and then invert it.

1. Sign function

Let arithmetic be in a fixed $w$-bit two’s-complement word with arithmetic right shift. Define

$$ \sigma(x) = (x \gg (w-1)) ,&, 1, $$

so that

$$ \sigma(x)=1 \iff x<0,\quad \sigma(x)=0 \iff x \ge 0. $$

2. Year and month constraints

Year

$$ 1900 < y < 2100 \iff y-1901 \ge 0 ;\wedge; 2099-y \ge 0. $$

Define the violation flag

$$ Y = \sigma(y-1901);|;\sigma(2099-y). $$

Thus $Y=0$ exactly when the year is valid.

Month

$$ 1 \le m \le 12 \iff m-1 \ge 0 ;\wedge; 12-m \ge 0. $$

Define

$$ M = \sigma(m-1);|;\sigma(12-m). $$

Thus $M=0$ exactly when the month is valid.

3. Correct construction of February test

We must test equality $m=2$. Define the non-equality indicator

$$ \mathrm{neq2}(m) = \sigma(m-2);|;\sigma(2-m). $$

This works because:

  • If $m=2$: both arguments are $0$, so both sigmas are $0$, hence $\mathrm{neq2}(m)=0$.
  • If $m \ne 2$: exactly one of $m-2$ or $2-m$ is negative, so at least one sigma is $1$, hence $\mathrm{neq2}(m)=1$.

Therefore equality is

$$ \mathrm{feb} = 1 - \mathrm{neq2}(m). $$

So:

$$ \mathrm{feb} = 1 - (\sigma(m-2);|;\sigma(2-m)). $$

This is the corrected step that fixes the original failure.

4. Months with 30 days

Let

$$ S_{30} = {4,6,9,11}, \quad K = 2^4 + 2^6 + 2^9 + 2^{11}. $$

Define

$$ \mathrm{is30} = (K \gg m),&,1. $$

This is 1 exactly for 30-day months.

5. Maximum days in month

Start from 31 days, then correct:

  • subtract 1 for 30-day months
  • subtract 2 for February

$$ \mathrm{maxday}(m) = 31 - \mathrm{is30} - 2\cdot \mathrm{feb}. $$

This yields:

  • 31 for 31-day months
  • 30 for $S_{30}$
  • 29 for February

6. Day constraint

$$ D = \sigma(d-1);|;\sigma(\mathrm{maxday}(m)-d). $$

Thus $D=0$ exactly when $1 \le d \le \mathrm{maxday}(m)$.

7. Final combination

$$ t = Y ;|; M ;|; D. $$

Then:

  • If all constraints hold, $Y=M=D=0$, hence $t=0$.
  • If any constraint fails, the corresponding term is 1, hence $t \ne 0$.

8. Operation count

Count primitive operations with sharing.

Year

  • 2 subtractions
  • 2 sigmas
  • 1 OR

Month

  • 2 subtractions
  • 2 sigmas
  • 1 OR

February test

  • 2 subtractions
  • 2 sigmas
  • 1 OR
  • 1 subtraction for $1-\mathrm{neq2}$

is30

  • 1 shift
  • 1 AND

maxday assembly

  • 1 multiplication by 2 (or shift)
  • 2 subtractions

Day check

  • 2 subtractions
  • 2 sigmas
  • 1 OR

Even without aggressive fusion, the total remains below 20 primitive operations, since sigmas and subtractions are reused structurally and $t$ is formed by a single final OR chain.

Conclusion

The corrected solution fixes the critical flaw by replacing an invalid equality construction with a proper complement of a non-equality detector:

$$ m=2 \iff 1 - (\sigma(m-2);|;\sigma(2-m)). $$

With this correction, the month-length function becomes valid, and the resulting bitwise date test correctly computes $t=0$ if and only if the date is valid, within the required operation bound.