Bitwise operation in C to compare two integers

Question

I recently got a quiz in one of my classes. Question below:

Write a function (referred to cmp) in C, which takes two integers ( xand y) and returns: -1if x< y, 0if x= y, 1if x> y. Write cmpas concise as possible.

The shortest function I could think of:

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

But I feel that there may be a bit of manipulation that I could use to do this more briefly. Perhaps a combination of &and ^? This has bothered me over the past few days, and I wanted to know if there IS an better way to do this?

Answer 1

“as concise as possible” is an extremely vague requirement for a quiz. Do you expect to play golf? Does spaces and parentheses remove more concise? In any case, there is one solution using arithmetic according to the results of comparisons:

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

Answer 2

• If x == y, then x - y == 0.
• If x < y, thenx - y < 0
• If x > y, thenx - y > 0

So, we want to see if we can convert the 3 conditions described in 3 points above into 3 single output values ​​needed for your function cmp:

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

This can be redefined as follows:

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- , aka 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

1- , -1. diff 0, 0 Else return 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

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;

(?:) (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..1111, 0 th 1, 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;
}

Answer 3

May I suggest the following:

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

The comparison x > yis 1 when it is xmore, and 0 is not. Ryan's answer is shorter, but I think this version still clearly shows what the code should do.