花几个月的时间：低级编程的历法之旅

（TL;DR：对于不耐烦的人，请参阅此处和此处。对于其他所有人，请继续阅读……）日历系统是一种尝试，以理解与天文现象相关的时间流逝——太阳、月亮的定位以及相对于我们不固定和可移动的地球的星星。具有讽刺意味的是，广泛使用的公历系统是一个拼凑而成的大杂烩，与天体秩序或逻辑一致性相比，它更能反映历史的任意性。在许多文化中，以某种方式根据月亮的周期（月和月有一个共同的词源）将一年划分为几个月是很常见的。月球的恒星周期（它相对于恒星的位置）刚好超过 27 天。它的会合周期是超过 29 天的半天（从地球看它相对于太阳的位置）。四个星期——28 天——不会是一个不合理的妥协。如果我们要从头开始设计一个日历，试图以尽可能一致的形式调和日、周、月和年的其他未对齐概念，那么国际固定日历将是一个不错的选择——13 个月，每个月 28 天，加上闰日（或两个，闰年）。但这不是我们所拥有的。月份没有固定的长度。长月（31 天）和短月（30 天）交替的系统会运行得很好，可以很好地覆盖 366 天。在这样的系统中，闰年是有规律的，但普通年份需要从一个月中减去一天——将长月从 31 缩短到 30，而不是将短月从 30 缩短到 29 会尽可能保持一致面对不一致。这样的日历每年有 12 个月，所有月份都有 30 或 31 天，没有例外。闰年有六个 30 天的月和六个 31 天的月；在一个普通的年份中，将有七个 30 天的月和五个 31 天的月。但这不是我们所拥有的。与组织时间的其他尝试一样，我们的日历是“天文学与政治之间的不幸联姻”。日历有七个长月和五个短月，其中一个短月——二月——累积了所有的例外——确实默认为28天，但比其他短月短，是闰年的倾倒场每闰年注射一天。其他月份在长短交替之间，但只是一种。为了弄明白这一点，人们采取了从指关节到押韵的各种方法来记住模式。

九月、四月、六月和十一月有三十天；其余的都有三十一个，只有二月除外。我们分配给它二十八，直到闰年给它二十九。如果你按顺序写出月份，强调长月份，你可以看到模式和它在哪里中断：我们可以看到八月是麻烦制造者——或者，准确地说，奥古斯都皇帝，正如一个故事所说：但是这个是一个故事。其他消息表明，Sextilis 月已经有 31 天，而因果关系正好相反，即，不是将 Sextilis 重命名为 August 并将其扩展到 31 天，而是选择了 31 天的月份进行重命名，并且 Sextilis 可用.它紧接在以前称为 Quintilis（为了纪念凯撒大帝而改名为七月）的月份之后，既方便又巧合。还值得记住的是，相邻的两个月份为 31 天并不罕见。我们认为月份主要在多头和空头之间交替的看法在很大程度上是我们开始和结束这一年的假象。罗马年不是从一月开始：因此，为什么我们认为的第 7 个月（七月）和第 8 个月（八月）以前被命名为第 5 个月（Quintilis）和第 6 个月（Sextilis）——是的，第 7、8 个月、9 和 10 给了我们九月、十月、十一月和十二月。无论哪种方式，正是 Johannes 的推文让我重新审视了多年前的一个编码问题，并最终深入到本文中。

因为月份的长度不是以一致的方式交替，为了确定月份是否长，我们可以将其改写为集合成员的问题：对于给定的月份 m，它是长 iff m ∈ {January,三月、五月、七月、八月、十月、十二月}。如果我们从 1 开始计算月份，这会直接转化为 Python，因为让数据说话——集合、查找表等——是一项未开发的技能，也是一个经常错失的机会。您很可能（如果不是更有可能）遇到以下情况： def is_long_month(m): return (m == 1 or m == 3 or m == 5 or m == 7 or m == 8 or m == 10 或 m == 12) 一些程序员可能会将此视为控制流问题，从而产生布尔到布尔转换器的非常常见的代码味道： def is_long_month(m): if ( m == 1 or m == 3 or m == 5 or m == 7 or m == 8 or m == 10 or m == 12): return True else: return False不幸的是，使代码更加明确的努力会产生相反的效果，使其变得笨拙，具有同义反复和冗长的特点。进一步扼杀逻辑也是一个流行的选择： def is_long_month(m): if m == 1: return True elif m == 3: return True elif m == 5: return True elif m == 7: return True elif m == 8: return True elif m == 10: return True elif m == 12: return True else: return False

