使用无符号倒数的正确方法

Question

我正在为我的测验阅读卡内基梅隆大学关于计算机系统的幻灯片。在 slide 第 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。请解释。

Answer 1

循环的目标是从 cnt-2 循环到 0。实现了写i >= 0.

的效果

上一张幻灯片正确地讨论了为什么 i >= 0 的循环条件不起作用。无符号数总是大于或等于 0，因此这样的条件将空洞地为真。 i < cnt 的循环条件结束循环，直到 i 超过 0 并环绕。当你递减一个无符号的 0 时，它变成 UINT_MAX （2³² - 1 对于 32 位整数）。发生这种情况时，i < cnt 保证为假，循环终止。

我不会写这样的循环。它在技术上是正确的，但风格很差。好的代码不仅是正确的，而且是可读的，所以其他人可以很容易地弄清楚它在做什么。

Answer 2

这个循环仅仅依赖于 i 将递减到 0 之后的事实，这使其成为最大 uint 值。这打破了循环，因为现在 i < cnt == false。

根据 Overflowing of Unsigned Int:

unsigned numbers can't overflow, but instead wrap around using the properties of modulo.

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

Answer 3

这似乎是实现相同事物的既定习语的另一种表达方式

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

他们只是用更隐晦的 i < cnt 替换了更易读的 i != -1 条件。当 0 在 unsigned 域中递减时，它实际上环绕到 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有符号或无符号。

Answer 4

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

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

产生...

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

稍微简化示例，以下是如何从 5（不含）倒数到 0。

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

打印：

在最后一次迭代中 i = UINT_MAX 保证大于 cnt 所以 i < cnt 是错误的。

size_t 是 "better" 因为它是无符号的并且它和 C 中最大的东西一样大，所以你不必确保 cnt 与 i.

Answer 5

我认为您对 int 和 unsigned int 数据类型感到困惑。这两个是不同的。在 int 数据类型（2 字节存储大小）中，它的范围从 -32,768 到 32,767 而在 unsigned int 数据类型（2 字节存储大小）。您的范围从 0 到 65,535 。在上面提到的示例中，您使用的是 unsigned int 类型的变量 i。它会递减到 i=0，然后根据语义结束 for 循环。

Answer 6

到目前为止我发现的递减计数循环的最佳选择是使用

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

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

使用无符号倒数的正确方法

Proper way to count down with unsigned

c

unsigned

loops