C中的按位运算比较两个整数

Question

我最近在我的一个课程中接受了测验.问题如下:

cmp在C中编写一个函数(调用),它接受两个整数(x和y)并返回:-1if x< y,0if x= y,1if x> y.写得cmp尽可能简洁.

我能想到的最简洁的功能是:

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

但我有一种感觉,我可以用一些操作来更简洁地做到这一点.也许是&和^？的结合？这已经困扰了我过去的几天,我想知道是否有其实IS更好的方式来做到这一点？

Answer 1

"尽可能简洁"是对测验的极其模糊的要求.你有望打高尔夫吗？删除空格和括号是否使其更简洁？无论如何,这是一个使用算术比较结果的解决方案:

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

Answer 2

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

所以我们想看看我们是否可以将上面3个要点中描述的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,0th位)1.

对于32位整数,这意味着以下表达式适用于所有负数:

( anyNegativeNumber & 0x8000000 ) == 0x8000000

反之亦然:所有正非零整数的MSB均为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

如果设置了diff的第1位,则返回-1.如果是diff值0则返回0 Else return1

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

这可以压缩:

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

这仍然是使用==和!=运算符...这可以通过利用单比特(n第三位)值可以被移位n-bits以将其转换为布尔值的事实来消除:

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

该diff != 0位可利用的事实,被淘汰!!a是1所有非零值和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;

此操作在it(?:)和临时变量(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

该>>经营者具有"符号扩展"为符号值,这意味着:

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

如果是,那diff >> 31将是,否则是.1111..1111010000..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;
}