Comparison without relational operators
Source: Quant interview at Religare Technova
Problem: Write a C program to compare two integers without using relational operators (== != < <= > >=)
Problem: Write a C program to compare two integers without using relational operators (== != < <= > >=)
Solution:
Highlight the part between the * symbols for the answer.
* Idea: subtract and inspect the sign without any relational operator.
Equality: a == b iff (a ^ b) == 0, i.e. use if (!(a ^ b)).
Greater/less: with 64-bit ints, d = a - b; the sign bit of d tells the answer: ((uint64_t)(a - b)) >> 63 is 1 iff a < b (Sanjoy's version). Equivalently, without shifts: if (d - abs(d)) is nonzero, d was negative so b > a; otherwise a > b (NG's version).
A branch-free max uses the same sign trick: max = a - ((a - b) & ((a - b) >> 63)) for 64-bit ints. (Caveats from the thread: watch out for integer overflow in a - b, and abs() itself is usually implemented with a comparison - the sign-bit version avoids that.)
Solution by Sanjoy and NG from the comments. *
int d = a - b;
ReplyDeleteif(d)
{
// a is not equal to b
if( d - abs(d) )
{
// d was negative => b > a
}
else
{
// d was positive => a > b
}
}
else
{
// a == b :)
}
In the implementation of abs(), a relational operator is used to determine whether the number passed is less than or greater than zero.
Deletesay 2 nos are a and b in their n-bit representations. subtract b from a by taking 2's complement of b and adding it to a, multiply it by 100...(n-1 0s). then right-shift the no n-1 times. call it c. multiply c by b. then complement c, multiply it by a. now max = b*c+a*(complement of c)
ReplyDeleteWill this work?
ReplyDeleteint compare(int64_t a, int64_t b)
{
return ((uint64_t) (a - b)) >> 63;
}
Sorry but i couldn't make it simpler..
ReplyDelete#include
#include
int maximum(int x,int y)
{
return(x+y+sqrt(-2*y*x +x*x + y*y))/2;
}
int main()
{
int a,b,c;
scanf("%d%d",&a,&b);
c=maximum(a,b);
printf("\n%d",c);
}
int main () {
ReplyDeleteint a,b;
printf ( "enter the two values u like to compare\n");
scanf (" %d %d",&a,&b);
if (!(a ^ b))
printf ("both are equal\n);
else
printf ("both are not equal\n");
}
int ret_max(int a, int b){
ReplyDeleteint c=a,d=b;
while (c&d){
c&=(c-1);
c&=(d-1);
}
if (c)
return a;
else // also takes care of equality
return b;
}
//to check if no's are equal
ReplyDeleteif(!(a^b))
print(equal)
else if (a/b)
print(b greater than a)
else
print(a greater than b)
//this should be vice versa
Deleteelse if (a/b)
print(a greater than b)
else
print(b greater than a)
//also this will not work if one number is negative for example a = 1 and b = -5.
Clean logic - but see Sandeep's catch below: abs() itself is implemented with a relational test, so this arguably smuggles one in. The bit-trick versions (extracting the sign bit) are the honest way. Also watch for overflow when a and b are large and of opposite signs. (replied using AI)
ReplyDeleteThe right idea - compute the sign of a-b and use it as a 0/1 mask to select between a and b - though the multiply-then-shift description is convoluted. Sanjoy's version below ((uint64_t)(a-b) >> 63) is the same trick in one line, and the mask generalization (max = b + ((a-b) & ~(signmask...))) is the classic branchless max. (replied using AI)
ReplyDeleteAlmost - one caveat: a - b can overflow int64_t when a and b have opposite signs and large magnitudes (a = INT64_MIN, b = 1), which is undefined behavior in C. The robust version does the subtraction in unsigned arithmetic or widens first. Otherwise, yes: the top bit of a-b is exactly "a < b". (replied using AI)
ReplyDeleteNice math trick - it is max = (x + y + |x - y|)/2 in disguise, since sqrt((x-y)^2) = |x-y|. Correct for small integers; in practice floating-point sqrt loses exactness for large int64 values, but for the interview puzzle it is a valid and elegant answer. (replied using AI)
ReplyDeleteXOR handles the equality test cleanly (a^b == 0 iff a == b). The problem also wants you to distinguish a < b from a > b, though - that needs the sign-of-difference trick from the other comments. (replied using AI)
ReplyDeleteThe intended idea is nice: strip the lowest set bit from both numbers (c &= c-1) until one runs out of bits - the smaller number runs out first (works for non-negative integers). As written, though, c &= (d-1) looks like a typo for d &= (d-1). Also note it only applies to non-negative ints - two's-complement negatives have infinite sign bits. (replied using AI)
ReplyDeleteGood catch - abs() hides exactly the comparison the problem bans. (Pedantic footnote: branchless abs via (x + mask) ^ mask with mask = x >> 63 exists, so a charitable reading could allow it, but in an interview the spirit of the question rules it out.) (replied using AI)
ReplyDeleteTwo bugs, as the next commenter notes: the branches are swapped (a/b truncating to 0 means a < b, so it should print "b greater"), and integer division breaks for negative numbers and for b = 0. Works only for strictly positive integers with the branches fixed. (replied using AI)
ReplyDeleteBoth corrections confirmed - branch order and the negative-number (plus divide-by-zero) failure. Thanks for the audit. (replied using AI)
ReplyDelete