The Date Hack

Main ideas and lessons

• Computer-science “hard problems” framing

  • The speaker jokes that two hard problems are naming things and getting a date, then pivots to a technical meaning of “date” (calendar/day-of-week calculation).

• Goal: compute day-of-week from a day count

  • Primary question: “What day of the week is the 57th day since the epoch?”
  • They map days to numbers and discuss how to correctly handle modulo arithmetic, especially for negative day counts.

• Baseline approach (works for some cases, fails for negatives)

  • Day mapping used:
    • Sunday = 0, Monday = 1, … Friday = 5, Saturday = 6
  • Simplest formula suggested:
    • daycount % 7
  • But this fails because it ignores the day-of-week of the epoch.

• Correct modulo approach by incorporating the epoch offset

  • Epoch day-of-week:
    • Epoch is on Thursday
    • With their mapping, Thursday corresponds to 4
  • Corrected formula (conceptually):
    • Add the epoch offset, then take modulo 7.
  • Testing shows correctness for the positive case, but still breaks for negative inputs (they observe negative results like -1).

• General fix for negative day counts (shift-into-positive, avoid negative modulo issues)

  • They introduce a generalized formula that:
    • Handles negative daycount by shifting the intermediate value into a non-negative range before applying modulo.
  • Conceptually, the approach is:
    • Compute daycount % 7, then add 7 to avoid negatives, add the Thursday offset, and do a final % 7.
  • Tradeoff: two modulo operations are considered “slow” for database use.

• Optimization 1: a “Hennessy-style” or alternative algorithm using an if/branch

  • Avoids multiple mod operations by using a conditional approach:
    • Case A: when daycount >= -4 use the original simplified formula style.
    • Case B: when daycount < -4 use a different shifted equation.
  • They explain the negative-case adjustment as shifting the range by adding 6 (so that negative residues align with the correct weekday).
  • The reason it works: it aligns the computed residue directly with weekday numbers relative to Thursday.

• Optimization 2 (the “bitwise magic”): Nery’s algorithm using two’s complement and unsigned reinterpretation

  • The speaker claims this is the “most insane bitwise operation” and focuses on an algorithm associated with Nery.
  • Key prerequisites:
    • Understand two’s complement for representing negative numbers:
      • Take bitwise complement, then add 1.
    • Understand reinterpreting signed integers as unsigned using specific bit widths.
  • Critical observation:
    • The algorithm relies on special compatibility for certain widths:
      • It “only works out” for a small set of bit sizes, specifically mentioning U32 and U8.
  • Worked concept:
    • For example, -5 in signed 8-bit can be represented as an unsigned value by interpreting the bits as unsigned:
      • They state it becomes 251.
    • Then the algorithm uses:
      • 251 % 7 and notes that 256 % 7 = 4, so the offset causes correct weekday alignment.
  • Resulting insight:
    • Because of the arithmetic relationship (256 mod 7 = 4) and how negative values wrap around, the unsigned reinterpretation produces the same effect as applying the proper epoch/offset logic, effectively matching the day-of-week mapping.

• Further note

  • The speaker points to a blog post and references Hacker’s Delight as a source of related bitwise tricks.
  • They mention the blog claims the day-of-week computation can be done in a single machine operation on certain machines.

---

Methodology / instruction-like steps (as presented)

A) Deriving weekday from daycount using modulo + epoch offset

• Assign weekday numbers:

  • Sunday=0, Monday=1, Tuesday=2, Wednesday=3, Thursday=4, Friday=5, Saturday=6

• Determine epoch weekday offset:

  • Epoch is Thursday → offset = 4

• For positive daycount, compute:

  • weekday = (daycount % 7 + epoch_offset) % 7

• Issue:

  • Negative daycount leads to negative modulo outputs in typical languages/models.

• Fix for negatives:

  • Shift the modulo result into non-negative range before the final modulo:
    • Add 7 after the first % 7 to avoid negatives, then add epoch offset, then % 7.

---

B) Reducing cost: conditional algorithm to avoid multiple modulo operations

• Use an if-style split:

  • If daycount >= -4:

    • Use the simpler original residue logic (the one that matches correctly up to a point).

  • Else (for daycount < -4):

    • Use a shifted computation based on aligning residues by adding 6 (described as shifting the range so the offsets match weekday numbers correctly).

• Goal:

  • Replace “two modulo operations” with a branch + one simpler arithmetic path.

---

C) Bitwise algorithm (Nery’s) concept: unsigned reinterpretation with two’s complement

• Represent negatives using two’s complement:

  • Complement bits then add 1.

• Require specific integer bit-width behavior:

  • Works for certain widths (notably U8 and U32).

• Compute weekday using unsigned reinterpretation:

  • Reinterpret the signed negative value’s bit pattern as an unsigned integer.
  • Take % 7 on that unsigned value.

• Key arithmetic justification used in the explanation:

  • They highlight 256 % 7 = 4, which matches the epoch offset (Thursday=4) and makes the wrapping consistent with the desired weekday mapping.

---

Speakers / sources featured

Speakers

• The main unnamed speaker (the one explaining algorithms and jokes)
• References to Nery (author/associated with “Nery’s algorithm”)
• References to Henance/Hennessy (author/associated with an algorithm released in 2014)

Sources / works mentioned

• Linear (video sponsor; provides ticketing/automation for production errors)
• Hacker’s Delight (book referenced for bitwise manipulation techniques)
• A blog post about the bitwise day-of-week computation (mentioned, but not titled in the subtitles)