I need to compare two integer using Bit operator. I faced a problem where I have to compare two integers without using comparison operator.Using bit operator would help.But how?
Lets say a = 4; b = 5;
We have to show a is not equal to b. But,I would like to extend it further ,say,we will show which is greater.Here b is greater..
You need at least comparison to 0 and notionally this is what the CPU does for a comparison. e.g.
Equals can be modelled as ^ as the bits have to be the same to return 0
(a ^ b) == 0
if this was C you could drop the == 0 as this can be implied with
!(a ^ b)
but in Java you can't convert an int to a boolean without at least some comparison.
For comparison you usually do a subtraction, though one which handles overflows.
(long) a - b > 0 // same as a > b
subtraction is the same as adding a negative and negative is the same as ~x+1 so you can do
(long) a + ~ (long) b + 1 > 0
to drop the +1 you can change this to
(long) a + ~ (long) b >= 0 // same as a > b
You could implement + as a series of bit by bit operations with >> << & | and ^ but I wouldn't inflict that on you.
You cannot convert 1 or 0 to bool without a comparison operator like Peter mentioned. It is still possible to get max without a comparison operator.
I'm using bit (1 or 0) instead of int to avoid confusion.
bit msb(x):
return lsb(x >> 31)
bit lsb(x):
return x &1
// returns 1 if x < 0, 0 if x >= 0
bit isNegative(x):
return msb(x)
With these helpers isGreater(a, b) looks like,
// BUG: bug due to overflow when a is -ve and b is +ve
// returns 1 if a > b, 0 if a <= b
bit isGreater_BUG(a, b):
return isNegative(b - a) // possible overflow
We need two helpers functions to detect same and different signs,
// toggles lsb only
bit toggle(x):
return lsb(~x)
// returns 1 if a, b have same signs (0 is considered +ve).
bit isSameSigns(a, b):
return toggle(isDiffSigns(a, b))
// returns 1 if a, b have different signs (0 is considered +ve).
bit isDiffSigns(a, b):
return msb(a ^ b)
So with the overflow issue fix,
// returns 1 if a > b, 0 if a <= b
bit isGreater(a, b):
return
(isSameSigns(a, b) & isNegative(b - a)) |
(isDiffSigns(a, b) & isNegative(b))
Note that isGreater works correctly for inputs 5, 0 and 0, -5 also.
It's trickier to implement isPositive(x) properly as 0 will also be considered positive. So instead of using isPositive(a - b) above, isNegative(b - a) is used as isNegative(x) works correctly for 0.
Now max can be implemented as,
// BUG: returns 0 when a == b instead of a (or b)
// returns a if a > b, b if b > a
int max_BUG(a, b):
return
isGreater(a, b) * a + // returns 0 when a = b
isGreater(b, a) * b //
To fix that helper isZero(x) is used,
// returns 1 if x is 0, else 0
bit isZero(x):
// x | -x will have msb 1 for a non-zero integer
// and 0 for 0
return toggle(msb(x | -x))
So with the fix when a = b,
// returns 1 if a == b else 0
bit isEqual(a, b):
return isZero(a - b) // or isZero(a ^ b)
int max(a, b):
return
isGreater(a, b) * a + // a > b, so a
isGreater(b, a) * b + // b > a, so b
isEqual(a, b) * a // a = b, so a (or b)
That said, if isPositive(0) returns 1 then max(5, 5) will return 10 instead of 5. So a correct isPositive(x) implementation will be,
// returns 1 if x < 0, 0 if x >= 0
bit isPositive(x):
return isNotZero(x) & toggle(isNegative(x))
// returns 1 if x != 0, else 0
bit isNotZero(x):
return msb(x | -x)
int findMax( int x, int y)
{
int z = x - y;
int i = (z >> 31) & 0x1;
int max = x - i * z;
return max;
}
Reference: Here
a ^ b = c // XOR the inputs
// If a equals b, c is zero. Else c is some other value
c[0] | c[1] ... | c[n] = d // OR the bits
// If c equals zero, d equals zero. Else d equals 1
Note: a,b,c are n-bit integers and d is a bit
The solution in java without using a comparator operator:
int a = 10;
int b = 12;
boolean[] bol = new boolean[] {true};
try {
boolean c = bol[a ^ b];
System.out.println("The two integers are equal!");
} catch (java.lang.ArrayIndexOutOfBoundsException e) {
System.out.println("The two integers are not equal!");
int z = a - b;
int i = (z >> 31) & 0x1;
System.out.println("The bigger integer is " + (a - i * z));
}
