ISourceCode

Make the frequent cases fast and the rare case correct

Program to find Maximum of two numbers without using comparison operators and conditional statements

This requires a binary hack at one step

For 2 nos where a>b we can conclude a-b>0. but again we are using conditional statement to check > 0.

so does (a-b) tell us anything. Yes it does the resultant binary representation of this value can be made use.

for a=8 and b =10 (a-b) = -2 its binary representation is 110.
now let us take a variable msb which will be set to 1 if (a-b) is negative and 0 if (a-b) is positive. this is done by (a-b)>>31 & 0x1.
thus when this variable msb is multiplied with (a-b) and added to the first variable we get the max value.
integer 4 bytes
-2 = 1000 0000 0000 0000 0000 0000 0000 0010

-2 >> 31 =
0000 0000 0000 0000 0000 0000 0000 0101 AND
0000 0000 0000 0000 0000 0000 0000 0001
= 1

hence after right shift 31 times for a negative number the msb ends up in the lsb and for a positive number lsb after 31 right shift is 0.
AND is to make sure we get a unique value for each case i.e with 0 or 1

for a=8 and b=10
8 – 1 * (-2)

for a=10 and b=8
10 – 0 * (2)

for a = -8 and b =-10
-8 – 0 * (2)

#include <iostream>
using namespace std;
int main()
{
	int a = 8;
	int b = 10;	
	int diff,msb,max;	
	diff = a - b;
	msb = (diff >> 31) & 0x1;
	max = a - msb * diff;
	cout<<"Maximum of two numbers is : "<<max<<endl;
	return 0;
}

OUTPUT:

laptop:~/code$ ./a.out
Maximum of two numbers is : 10

for a = -8 and b = -10
laptop:~/code$ ./a.out
Maximum of two numbers is : -8

You can refer to Bit Twiddling Hacks article from Stanford for more of similar questions

Thanks for reading !

One response to “Program to find Maximum of two numbers without using comparison operators and conditional statements

  1. thrilok January 22, 2011 at 8:51 am

    well articulated !!! very helpful…
    thanks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: