Comparing two integers without any comparison

Question

Is it possible to find the greatest of two integers without any comparison? I found some solutions:

if(!(a/b)) // if a is less than b then division result will be zero.
{
    cout << " b is greater than a";
}
else if (!(a-b)) // we know a is greater than or equal to b now.  check whether they are equal.
{
    cout << "a and b are equal";
}
else
    cout << "a is greater than b";

But if(c) or if(!c) is a comparison to zero. In addition it doesn't work for negative numbers. In fact I need a solution that avoids any if statement. Instead I should use switch statements and arithmetic operators. ThanX.

Answer 1

Subtract them and check the sign using nasty bit twiddling hacks
http://graphics.stanford.edu/~seander/bithacks.html

Don't do this in production code if the other programmers know where you live.

Answer 2

Here's a fun bit-twiddling version that doesn't have any conditional branches.

int g = (int)"greater";
int l = (int)"less";
int e = (int)"equal";

int a = 7;
int b = 10;

char *result = (char*)((((a - b) >> 31) & l) | (((b - a) >> 31) & g) | ((~((a - b) | (b - a))) >> 31) & e);
cout << result;

Answer 3

Not one of the samples presented in the question or any of the answers thus far protects from division by zero. Why on earth are you trying to avoid an 'if' statement? I suspect homework question about ?: operators.

cout << "Maximum is: " << ((a>b)?a:b)

There we go.

It's not possible to compare two numbers without a comparison. You can fudge it and do an indirect operation, but at the end of the day you're comparing something. Trust the compiler to optimize the code and select the best operations.

Answer 4

You might exploit the fact that the sign of the calculation a - b depends on which number is greater. This is used in many implementations of comparison. But I believe you'll never be able to completely avoid comparison. In this case, you still at least need to evaluate the contents of the sign flag on the processor.

If you just need to display the lower number you can also use arithmetic tricks:

result = ((a + b) - sqrt((a - b) * (a - b))) / 2

EDIT erm … you're allowed to use switch?

I should use switch statements and arithmetic operators.

switch is basically the same as chained if and as such it also uses comparison. This sounds as if you should indeed just compare to zero to see what sign a - b has.

Answer 5

char c;
c=0x3D + (!(b/a) && (a-b)) - (!(a/b) && (a-b));
printf("a %c b",c);

Answer 6

(!(a/b) ?  cout << " b is greater than a" : (!(b-a) ? cout << "a and b are equal" :  cout << "a is greater than b") :  cout << "a is greater than b");

That gets a bit messy though

Edit: Is this homework?

Answer 7

I just cant see any good reason to do that : who would want to program without "if" ?

a possible answer is :

( ( a + b ) + abs ( a -b ) ) / 2

I guess "abs" just hides a "if" somewhere, just as the ternary operator that is just another name for "if" ...

Answer 8

The Perverse Idea: use an array of function pointers. Then with some arithmetic and bitwise operations get an index into that array.

Answer 9

As a pointless exercise, here's a way of implementing a cond function - to serve the purpose of if, supposing it (and switch, and ?:) had somehow disappeared from the language, and you're using C++0x.

void cond(bool expr, std::function<void ()> ifTrue, std::function<void ()> ifFalse)
{
    std::function<void ()> choices[2] = { ifTrue, ifFalse };
    choices[expr == false]();
}

e.g.

cond(x > y,
    /*then*/ [] { std::cout << "x is greater than y"; },
    /*else*/ [] { std::cout << "x is not greater than y"; });

Like I say, pointless.

Answer 10

Try this, tested it, works well.

public static int compare(int a, int b)
{
    int c = a - b;
    return (c >> 31) & 1 ^ 1;
}

Answer 11

I think this method is better than others, you can use this logic c and java both programming languages but int should be of 4 byte if int is of 2 byte then make 15 byte right shift instead of 31 byte.

enter code here

#include<stdio.h>

main()
{
   int a, b;
   printf("Enter three numbers\n");
   scanf("%d %d", &a, &b);
   printf("Largest number is %d \n",findMax( a,b ));
}
int findMax( int x, int y)
{
  int z = x - y;
  int i  = (z  >>  31)  &  0x1;
  printf("i = %d shift = %d \n", i, (z>>31));
  int  max  =  x - i  *  z;
  return max;
}

Answer 12

To get the greatest number without using comparison/relational operator

void PrintGreatestNumber(int a, int b)
{
   int [] x = new int[] { -1, 0, 1 };
   int greatestNumber =  ((a+b)+ x[ 1 + ((a-b) >> 31) - (-(a-b) >> 31)] * (a-b)) /2;  
   Console.WriteLine(greatestNumber);
}

Answer 13

void greater(int a, int b) {
    int c = a - b;
    switch(c) {
        case 0:
            cout << "a and b are equal" << endl;
            break;
        default:
            int d = c & (1<<31);
            switch(d) {
                case 0:
                    cout << "a is bigger than b" << endl;
                    break;
                default:
                    cout << "a is less than b" << endl;
            }
    }
}