在C语言中进行位运算比较两个整数

Question

最近我在一门课程中参加了一次小测验，以下是问题:

编写一个C函数（名为cmp），接受两个整数(x和y)作为参数，并返回：-1如果x<y，0如果x=y， 1 如果 x > y。尽可能简洁地编写 cmp。

我能想到的最简洁的函数是：

int cmp(int x, int y) {
    return ((x < y) ? (-1) : ((x == y) ? (0) : (1)));
}

但我感觉可能有一些操作可以更简洁地完成。也许是 & 和 ^ 的组合方式？这个问题困扰了我几天，我想知道是否确实有更好的方法来解决这个问题？

- an4s

---

你不需要那么多的括号。 - Dai

在使用位运算时要小心 - 如果我没记错，C语言并没有规定有符号整数的实现细节：它们可以使用二进制补码、一进制补码、符号位或其他一些奇特的格式。我相信唯一保证正确比较有符号整数的方法是使用内置运算符<、>、==、!=、<=和>=。 - Dai

@ Dai：你是正确的。我只是想对我的代码小心谨慎，我猜想在考试之前的讲座中提到了很多有关位运算的内容。因此，我预感可能会测试一些位运算的概念。 - an4s

我投票关闭此问题，因为实际上促进不可读代码的问题对您来说是不好的 :-) 更好的方法是编写您的代码，就好像您的祖母需要理解它一样，并让编译器处理优化-它比大多数开发人员更擅长这方面。 - paxdiablo

在内部，编译器执行减法并设置CPU标志。你可以进行减法运算，如果结果为0则返回0，或者将高位移动到最低位并返回。这样做更快吗？可能不是。但你必须比较每个汇编输出才能确定。老实说，你的方法只需要2次比较，已经很不错了。这取决于比较/跳转的成本，而这在每个CPU上都有所不同。 - Michael Dorgan

Answer 1

“尽可能简洁”对于一道测验来说是一个非常模糊的要求。你是否需要进行代码高尔夫比赛？删除空格和括号是否会使它更加简洁？无论如何，这里有一个使用比较结果进行算术运算的解决方案：

int cmp(int x, int y) {
    return (x > y) - (x < y);
}

- Ry-

---

实际上，意图是在 C 中简洁编写代码，还是针对底层机器语言编写旨在简洁（或快速）的代码？ - BeeOnRope

C99引入了bool类型 - 但比较运算符是否仍然会产生int表达式，还是现在是bool？减去bool值的操作是否定义良好？ - Dai

@Dai：在C99中，比较运算符仍会产生“int”表达式，但即使它们不是这样，从“bool”到“int”的转换仍然是明确定义的。 - Ry-

x - y 可能会溢出。特别是如果你正在学习网络安全，你应该避免使用在某些输入上具有不可预测、未定义或不正确结果的快捷方式。 - rici

@rici：是的，这很重要，我不确定为什么之前我忽略了它。（把它误读成“两个正整数”了吗？）无论如何已经删除了。 - Ry-

Answer 2

• 如果x == y，那么x - y == 0。
• 如果x < y，那么x - y < 0
• 如果x > y，那么x - y > 0

因此，我们希望将上述3个条件转换为cmp函数所需的3个单一输出值：

int cmp( int x, int y ) {
    return -1 if x < y
    return  0 if x == y
    return  1 if x > y
}

这可以被重新定义为：

int cmp( int x, int y ) return singleValue( x - y );

int singleValue( int diff ) {
    return -1 if diff < 0
    return  0 if diff == 0
    return  1 if diff > 0
}

现在考虑（并假设）计算机使用32位有符号整数的二进制补码，也称为int），那么所有负值都将具有最高有效位（MSB，第0位）设置为1。

对于32位整数，这意味着以下表达式对于所有负数都成立：

( anyNegativeNumber & 0x8000000 ) == 0x8000000

相反的情况也是成立的：所有正的非零整数的最高位都是 0。最后，所有值为零的数（int zero == 0）其所有位都被设置为 0。

( anyPositiveNumber & 0x8000000 ) == 0

如果我们查看MSB（最高位）并检查是否有其他位为1，结合上述singleValue函数的期望输出：

value | first bit | any other bits | desired output
    0 |         0 |              0 |           0b ( 0)
  122 |         0 |              1 |           1b ( 1)
 -128 |         1 |              0 | 11111...111b (-1)
 -123 |         1 |              1 | 11111...111b (-1)

