无符号数倒计时的正确方式

Question

我正在阅读卡内基梅隆大学的《计算机系统》幻灯片以备我的小测验。在第49页幻灯片中：

Counting Down with Unsigned
Proper way to use unsigned as loop index

unsigned i; 
for (i = cnt-2; i < cnt; i--) 
a[i] += a[i+1]; 

Even better

size_t i; 
for (i = cnt-2; i < cnt; i--) 
a[i] += a[i+1];   

我不明白为什么这不会变成无限循环。我正在减少 i，而它是无符号的，所以应该始终小于 cnt。请解释。

- Kalia Dona

---

unsigned i = cnt - 1; while (i--) a[i] = a[i+1];有什么问题吗？ - David C. Rankin

@DavidC.Rankin 推荐在编写 C 和 C++ 安全代码时采用后者，因为这样长度就与一个单词的大小大致相当。 - Kalia Dona

可能是为什么在C语言中使用无符号整数倒计时会导致无限循环？的重复问题。 - Evan Carroll

Answer 1

迄今为止，我发现用下计数循环的最佳选择是使用 for 循环。

for(unsigned i=N; i-->0; ) {   }

这会以i=N-1 ... 0的顺序调用循环体。这对于有符号和无符号数据类型的处理方式相同，并且不依赖于任何溢出。

- Meixner

---

由于某些原因，这个答案没有得到适当的关注。 - Sergey K.

Answer 2

这个循环依赖于一个事实，即 i 会被递减到0以下，这使得它成为最大的uint值。这会导致循环中断，因为现在 i < cnt == false。

根据Unsigned Int溢出：

无符号数字不能溢出，而是使用模运算的属性进行包装。

C和C++标准都保证了这种uint包装行为，但对于有符号整数则未定义。

- Drakestar

Answer 3

这是利用无符号整数0递减时发生的情况。以下是一个简单示例。

unsigned cnt = 2;
for (int i = 0; i < 5; i++) {
    printf("%u\n", cnt);
    cnt--;
}

那会产生...

2
1
0
4294967295
4294967294

无符号整数0-1变为UINT_MAX。因此，您不是寻找-1，而是观察计数器何时变为比其初始状态更大。

稍微简化一下这个例子，以下是如何从5（独占）倒数到0的方法。

unsigned i;
unsigned cnt = 5;
for (i = cnt-1; i < cnt; i--) {
    printf("%d\n", i);
}

这会打印：

4
3
2
1
0

在最后一次迭代中，i = UINT_MAX，这保证了它比cnt大，因此i < cnt为假。 size_t更好，因为它是无符号的，并且与C语言中最大的数据类型一样大，因此您不必确保cnt与i是相同的数据类型。

- Schwern

---

这段代码使用后置递减运算符，产生与unsigned i = cnt - 1; while (i--) printf("%u\n", i);相同的迭代效果。该运算符允许在循环体内评估i=0，然后在下一次检查（在后置递减之前）的while(0)条件终止循环。 - David C. Rankin

Answer 4

循环的目的是从 cnt-2 循环到 0。它实现了写成 i >= 0 的效果。

前一张幻灯片正确地讲述了为什么循环条件 i >= 0 不起作用。无符号数始终大于或等于 0，因此这样的条件将是真实的。循环条件 i < cnt 最终会循环直到 i 超过 0 并绕回。当你将一个无符号的 0 减小时，它变成了 UINT_MAX（32位整数为2³²-1）。当发生这种情况时，i < cnt 保证是假的，并且循环终止。

我不会像这样编写循环。它在技术上是正确的，但风格非常糟糕。好的代码不仅要正确，还要易读，以便其他人可以轻松地弄清楚它正在做什么。

- John Kugelman

Answer 5

这似乎是一种实现相同功能的已有成语的替代表达方式。

for (unsigned i = N; i != -1; --i) 
   ...;

他们只是用稍微晦涩一点的i < cnt替换了更易读的条件i != -1。在无符号域中将0递减实际上会绕回到UINT_MAX值，该值与在无符号域中相等的-1相比较，且大于或等于cnt。因此，i != -1或i < cnt都可以作为继续迭代的条件。

为什么他们要这样做？显然是因为他们从cnt-2开始，而cnt的值可能小于2，在这种情况下，他们的条件确实有效（而i != -1则不行）。除了这种情况外，没有理由将cnt纳入终止条件。有人可能会说，更好的想法是预先检查cnt的值，然后使用i != -1的习惯用法。

if (cnt >= 2)
  for (unsigned i = cnt - 2; i != -1; --i) 
     ...;

请注意，只要已知i的起始值为非负数，则基于i != -1条件的实现无论i是有符号还是无符号都可以工作。

- AnT stands with Russia

---

尽管cnt=0时，它的工作优势就是i<cnt不成立。 - doynax

有很多正确的候选解决方案适用于这个问题，但是你的更加详细。谢谢！ - Kalia Dona

我不相信这被支持，错误：常量-1与类型为'uint8_t'（也称为'unsigned char'）的表达式的比较始终为真。 - Evan Carroll

这可能对于其他数据类型失败，但对于无符号数会成功：例如对于无符号字符(unsigned char)(-1)=255!=-1。 - Meixner

Answer 6

我觉得你对int和unsigned int数据类型有些混淆。这两个是不同的。在int数据类型（存储大小为2字节）中，它的范围是从-32,768到32,767；而在unsigned int数据类型（存储大小为2字节）中，它的范围是从0到65,535。 在上述例子中，你正在使用unsigned int类型的变量i。它会递减直到i=0，然后根据语义结束for循环。

- sreepurna