Cognzant Technology Solutions Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
Just an edit, you could use x>=y for one case to cover if both numbers end up being equal
int max(int i, int j)
{
int iMax = i - j;
unsigned int uiMax = static_cast<unsigned int> (iMax);
uiMax = uiMax >> 31;
return (j*uiMax) + (i * (1-uiMax));
}
1 bitwise op, 3 adds, 2 multiplies.
The top answer uses much cheaper operations. Something like 4 bit ops and 1 or 2 adds.
Here is an approximate answer and untested... might have to replace 31 with bigger/smaller number...
double min(double x, double y) {
int n = 1 << 31;
double min = pow (pow (x, -n) + pow (y, -n), n);
}
double max(double x, double y) {
int n = 1 << 31;
double min = pow (pow (x, n) + pow (y, n), n);
}
This answer is not what an interviewer would have wanted, but under many compilers, this answer technically not generate any branch instructions, and instead uses conditional adds, or else uses the same sort of bit hacks discussed in this thread. Many compilers are smart enough to use the approaches in this thread without a human writing the code that way.
// we want to find the minimum of x and y
- fresherparty September 10, 2012int x; int y;
// the result goes here
int r;
// min(x, y)
r = y ^ ((x ^ y) & -(x < y));
It works because if x < y, then -(x < y) will be all ones, so r = y ^ (x ^ y) & ~0 = y ^ x ^ y = x. Otherwise, if x >= y, then -(x < y) will be all zeros, so r = y ^ ((x ^ y) & 0) = y.
NOTE:
On some machines, evaluating (x < y) as 0 or 1 requires a branch instruction, so there may be no advantage.
Reference: graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
To understand this problem more clearly you may like to watch
youtube.com/watch?v=C95-S1jsbMo