C语言 如何用环绕或溢出减去两个无符号整数

How to subtract two unsigned ints with wrap around or overflow

提问by mgag

There are two unsigned ints (x and y) that need to be subtracted. x is always larger than y. However, both x and y can wrap around; for example, if they were both bytes, after 0xff comes 0x00. The problem case is if x wraps around, while y does not. Now x appears to be smaller than y. Luckily, x will not wrap around twice (only once is guaranteed). Assuming bytes, x has wrapped and is now 0x2, whereas y has not and is 0xFE. The right answer of x - y is supposed to be 0x4.

有两个无符号整数（x 和 y）需要相减。x 总是大于 y。但是，x 和 y 都可以环绕；例如，如果它们都是字节，则在 0xff 之后是 0x00。问题是如果 x 环绕，而 y 不环绕。现在 x 似乎小于 y。幸运的是， x 不会回绕两次（保证只有一次）。假设字节数，x 已经换行并且现在是 0x2，而 y 没有并且是 0xFE。x - y 的正确答案应该是 0x4。

Maybe,

也许，

( x > y) ? (x-y) : (x+0xff-y);

But I think there is another way, something involving 2s compliment?, and in this embedded system, x and y are the largest unsigned int types, so adding 0xff... is not possible

但我认为还有另一种方式，涉及 2s 的恭维？，在这个嵌入式系统中，x 和 y 是最大的 unsigned int 类型，因此添加 0xff... 是不可能的

What is the best way to write the statement (target language is C)?

编写语句的最佳方式是什么（目标语言是 C）？

回答by Matthew Slattery

Assuming two unsignedintegers:

假设两个无符号整数：

• If you know that one is supposed to be "larger" than the other, just subtract. It will work provided you haven't wrapped around more than once (obviously, if you have, you won't be able to tell).
• If you don't know that one is larger than the other, subtract and cast the result to a signed int of the same width. It will work provided the difference between the two is in the range of the signed int (if not, you won't be able to tell).

• 如果您知道一个应该比另一个“大”，只需减去。如果您没有超过一次，它就会起作用（显然，如果您有，您将无法分辨）。
• 如果您不知道一个大于另一个，请减去并将结果转换为相同宽度的有符号整数。如果两者之间的差异在有符号整数的范围内（如果不是，您将无法分辨），它将起作用。

To clarify: the scenario described by the original poster seems to be confusing people, but is typical of monotonically increasing fixed-width counters, such as hardware tick counters, or sequence numbers in protocols. The counter goes (e.g. for 8 bits) 0xfc, 0xfd, 0xfe, 0xff, 0x00, 0x01, 0x02, 0x03 etc., and you know that of the two values x and y that you have, x comes later. If x==0x02 and y==0xfe, the calculation x-y (as an 8-bit result) will give the correct answer of 4, assuming that subtraction of two n-bit values wraps modulo 2ⁿ- which C99 guarantees for subtraction of unsigned values. (Note: the C standard does notguarantee this behaviour for subtraction of signedvalues.)

澄清一下：原始海报描述的场景似乎使人们感到困惑，但它是典型的单调递增的固定宽度计数器，例如硬件滴答计数器或协议中的序列号。计数器变为（例如，对于 8 位）0xfc、0xfd、0xfe、0xff、0x00、0x01、0x02、0x03 等，并且您知道您拥有的两个值 x 和 y 中的 x 稍后出现。如果 x==0x02 和 y==0xfe，则计算 xy（作为 8 位结果）将给出正确答案 4，假设两个n位值的减法包含模 2 ⁿ- C99 保证减去无符号值。（注：C标准并不能保证这种行为的减法签署价值。）

回答by Purdude

Here's a little more detail of why it 'just works' when you subtract the 'smaller' from the 'larger'.

当您从“较大”中减去“较小”时，这里有更多细节说明为什么它“有效”。

A couple of things going into this…
1. In hardware, subtraction uses addition: The appropriate operand is simply negated before being added.
2. In two's complement (which pretty much everything uses), an integer is negated by inverting all the bits then adding 1.

有几件事情要讨论……
1. 在硬件中，减法使用加法：适当的操作数在被加之前被简单地取反。
2. 在二进制补码（几乎所有东西都使用）中，通过反转所有位然后加 1 来否定整数。

Hardware does this more efficiently than it sounds from the above description, but that's the basic algorithm for subtraction (even when values are unsigned).