我们可以通过掩码位直接从输入值中创建0和1，但是-1是一个特殊情况，但我们可以像这样处理它：

int diff = x - y; // so only the 1st and last bits are set

如果差异的第一位被设置，则返回-1。如果差异值为0，则返回0。否则返回1。

return ( diff & 0x80000000 == 0x80000000 ) ? 0xFFFFFFFF : ( diff != 0 );

这可以压缩：

int diff;
return ( ( ( diff = x - y ) & 0x80000000 ) == 0x80000000 ) ? 0xFFFFFFFF : ( diff != 0 );

但是仍然使用==和!=运算符，这可以通过利用单个位（第n位）值可以向右移动n位以将其转换为布尔值的事实来消除：

( diff = x - y ) >> 31 // evaluates to 1 if x < y, 0 if x == y or x > y

"

可以通过利用!!a对于所有非零值为1，对于零值为0的事实来消除diff != 0位：

"

!diff  // evaluates to 1 if diff == 0, else 0
!!diff // evaluates to 0 if diff == 0, else 1

我们可以将两者结合起来：

int diff;
return ( ( diff = x - y ) >> 31 ) ? -1 : !!diff;

这个操作中包含了一个分支语句（?:）和一个临时变量（diff），但是同样的函数也可以不使用分支语句。

可以看到，这个操作有三种可能的输出结果：

0xFFFFFFFF == 1111_1111 1111_1111 1111_1111 1111_1111 b
0x00000000 == 0000_0000 0000_0000 0000_0000 0000_0000 b
0x00000001 == 0000_0000 0000_0000 0000_0000 0000_0001 b

< p > < code >>> 运算符对于有符号值具有“符号扩展”的特性，这意味着：

1000 b >> 2 == 1110 b
0100 b >> 2 == 0001 b

如果第0位是1，则diff >> 31为1111..1111，否则为0000..0000。

每个单独的位的值可以表示为diff的函数：

a = ( diff >> 31 ) // due to sign-extension, `a` will only ever be either 1111..1111 or 0000..0000
b = !!diff         // `b` will only ever 1 or 0
c = a | b          // bitwise OR means that `1111..1111 | 0` is still `1111..1111` but `0000..0000 | 1` will be `0000..0001`.

或者只需：

c = ( diff >> 31 ) | ( !!diff );

将此代入上述表达式：

int diff = x - y;
return ( diff >> 31 ) | !!diff;

或者

int diff;
return diff = x - y, ( diff >> 31 ) | !!diff;

逗号运算符 必须使用，因为C语言不指定也不保证二元运算符操作数表达式的求值顺序，但逗号运算符的求值顺序是确定的。

由于这是一个内联函数，并且假设我们可以接受可变参数，那么我们可以消除 diff，因为我们只使用了 x 或者 y 一次：

return x = x - y, ( x >> 31 ) | !!x;

这是我的测试程序和使用GCC得到的输出：

#include <stdio.h>

int cmp(int x, int y) {

    return x = x - y, ( x >> 31 ) | !!x;
}

int main() {

    printf( "cmp( 1, 2 ) == %d\n", cmp( 1,2 ) );
    printf( "cmp( 2, 2 ) == %d\n", cmp( 2,2 ) );
    printf( "cmp( 2, 1 ) == %d\n", cmp( 2,1 ) );
}

输出：

cmp( 1, 2 ) == -1
cmp( 2, 2 ) == 0
cmp( 2, 1 ) == 1

现在这个算法并不完美，因为如果x和y都是大数且x为负数，例如(-4000000000) - (4000000000)，就会出现整数溢出的问题。虽然可以检查此条件，但这样做违背了让代码尽可能简洁的初衷，而且还需要添加处理错误情况的代码。在这种情况下，更好的方法是仅检查用户提供的输入，而不是检查函数参数值。

TL;DR:

int cmp(int x, int y) {

    return x = x - y, ( x >> 31 ) | !!x;
}

- Dai

---

我喜欢答案的详细说明。感谢您解释每个步骤。 - an4s

在编程中，从一个大正数中减去一个大负数会导致整数溢出。假设类似于gcc的行为，这将导致一个负数，因此断言“x>y ==> x-y>0”并不总是正确的。 - rici

Answer 3

我可以建议这个吗：

int cmp(int x, int y) {
    return (x < y) ? -1 : (x > y);
}

"

x > y比较中，当x较大时为1，否则为0。虽然Ryan的回答更短，但我认为这个版本仍然清楚地展示了代码的意图。

"

- Tor Klingberg