def is_long_month(m): if (m == 1 or m == 3 or m == 5 or m == 7 or m == 8 or m == 10 or m == 12): return True return False Every if无论您是否使用它，都可以免费使用 else。我什至听到程序员大声朗读这样的代码：“……然后返回真，否则返回假”或“……然后返回真，否则返回假”。如果你说的是真的，那就是写出你的意思的机会。在没有充分理由的情况下打破现有的对称性更像是一种习惯而不是理性的结果，不幸的是，这会导致代码变得更难推理、组合或重构。从广泛适用的函数式和结构化编程中可以学到一些教训和习惯。我们可以将前两个示例的样式组合成尽可能命令式的代码，而不会对控制流造成不必要的暴力： def is_long_month(m): if m == 1: return True if m == 3 : return True if m == 5: return True if m == 7: return True if m == 8: return True if m == 10: return True if m == 12: return True return False 不一定是这样许多程序员不熟悉数据驱动方法或对布尔逻辑感到不舒服或不了解块结构的编程实践……但有时似乎许多程序员不熟悉数据驱动方法或对布尔逻辑感到不舒服或不了解块-结构化编程实践。习惯——因此被个人认为是“正常的”或“简单的”——在很大程度上是熟悉和接触的副产品。我们学到的很多东西都来自复制——有意识地或以其他方式——我们看到别人在做什么。如果你改变人们所接触到的想法和风格，被视为“正常”或“简单”的东西也会改变。许多遗留代码和示例代码是无情的过程性的，无论其广告范式如何，因此许多程序员查看问题和框架解决方案的镜头相应地是面向控制流和命令式的。这是习惯的形成。