硬件比上面的描述听起来更有效，但这是减法的基本算法（即使值是无符号的）。

So, lets figure 2 – 250 using 8bit unsigned integers. In binary we have

因此，让我们使用 8 位无符号整数计算 2 – 250。在二进制中，我们有

  0 0 0 0 0 0 1 0  
- 1 1 1 1 1 0 1 0

We negate the operand being subtracted and then add. Recall that to negate we invert all the bits then add 1. After inverting the bits of the second operand we have

我们否定被减去的操作数，然后加上。回想一下，为了取反，我们反转所有位然后加 1。在反转第二个操作数的位之后，我们有

0 0 0 0 0 1 0 1  

Then after adding 1 we have

然后在添加 1 之后我们有

0 0 0 0 0 1 1 0  

Now we perform addition...

现在我们执行加法...

  0 0 0 0 0 0 1 0   
+ 0 0 0 0 0 1 1 0

= 0 0 0 0 1 0 0 0 = 8, which is the result we wanted from 2 - 250

回答by GManNickG

Maybe I don't understand, but what's wrong with:

也许我不明白，但有什么问题：

unsigned r = x - y;

unsigned r = x - y;

回答by AnT

The question, as stated, is confusing. You said that you are subtracting unsigned values. If xis always larger than y, as you said, then x - ycannot possibly wrap around or overflow. So you just do x - y(if that's what you need) and that's it.

如上所述，这个问题令人困惑。你说你正在减去无符号值。如果x总是大于y，如您所说，则x - y不可能环绕或溢出。所以你只要做x - y（如果那是你需要的），就是这样。

回答by C guy

This is an efficient way to determine the amount of free space in a circular buffer or do sliding window flow control. Use unsigned ints for headand tail- increment them and let them wrap! Buffer length has to be a power of 2.

这是确定循环缓冲区中的可用空间量或进行滑动窗口流量控制的有效方法。使用unsigned ints for headand tail- 增加它们并让它们换行！缓冲区长度必须是 2 的幂。

free = ((head - tail) & size_mask), where size_maskis 2^n-1 the buffer or window size.

free = ((head - tail) & size_mask)，其中size_mask2^n-1 是缓冲区或窗口大小。

回答by Tarion

Just to put the already correct answer into code:

只是将已经正确的答案放入代码中：

If you know that x is the smaller value, the following calculation just works:

如果您知道 x 是较小的值，则以下计算仅适用：

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    uint8_t res = y - x;
    printf("Expect 20: %d\n", res); // res is 20

    return 0;
}

If you do not know which one is smaller:

如果您不知道哪个较小：

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    int8_t res1 = (int8_t)x - y;
    int8_t res2 = (int8_t)y - x;
    printf("Expect -20 and 20: %d and %d\n", res1, res2);

    return 0;
}

Where the difference must be inside the range of uint8_tin this case.

uint8_t在这种情况下，差异必须在范围内。

The code experiment helped me to understand the solution better.

代码实验帮助我更好地理解了解决方案。

回答by hpc64

The problem should be stated as follows:

问题应说明如下：

Let's assume the position (angle) of two pointers aand bof a clock is given by an uint8_t. The whole circumerence is devided into the 256 values of an uint8_t. How can the smaller distance between the two pointer be calculated efficiently?

让我们假设两个指针a和b时钟的位置（角度）由 uint8_t 给出。整个圆周被划分为一个 uint8_t 的 256 个值。如何有效计算两个指针之间的较小距离？

A solution is:

一个解决办法是：

uint8_t smaller_distance = abs( (int8_t)( a - b ) );

uint8_t smaller_distance = abs( (int8_t)( a - b ) );

I suspect there is nothing more effient as otherwise there would be something more efficient than abs().

我怀疑没有什么比 abs() 更有效的了，否则会有比 abs() 更有效的东西。

回答by MSN

To echo everyone else replying, if you just subtract the two and interpret the result as unsigned you'll be fine.

为了回应其他人的回复，如果你只是将两者相减并将结果解释为无符号，你会没事的。

Unless you have an explicit counterexample.

除非你有明确的反例。

Your example of x = 0x2, y= 0x14would not result in 0x4, it would result in 0xEE, unless you have more constraints on the math that are unstated.

您的例子x = 0x2，y= 0x14不会导致0x4，这将导致0xEE，除非你对此是不成文的数学更多的约束。