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

Question

有两个无符号整数(x和y)需要减去.x总是大于y.但是,x和y都可以环绕; 例如,如果它们都是字节,则在0xff之后变为0x00.问题是如果x环绕,而y不环绕.现在x似乎小于y.幸运的是,x不会缠绕两次(只保证一次).假设字节,x已经包装并且现在是0x2,而y没有并且是0xFE.x - y的正确答案应该是0x4.

也许,

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

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

编写语句的最佳方法是什么(目标语言是C)？

Answer 1

假设有两个无符号整数:

• 如果你知道一个人应该比另一个人"更大",那就减去.它可以工作,只要你没有多次缠绕(显然,如果你有,你将无法分辨).
• 如果您不知道一个比另一个大,则将结果减去并转换为具有相同宽度的signed int.如果两者之间的差异在signed int的范围内(如果没有,你将无法分辨),它将起作用.

澄清一下:原始海报描述的场景似乎令人困惑,但典型的是单调增加固定宽度计数器,例如硬件计数器计数器或协议中的序列号.计数器(例如8位)0xfc,0xfd,0xfe,0xff,0x00,0x01,0x02,0x03等,你知道你拥有的两个值x和y,x后来出现.如果x == 0x02且y == 0xfe,则计算xy(作为8位结果)将给出4的正确答案,假设两个n位值的减法包装模2 ⁿ - C99保证减去无符号值.(注:C标准并不能保证这种行为的减法签署价值.)

Answer 2

当你从'较大'中减去'较小'时,这里有一个更详细的说明为什么它'正常工作'.

进入这里的一些事情......
1.在硬件中,减法使用加法:在添加之前,相应的操作数被简单地否定.
2.在二进制补码(几乎所有东西都使用)中,通过反转所有位然后加1来取消整数.

硬件比上面的描述更有效地做到这一点,但这是减法的基本算法(即使值是无符号的).

因此,让图2 - 250使用8位无符号整数.在二进制中我们有

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

我们否定被减去的操作数然后添加.回想一下,为了否定我们反转所有的位然后加1.反转第二个操作数的位后我们有

0 0 0 0 0 1 0 1  

然后我们加1后

0 0 0 0 0 1 1 0  

现在我们进行添加......

  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

Answer 3

也许我不明白,但有什么不对:

unsigned r = x - y;