让我们切换语言，看看我们会在 C 中做些什么来方便地编写 is_long_month 而无需求助于重定向控制流。 C 缺少类似集合的构造，例如 Python 的 in，但对基于数组的查找表有很好的支持： bool is_long_month(int m) { static const bool month[] = { true, false, true, false, true, false,真、真、假、真、假、真 };返回月份[m - 1]; } int is_long_month(int m) { static const int month[] = {1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1};返回月份[m - 1];反思我自己的经验，可能是学习 C 正确地向我介绍了基于表格的方法的价值和力量，这种方法通过对其他关键的开箱即用支持的语言进一步强化了我的习惯基于数据结构（无论是关联数组、字典还是映射）。现在，当我们在这里时，简要介绍一下命名风格：尽管我将函数名保留为长格式，但其他标识符比我通常编写的要短（例如，对于 long_months，使用 m 代替月和月）。一篇博文没有太多的横向空间，所以代码会在一个有意义的标识符的下降处进行包装。事情即将变得有趣…… C 在整数和布尔值之间有着如此密切的关系，以至于在 C 的大部分历史中，它们被认为是等效的。即使在 C99 中引入了 _Bool（如果包含 <stdbool.h>，则可以作为 bool 使用），两者之间的流量仍然免费且轻松。如果您曾经看到过一个由 1 和 0 组成的小数组，则很有可能您可以将其替换为一个被视为位集的整数。 （但仅仅因为你可以，并不意味着你应该。）在这种情况下，这十二个真值可以轻松地适应任何 16 位或更好的整数：

数字与前一个数组的顺序相反，即一月是最右边的 1 而不是最左边的。二进制文字在 C++、Java、Python、Ruby 和许多其他语言中是标准的，但在 C 中不是，它们仅作为编译器扩展受支持。鉴于 C 是一种系统编程语言，第二点可能会让人感到惊讶……但也许并不像 ANSI C 委员会为 C89 标准（ISO C99 未更改）提供的理由那么令人惊讶：添加二进制常量的建议由于缺乏先例和实用性不足而被拒绝。二进制文字在以金属为生的语言中“实用性不足”的想法令人困惑，令人惊讶，并及时提醒了 Barnett Cocks 的观察，即“实用性不足”的陈述肯定从来都不是真的，“ “缺乏先例”在很久以前就不再适用了。 C11 和 C17 再次错过了这艘船。就目前而言，二进制文字很可能出现在 C23 标准中。如果我们再次仔细查看月份的模式，我们可以看到，如果我们在 7 月之后的任何月份加上 1 的偏差，我们可以单独使用模运算来确定该月份是长还是短：

无需查找、控制流或位操作。这段代码利用了编程语言的人工制品和问题域中的巧合来实现其简洁性——它留给读者作为练习，以确定这是否是一件好事。了解一个月是短还是长可能不如了解它有多少天更有趣。如果月份长度严格为 30 天或 31 天，这将是一个容易解决的问题：m 月的天数始终为 30 + is_long_month(m)。但这不是我们所拥有的。月份可以有四种不同长度中的一种，二月占该变化的一半；对于其他 11 个月， 30 + is_long_month(m) 工作得很好。 int days_in_month(int m, int y) { switch (m) { case 1: case 3: case 5: case 7: case 8: case 10: case 12: return 31;情况 2：返回 28 + is_leap_year(y)；默认值：返回 30；我们假设闰年是一个年份为 0 的公历： int is_leap_year(int y) { return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;或者，我们可以更多地关注功能而不是控制流，通过观察到除了二月之外的每个月问题都已经解决：

int days_in_month(int m, int y) { return m == 2 ? 28 + is_leap_year(y) : 30 + is_long_month(m);另一种方法是切换回使用查找表，这是 C 编程语言的两个版本中采用的路径。 int days_in_month(int m, int y) { static const int days[2][12] = { {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {31 , 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} };返回天数[is_leap_year(y)][m - 1];结果由纯粹的表格方法以声明方式确定，不涉及其他算术或特殊情况处理。条件方法和表格方法之间的中途之家可能如下所示： int days_in_month(int m, int y) { static const int days[] = { 31, 28, 31, 30, 31, 30, 31, 31 , 30, 31, 30, 31 };返回 days[m - 1] + (m == 2 ? is_leap_year(y) : 0);一个有趣的巧合是最大月份长度为 31，即 2⁵-1，因为这意味着我们只需要 5 位来编码每个月份的长度。因此，对于 12 个月，我们只需要 60 位。这意味着我们的表可以被硬塞进一个 64 位整数，并保留一些位。 int days_in_month(int m, int y) { const long long days = 31LL << 0 | 28LL << 5 | 31LL << 10 | 30LL << 15 | 31LL << 20 | 30LL << 25 | 31LL << 30 | 31LL << 35 | 30LL << 40 | 31LL << 45 | 30LL << 50 | 31LL<<55；返回 ((days >> (m - 1) * 5) & 0b11111) + (m == 2 ? is_leap_year(y) : 0); }

这里有几件事需要注意，首先是不要在工作中这样做。第二个是我使用了 long long，它保证至少是 64 位宽，而不是 long，它不是。我可以通过使用 <stdint.h> 中的 int64_t 类型名称使这更明确，但是当我在编码中显式使用 long long 文字时，抽象的好处很小。第三，那些长长的文字：我使用 LL 而不是 ll。如果您习惯于在 C 中为数字文字类型使用小写后缀，那么您可能需要重新考虑这种习惯。这是再次使用小写的编码： const long long days = 31ll << 0 | 28ll << 5 | 31ll << 10 | 30ll << 15 | 31ll << 20 | 30ll << 25 | 31ll << 30 | 31ll << 35 | 30ll << 40 | 31ll << 45 | 30ll << 50 | 31ll << 55;而且，说到文字，要注意的第四件事是使用二进制文字 0b11111 来明确我正在屏蔽移位查找的低五位以恢复月份的天数。 （如果您认为能够以二进制形式直接显示位值是“不够实用”，那么请随意将 0b11111 替换为 31。） return ((days >> (m - 1) * 5) & 0b11111) + (m == 2 ? is_leap_year(y) : 0);我们可以利用布尔值和整数之间的密切关系在逻辑上生成 0 情况：

return ((days >> (m - 1) * 5) & 0b11111) + (m == 2 && is_leap_year(y)); return ((days >> (m - 1) * 5) & 0b11111) + (m == 2) * is_leap_year(y);这个片段的有趣之处在于，除了 is_leap_year 中的代码外，这段代码是无分支的，即，没有来自控制流的显式语句（例如 if 和 switch）或来自短路的控制流分支运算符，例如 && 和 ?:。 int is_leap_year(int y) { return !(y % 4) - !(y % 100) + !(y % 400);因此，我们可以在不执行查找或做出任何决定的情况下确定一个月中的天数： int days_in_month(int m, int y) { return 30 + is_long_month(m) + (m == 2) * ( is_leap_year(y) - 2); } int days_in_month(int m, int y) { return 30 + (m + (m > 7)) % 2 + (m == 2) * (!(y % 4) - !(y % 100) + !( y % 400) - 2); }

多年前，我试图弄清楚是否可以在不使用分支或使用查找的情况下计算一个月中的天数。 （我在火车上。我很无聊。）我写的代码已经在历史和我的记忆中消失了，但我猜它最终会像上面的代码一样。但是用一种强烈禁止布尔值和整数之间关系的语言来做呢？ C 对这种关系的宽容和自由放任的观点正是我多年前和这次再次选择 C ​​的原因：它已经足够棘手，而无需尝试将布尔运算转换为整数运算。现在情况不同了。 （疫情期间我在家。我很无聊。）而且，当本问起时，我认为这是一个有趣的后续挑战。我们可以通过将问题分解为其组成部分来找到解决方案。悬而未决的结果是决定一个月是长还是短。在 C 代码中，使用 m > 7 的布尔结果作为整数将 7 月后的偏差添加到月份中。另一种写法是 m ≥ 8。方便地，8 是 2³，因此所有大于或等于 8 的值都将设置 2³ 值位。 public static int isLongMonth(int m) { return (m + ((m & 8) >> 3)) % 2;既然风格已经从算术转移到按位，为了一致性，用按位替换余数运算符也不是没有道理的，即 (...) % 2 变为 (...) & 1，但我将其保留为是。果实的其余部分要高得多，但可以通过实现我们所需要的阶梯来实现，这是一种比较两个整数是否相等的方法，结果是 1 或 0，而不是真或假。引用计算机程序的结构和解释：

如果我们想象一个 eq 操作为我们做这件事，我们可以检测闰年如下： public static int isLeapYear(int y) { return eq(y % 4, 0) - eq(y % 100, 0) + eq (y % 400, 0); } public static int daysInMonth(int m, int y) { return 30 + isLongMonth(m) + eq(m, 2) * (isLeapYear(y) - 2);现在，为了让我们的愿望成真，我们需要具体化 eq —— 我们已经解决了这个问题，但希望我们没有把自己逼到绝境。如何比较两个整数以获得整数而不是布尔值？如果我们从另一个整数中减去一个整数，如果它们相等，则为零，如果它们不相等，则为非零。在相等的情况下，当结果为 0 时，加 1 得到我们想要的布尔到整数的转换。但是，当它们不相等时，这在一般情况下不起作用。整数使用二进制补码表示。对于 32 位 int，从 0 到 2³¹-1 的正整数按我们的预期以二进制表示。然而，负整数是通过对位求补并加 1 来表示的。因此对于整数 n，-n 是 ~n+1。这意味着前导位是一个符号位，零和正整数为 0，负整数为 1。

对于两个整数 a 和 b，ab 等于 -(ba)。当 a 和 b 不相等时，这意味着 ab 为负而 ba 为正，或者 ab 为正而 ba 为负。无论哪种方式，如果 a 和 b 不相等，都会有一个负结果的减法。如果您使用按位或组合两个相反符号的数字，则符号位将始终为 1。这意味着 (ab) | (ba) 当 a 和 b 相等时符号位为 0，不相等时符号位为 1。如果将整数 0 右移任意位数，它仍为 0。如果对负数执行算术右移，它仍为负数，即用 1 填充最左边的位。因此，如果右移 32-位负整数乘以 31 位，您将得到所有位设置为 1，即整数值 -1，加上 1 得到 0，因此，我们需要布尔到整数的转换。 public static int eq(int a, int b) { return 1 + (((a - b) | (b - a)) >> 31); } public static int daysInMonth(int m, int y) { return 30 + (m + ((m & 8) >> 3)) % 2 + (1 + (((m - 2) | (2 - m)) >> 31)) * ((1 + (((y % 4) | -(y % 4)) >> 31)) - (1 + (((y % 100) | -(y % 100)) > > 31)) + (1 + (((y % 400) | -(y % 400)) >> 31)) - 2);这篇文章有很多你应该和不应该带走的东西。第一个是

......