# An interview question: Compare two integers without +,-,*,/ or > and <

Our team architect has asked us this question which is said to be an interview question from Microsoft long time ago:

Please implement one function which accepts two integers as input and generate the following result accordingly:
``````If a > b, return 1,
if a = b, return 0,
if a < b, return -1``````
For simplification reason here we can just consider unsigned int ( that is, all importing parameter of integers are greater than or equal to 0 ).
Inside the implementation, you are NOT allowed to use +, -, *, /, > and < for comparison.
There must be multiple ways to achieve it, here below is just one among them. Even we are not allowed to use four arithmetic operations and > or <, we can still leverage the bit operation supported on Integer.
The basic idea is, say we have 6 and 5 for comparison.
``````Binary format of 6: 0110
Binary format of 5: 0101``````
If we can generate the biggest-sub-bits-series which differentiate the two integers, in the example above it is 0010( since the third bit of both integer are equal ), then we can simply know which is bigger by making bit AND operation:
``````0110 & 0010  = 10 which <> 0.
0101 & 0010 = 0``````
So we can know 0110 > 0101.
Another example – compare 4 and 3
``````Binary format of 4: 0100
Binary format of 3: 0011``````
The biggest-sub-bits-series: 0100
``````0100 & 0100 = 0100 which <> 0
0011 & 0100 = 0``````
So 0100 > 0011.

# Solution in JavaScript

``````function compare(a,b){
var diff = a ^ b;
if( diff == 0)
return 0;
diff = diff | ( diff >> 1 );
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
diff ^= diff >> 1;
return  ( a & diff )? 1:-1;
}

console.log(compare(1,2));
console.log(compare(3,2));
console.log(compare(300,2));
console.log(compare(3000,2));
console.log(compare(3000,3000));
console.log(compare(3000,3001));``````
Output: # Solution in Java

``````public static int compare(int a, int b){
int diff = a ^ b;
if( diff == 0)
return 0;
diff = diff | ( diff >> 1 );
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
diff ^= diff >> 1;
return  ( (a & diff) == 0 )  ? -1 : 1;
}
System.out.println(compare(1,2));
System.out.println(compare(3,2));
System.out.println(compare(300,2));
System.out.println(compare(3000,2));
System.out.println(compare(3000,3000));
System.out.println(compare(3000,3001));``````
Output: # Solution in ABAP

Since it is not possible to directly perform bit operation on integer in ABAP, in my blog Bitwise operation ( OR, AND, XOR ) on ABAP Integer I simulate these three operations with the help of ABAP internal table. Still it is not enough, the bit shift operation like >> and << are also required to finish this exercise, so I make further enhancement, adding two new methods SHIFT_RIGHT and SHIFT_LEFT in ZCL_INTEGER, which could be found from my github.
Now all prerequisite to finish it using ABAP are fulfilled.
Here it is: Source code:
``````METHOD compare.

DEFINE shift_right.
lv_diff = a->get_raw_value( ).
a->shift_right( &1 ).
lo_diff = zcl_integer=>value_of( lv_diff ).
a = lo_diff->or( a ).
END-OF-DEFINITION.

DATA(a) = zcl_integer=>value_of( iv_a ).
DATA(b) = zcl_integer=>value_of( iv_b ).
DATA: lv_diff TYPE int4,
lo_diff TYPE REF TO zcl_integer.
a = a->xor( b ).
IF a->get_raw_value( ) IS INITIAL.
rv_result = 0.
RETURN.
ENDIF.

shift_right 1.
shift_right 2.
shift_right 4.
shift_right 8.
shift_right 16.

lv_diff = a->get_raw_value( ).
a->shift_right( 1 ).
lo_diff = zcl_integer=>value_of( lv_diff ).
a = lo_diff->xor( a ).

DATA(lo_origin_a) = zcl_integer=>value_of( iv_a ).
rv_result = zcl_integer=>value_of( lo_origin_a->and( a )->get_raw_value( ) )->get_raw_value( ).

rv_result = COND #( WHEN rv_result IS INITIAL THEN -1 ELSE 1 ).
ENDMETHOD.``````
Test code:
``````WRITE:/ zcl_comparator=>compare( iv_a = 1 iv_B = 2 ).

WRITE:/ zcl_comparator=>compare( iv_a = 3 iv_B = 2 ).

WRITE:/ zcl_comparator=>compare( iv_a = 300 iv_B = 2 ).

WRITE:/ zcl_comparator=>compare( iv_a = 3000 iv_B = 2 ).

WRITE:/ zcl_comparator=>compare( iv_a = 3000 iv_B = 3000 ).

WRITE:/ zcl_comparator=>compare( iv_a = 3000 iv_B = 3001 ).``````
Test output: # Reference

Most Significant Bit introduced in Wikipedia

/    You must be Logged on to comment or reply to a post.
• In ABAP we have the awesome internal tables. Put the a and b values in an internal table and sort it. Ta-dah! 🙂

``````if a = b.
result = 0.
exit.
endif.

ls-field = a.
append ls to itab.
ls-field = b.
append ls to itab.

sort itab.
read itab into ls index 1.
* Default sort is ascending, so if a is in the first record then a < b
if ls-field = a.
result = -1.
else.
result = 1.
endif.``````

I better be hired now. 🙂

• Jerry Wang Post author

Hello Jelena,

An awesome solution 🙂

Best regards,

Jerry

• Follow-up question: Implement sort without using +, -, /, *, >, or <.