2

Possible Duplicate:
Find the maximum of two numbers without using if-else or any other comparison operator

isGreater:

if x > y  then return 1, else return 0

Example:

  • isGreater(4,5) = 0
  • isGreater(5,4) = 1

Legal operators: ! ~ & ^ | + << >>

isGreater is the function..

I tried:

int isGreater(int x, int y) {
    return (y+(~x+1)) >> 31 & 1;
}

but not working.. :(( Let me know what else I can do?

Community
  • 1
  • 1
hello
  • 29
  • 1
  • 2
  • 13
    What is with the endless stream of "how do I do X with some limited subset of the C operators?" type questions? – Oliver Charlesworth Jan 25 '11 at 21:56
  • 4
    Step 1. Please format your code using the `{}` button. Step 2. Please mark your homework with the [homework] tag. – S.Lott Jan 25 '11 at 21:57
  • 1
    @Oli, it's a common homework assignment, apparently. – Charles Salvia Jan 25 '11 at 21:59
  • @thkala: mostly - but `+` is binary and not bitwise...(unless it is a mistake). – Jonathan Leffler Jan 25 '11 at 21:59
  • @Oli: it looks like it's probably from a computer architecture class, where they're only allowed to use things that can be implemented with simple gates (and, or, not) or simple combinations of them (xor, adder, shifter). – Jerry Coffin Jan 25 '11 at 22:01
  • @Jonathan Leffler: while not totally accurate, I think that using "bitwise" reflects the intent of the question better... – thkala Jan 25 '11 at 22:03
  • can you provide a counter example to why that code is not working? It makes sense... you basically do y - x and return 1 if and only if that is negative (meaning x > y). (barring any architecture differences) – vmpstr Jan 25 '11 at 22:04
  • 1
    The title says "Maximum of two numbers" whereas the question itself suggests that you just want to test for `x > y` - which is it ??? – Paul R Jan 25 '11 at 22:20
  • @Jonathan - + can also be a unary operator, which isn't _exactly_ bitwise but can easily be implemented in terms of bitwise operations :p – Chris Lutz Jan 25 '11 at 22:28
  • @Chris: yes; plus is a unary 'do nothing' operator (as well as a meaningful binary operator), which is why unary plus was not a part of pre-standard C. – Jonathan Leffler Jan 25 '11 at 23:54
  • 2
    This is a reasonable homework assignment **for a math class**, not for a programming class. – R.. GitHub STOP HELPING ICE Jan 26 '11 at 05:29

2 Answers2

0

given x, y

try x + -y if < 0 then y is greater, if > 0 then x is greater.

-y = binary complement of y:

-y = (~(y-1))
<==>
-y = (~y)+1

From what I see, you do the binary complement with (~y +1)), which is the same.

Then bitshift >> 31 to get the MSB, and equal to 1.
Make sure to set parantheses, operator precedence !

 (y+-x) >> (31 & 1);
!=
 ((y+-x) >> 31) & 1;
Stefan Steiger
  • 78,642
  • 66
  • 377
  • 442
0

Too easy -- since you have + in the list of legal operators, you can trivially synthesize - (as others have noticed) and thus do a subtract and extract the sign. Its much more interesting if you leave out + (as it isn't a bitwise operator anyways) and answer the question with just bitwise ops (& | ^ ~) and shifts.

Of course, you could synthesize +/- from the bitwise ops and shifts, but there's actually an easier way.

Chris Dodd
  • 119,907
  • 13
  • 134
  • 226
  • That restriction does make it more interesting, though I can't +1 in good conscience as you're really asking a separate question. The solution I have in mind requires 5 right-shifts, which I suspect is the minimum possible number. – j_random_hacker Jan 26 '11 at 02:21