Here's a hint for anyone interested in trying this.
To find the answer, you only have to compare 1 bit -- the highest order bit where the two numbers differ.
So the first trick is to create a bit-mask with a 1 in the highest order bit where the two numbers differ and 0's elsewhere. Exclusive-or (which leaves 1's everywhere the bits differ) and a technique known as "bit-smearing" are useful here. Bit-smearing turns this
00100101
into this
00111111 (highest-order 1 bit is "smeared out" over the lower-order bits)
It's done like this (z is the value to smear)
Code:
z |= z >> 16; // leave out this one ...
z |= z >> 8; // ... and this one to test with just 8 bit numbers
z |= z >> 4;
z |= z >> 2;
z |= z >> 1;
Does anyone know a way of solving this problem without using the above technique? To restate the problem (as the OP has given it) : write this function
Code:
int isitGreater(int x, int y) {
// Return 1 if x is greater than y, 0 otherwise.
// Use only these operators and no control statements (if, for, etc)
// ! ~ & ^ | + << >>
// I've assumed that you can create local variables.
}
I personally don't see how the + is going to come into it, at least not in the naive way since it has problems with overflow. My solution uses ! (in the common !! way to return 1 or 0 from non-zero or zero) and ~ & ^ | <<