WZBLOG-惜梦博客-专注web编程的个人博客 WZBLOG-惜梦博客-专注web编程的个人博客

为什么数字(数组)下标要从 0 开始而不是 1?

in 其他 read (1019) 文章转载请注明来源!

Why numbering should start at zero

著名的计算机科学家Dijkstra在1982年的手稿中简要讨论了“为什么数字下标要从0开始”这个问题。

首先,他讨论了表示范围的最佳形式。 比如表示自然数序列2,3,···,12,有四种方法:

  1. 2i < 13 ,或者记作[2, 13)
  2. 1 < i12 ,或者记作(1, 12]
  3. 2i12 ,或者记作[2, 12]
  4. 1 < i < 13 ,或者记作(1, 13)

方法1是最好的

Dijkstra认为方法1和2是比较好的表示形式,原因有两个。

其一,范围的上限减去下限等于范围内元素的个数。 比如方法1中,13 - 2 = 11,而范围内刚好就有11个元素。 方法2也有同样的性质,但方法3和4就没有。

其二,连续的范围没有重叠。 两个连续的范围我们希望可以写成“a到b”和“b到c”这样的形式。 如果使用方法3,12就同时包含在 [2, 12][12, 24] 这两个范围里; 类似的,使用方法4,13既不包含在 (2, 13) 里也不在 (13, 25) 里。 用方法1和2就没有这样的问题。比如 [2, 13)[13, 25) 是两个连续的范围,13只会包含在后一个里。

虽然方法1和2都能满足上面两条性质,但Dijkstra继续给出了方法1比方法2好的理由: 我们常常会用到有下限无上限的集合,最典型的是自然数集合。 比如要表示自然数集合内的范围“0到10”, 用方法1可以写成 [0, 11) , 用方法2可以写成 (-1, 10] 。 方法2的问题是形式中出现了-1这个非自然数, 用非自然数来表示一个自然数集合内的范围显然不是一个好的选择。

为什么下标要从0开始

Dijkstra进而在其手稿中继续讨论数字下标为什么从0开始的问题,

他给出的第一个理由是,如果你能接受前半段关于表示范围的最佳表示方法的结论,那么N个元素的数列下标可以采用 [0, N) 或者 [1, N+1) 两种形式,前一种不需要+1也就显得更简洁了。

另一个理由是,如果从0开始标号,那数列中某个元素的下标就等于排在它前面元素的个数,这在很多时候是一个可以方便使用的性质。

1551102671(1).png

第三个理由有点模糊,他说0是”最自然的数”(a most natural number),却没有给出具体的解释。 于是我强行解释一下:计算机中的数用二进制表示,所有的位都是off时,便是起点,也就是最自然的数吧。

你问我资瓷不资瓷Dijkstra,那肯定回答资瓷

Dijkstra绕了个圈子论证了从0开始的正当性,我能联想到与此相关的最直接的编程技巧是C语言中的数组操作:读取数组元素的操作和指针操作有比较直接的等价关系。

具体地说,C语言中 arr[idx] 等价于 *(arr + idx) 。 指针操作你可以看作对base地址偏移offset的量, 即在 *(arr + idx) 式子中, arr 是base地址, idx 是offset。 试想如果下标设计成从1开始,那C语言可能需要设计成 arr[idx] 等价于 *(arr + idx - 1) 了。

本文英文原文: 计算机科学家Dijkstra在1982年的手稿
本文中文翻译原文: czheo GitHub

本文基于《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
文章链接:https://blog.wz52.cn/archives/174.html (转载时请注明本文出处及文章链接)

其他
发表新评论
PREVIOUS NEXT
雷姆
拉姆