# greatest of two numbers

Discussion in 'C Programming' started by aarklon@gmail.com, Dec 7, 2007.

1. ### Guest

Hi all,

The following question is asked frequently in interviews

How to find the greatest of 2 numbers without using relational
operators ?

the solution i have seen is

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

is there any better solution than this ....?????

, Dec 7, 2007

2. ### Richard HeathfieldGuest

said:

> Hi all,
>
> The following question is asked frequently in interviews
>
> How to find the greatest of 2 numbers without using relational
> operators ?

The proper answer is: badly. The relational operators are there for a
reason.

> the solution i have seen is
>
> ( a+b + abs(a-b) ) /2 ;
>
> is there any better solution than this ....?????

Yes - use the relational operators! It's a pretty good bet that abs() uses
one anyway, and one major advantage of using a relational operator rather
than the code you show is that you avoid the two additions, the
subtraction, possibly a function call, and a division. You also avoid no
fewer than three overflow hazards.

So my answer to the interviewer would be: "sir (or madam), I guess that you
are looking for a trick answer, but I don't have one. All I have is the
correct answer, which is - use a relational operator. That is the proper
engineering solution. I can fully accept that there might be a curious and
interesting trick for doing this, but - whatever it is - it will not be as
sound a solution as using a relational operator. If you want to hire
someone who can play programmatic tricks, you don't want me; please look
elsewhere, because I am a programmer, not a stage magician, and I am
looking for a client who understands this. But if you are after someone
who can point at the Emperor and say 'why doesn't that silly man go and
get dressed?', someone who can write clear, concise, obvious code, and use
the right operators for the right jobs, then please ask your next
question."

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999

Richard Heathfield, Dec 7, 2007

3. ### jaysomeGuest

On Fri, 07 Dec 2007 07:46:04 +0000, Richard Heathfield
<> wrote:

> said:
>
>> Hi all,
>>
>> The following question is asked frequently in interviews
>>
>> How to find the greatest of 2 numbers without using relational
>> operators ?

>
>The proper answer is: badly. The relational operators are there for a
>reason.
>
>> the solution i have seen is
>>
>> ( a+b + abs(a-b) ) /2 ;
>>
>> is there any better solution than this ....?????

>
>Yes - use the relational operators! It's a pretty good bet that abs() uses
>one anyway, and one major advantage of using a relational operator rather
>than the code you show is that you avoid the two additions, the
>subtraction, possibly a function call, and a division. You also avoid no
>fewer than three overflow hazards.

Agree.

>So my answer to the interviewer would be: "sir (or madam), I guess that you
>are looking for a trick answer, but I don't have one. All I have is the
>correct answer, which is - use a relational operator. That is the proper
>engineering solution. I can fully accept that there might be a curious and
>interesting trick for doing this, but - whatever it is - it will not be as
>sound a solution as using a relational operator. If you want to hire
>someone who can play programmatic tricks, you don't want me; please look
>elsewhere, because I am a programmer, not a stage magician, and I am
>looking for a client who understands this. But if you are after someone
>who can point at the Emperor and say 'why doesn't that silly man go and
>get dressed?', someone who can write clear, concise, obvious code, and use
>the right operators for the right jobs, then please ask your next
>question."

Or perhaps that was the "trick" answer the interviewer was looking
for.

You're hired.

Best regards
--
jay

jaysome, Dec 7, 2007
4. ### Klutz_wdGuest

> So my answer to the interviewer would be: "sir (or madam), I guess that you
> are looking for a trick answer, but I don't have one. All I have is the
> correct answer, which is - use a relational operator. That is the proper
> engineering solution. I can fully accept that there might be a curious and
> interesting trick for doing this, but - whatever it is - it will not be as
> sound a solution as using a relational operator. If you want to hire
> someone who can play programmatic tricks, you don't want me; please look
> elsewhere, because I am a programmer, not a stage magician, and I am
> looking for a client who understands this. But if you are after someone
> who can point at the Emperor and say 'why doesn't that silly man go and
> get dressed?', someone who can write clear, concise, obvious code, and use
> the right operators for the right jobs, then please ask your next
> question."
>

funny!

Klutz_wd, Dec 7, 2007
5. ### Marco ManfrediniGuest

wrote:
> Hi all,
>
> The following question is asked frequently in interviews
>
> How to find the greatest of 2 numbers without using relational
> operators ?
>
> the solution i have seen is
>
> ( a+b + abs(a-b) ) /2 ;
>
> is there any better solution than this ....?????

Sure:

int max(int x, int y)
{
int d=x-y;
return y + d & ((~(d^((x^y)&(d^x))))>>31);
}

Watch out for over/underflows though.

Marco Manfredini, Dec 7, 2007
6. ### Marco ManfrediniGuest

Marco Manfredini wrote:
> return y + d & ((~(d^((x^y)&(d^x))))>>31);

return y + (d & ((~(d^((x^y)&(d^x))))>>31));

SRY

Marco Manfredini, Dec 7, 2007
7. ### Thomas X. IversonGuest

On 12ÔÂ7ÈÕ, ÏÂÎç3Ê±46·Ö, Richard Heathfield <> wrote:
> said:
>
> > Hi all,

>
> > The following question is asked frequently in interviews

>
> > How to find the greatest of 2 numbers without using relational
> > operators ?

>
> The proper answer is: badly. The relational operators are there for a
> reason.
>
> > the solution i have seen is

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

>
> > is there any better solution than this ....?????

>
> Yes - use the relational operators! It's a pretty good bet that abs() uses
> one anyway, and one major advantage of using a relational operator rather
> than the code you show is that you avoid the two additions, the
> subtraction, possibly a function call, and a division. You also avoid no
> fewer than three overflow hazards.
>
> So my answer to the interviewer would be: "sir (or madam), I guess that you
> are looking for a trick answer, but I don't have one. All I have is the
> correct answer, which is - use a relational operator. That is the proper
> engineering solution. I can fully accept that there might be a curious and
> interesting trick for doing this, but - whatever it is - it will not be as
> sound a solution as using a relational operator. If you want to hire
> someone who can play programmatic tricks, you don't want me; please look
> elsewhere, because I am a programmer, not a stage magician, and I am
> looking for a client who understands this. But if you are after someone
> who can point at the Emperor and say 'why doesn't that silly man go and
> get dressed?', someone who can write clear, concise, obvious code, and use
> the right operators for the right jobs, then please ask your next
> question."
>
> --
> Richard Heathfield <http://www.cpax.org.uk>
> Email: -http://www. +rjh@
> Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
> "Usenet is a strange place" - dmr 29 July 1999

you are right , to write a program simply and stupid is the best way
for developing and maintaining , algorithm is not the most important
thing in developing
Keep It Simple , Stupid!!!

the author's answer is good enough , i have no idea about the better
solution

Thomas X. Iverson, Dec 7, 2007
8. ### James KuyperGuest

wrote:
> Hi all,
>
> The following question is asked frequently in interviews
>
> How to find the greatest of 2 numbers without using relational
> operators ?
>
> the solution i have seen is
>
> ( a+b + abs(a-b) ) /2 ;
>
> is there any better solution than this ....?????

As people have pointed out, this is a stupid question. The solution you
have works fine as long as it doesn't overflow. Still, it would be nice
to avoid the overflow. If these were floating point numbers, all you
would have to do is divide by 2 before overflow can happen:

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

(There's no free lunch: with the corresponding expression for floating
point numbers you'd have to worry about loss of precision due to underflow)

Unfortunately, since this is integer arithmetic, the result is only an
approximation to the correct number. It is inaccurate due to the fact
that 2*(n/2) != n if n is odd. This can be fixed up by using a%2 and b%2
in some clever fashion that I'm leaving as an exercise for the reader,
because this IS a stupid question and I don't want to bother figuring it
out for myself.

James Kuyper, Dec 7, 2007
9. ### Guest

On Dec 7, 6:33 am, wrote:
> Hi all,
>
> The following question is asked frequently in interviews
>
> How to find the greatest of 2 numbers without using relational
> operators ?
>
> the solution i have seen is
>
> ( a+b + abs(a-b) ) /2 ;
>
> is there any better solution than this ....?????

Stupid question, anyway :

#include <math.h>
int maximum(int x,int y){return(x+y+sqrt(-2*y*x +x*x + y*y))/2;}

, Dec 7, 2007
10. ### Neil CeruttiGuest

On 2007-12-07, <> wrote:
> Hi all,
>
> The following question is asked frequently in interviews
>
> How to find the greatest of 2 numbers without using relational
> operators ?

If the hopeful applicant gets this one right, the next question
is usually: How to make me a cambric shirt without no seem nor
needlework?

--
Neil Cerutti

Neil Cerutti, Dec 7, 2007
11. ### Chris DollinGuest

wrote:

> The following question is asked frequently in interviews

How do we know this?

--
Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

Chris Dollin, Dec 7, 2007
12. ### Guest

On Dec 7, 10:59 am, Chris Dollin <> wrote:
> wrote:
> > The following question is asked frequently in interviews

>
> How do we know this?
>
>

just google "C interview Questions"

, Dec 7, 2007
13. ### user923005Guest

On Dec 6, 9:33 pm, wrote:
> Hi all,
>
> The following question is asked frequently in interviews
>
> How to find the greatest of 2 numbers without using relational
> operators ?
>
> the solution i have seen is
>
> ( a+b + abs(a-b) ) /2 ;
>
> is there any better solution than this ....?????

I think it is moronic to ask for gag answers in an interview. I
imagine that they were looking for the solutions from this web site:
http://aggregate.org/MAGIC/
--------------------------------------------------------------------------------
Integer Minimum or Maximum
Given 2's complement integer values x and y, the minimum can be
computed without any branches as x+(((y-x)>>(WORDBITS-1))&(y-x)).
Logically, this works because the shift by (WORDBITS-1) replicates the
sign bit to create a mask -- be aware, however, that the C language
does not require that shifts are signed even if their operands are
signed, so there is a potential portability problem. Additionally, one
might think that a shift by any number greater than or equal to
WORDBITS would have the same effect, but many instruction sets have
shifts that behave strangely when such shift distances are specified.

Of course, maximum can be computed using the same trick: x-(((x-
y)>>(WORDBITS-1))&(x-y)).

Actually, the Integer Selection coding trick is just as efficient in
encoding minimum and maximum....
--------------------------------------------------------------------------------
Integer Selection
A branchless, lookup-free, alternative to code like if (a<b) x=c; else
x=d; is ((((a-b) >> (WORDBITS-1)) & (c^d)) ^ d). This code assumes
that the shift is signed, which, of course, C does not promise.
--------------------------------------------------------------------------------

Writing weird crap like that when you mean:
maxab = a > b ? a : b;
is just plain stupid. Since 80% of the cost of software is
maintenance, writing code that is hard to maintain is counter
productive.

Now, in the very rare case, where you have some deeply nested loop and
a comparison is slowing the code down, then you can do a quick web
search and find simple gag solutions like the above. You will notice
that these gag solutions have caveats in them, so they would have to
be both heavily tested and also heavily commented.

Chances are good that profile guided optimization of the simple
solution will work just as well, since the right branch will be
predicted most of the time.

user923005, Dec 7, 2007
14. ### WillemGuest

user923005 wrote:
) Chances are good that profile guided optimization of the simple
) solution will work just as well, since the right branch will be
) predicted most of the time.

Chances are that a good compiler will recognize the idiom and insert
the correct branchless assembly instructions.
There are instructions in the vein of load-when-carry-set, which are much
more suited to the task of writing, say, max() in branchless code.
Also, note that there are CPUs where shifting by N bits is O(N).

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Willem, Dec 7, 2007
15. ### Christopher Benson-ManicaGuest

[comp.lang.c] Chris Dollin <> wrote:
> wrote:

>> The following question is asked frequently in interviews

> How do we know this?

It certainly seems to be asked frequently by instructors.

--
C. Benson Manica | I appreciate all corrections, polite or otherwise.
cbmanica(at)gmail.com |
----------------------| I do not currently read any posts posted through
sdf.lonestar.org | Google groups, due to rampant unchecked spam.

Christopher Benson-Manica, Dec 7, 2007
16. ### CBFalconerGuest

user923005 wrote:
> wrote:
>
>> The following question is asked frequently in interviews
>>
>> How to find the greatest of 2 numbers without using relational
>> operators ?
>>
>> the solution i have seen is
>>
>> ( a+b + abs(a-b) ) /2 ;
>>
>> is there any better solution than this ....?????

>
> I think it is moronic to ask for gag answers in an interview. I
> imagine that they were looking for the solutions from this web
> site: <http://aggregate.org/MAGIC/>

.... snip quote of garbage from site ...

The only reasonable answer is one using relational operators, which
are provided in the language for various purposes, including
finding maxima. Other foolishness will virtually always exhibit
undefined areas.

int maxof(int a, int b) {
if (a > b) return a;
return b;
}

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

CBFalconer, Dec 8, 2007
17. ### Chris DollinGuest

wrote:

> On Dec 7, 10:59 am, Chris Dollin <> wrote:
>> wrote:
>> > The following question is asked frequently in interviews

>>
>> How do we know this?
>>

> just google "C interview Questions"

My dear boy, seeing lots of Google hits for "C interview questions"
doesn't tell us whether or not the original question is frequently
asked in interviews, which is what dol... asked.

Do we know if this question is frequently asked in interviews, or
is it just a question than turns up in Google hits?

I expect the dol... and the hedge... are in agreement in their
opinions on this matter.

--
Frequently A Hedgehog
"No-one here is exactly what he appears." G'kar, /Babylon 5/

Chris Dollin, Dec 8, 2007
18. ### James FangGuest

On Dec 7, 1:33 pm, wrote:
> Hi all,
>
> The following question is asked frequently in interviews
>
> How to find the greatest of 2 numbers without using relational
> operators ?
>
> the solution i have seen is
>
> ( a+b + abs(a-b) ) /2 ;
>
> is there any better solution than this ....?????

In your solution there's an overflow issue.

Actually there's a simpler solution: you can use an array, and use the
array index istead of the relational operators.

int max(int a,int b)
{
int array[2];
array[0]=a;
array[1]=b;
return array[(a-b)&0x80000000];
}

also, you can make use of the C system stack to get rid of extra
memory space:

int max(int a,int b)
{
// in C standard, the function parameters are pushed from right to
left.
// so integer b is stored in high address.

return array *(&a+((a-b)&0x80000000>>31));
}

James Fang, Dec 8, 2007
19. ### James FangGuest

On Dec 8, 12:20 pm, James Fang <> wrote:
> On Dec 7, 1:33 pm, wrote:
>
> > Hi all,

>
> > The following question is asked frequently in interviews

>
> > How to find the greatest of 2 numbers without using relational
> > operators ?

>
> > the solution i have seen is

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

>
> > is there any better solution than this ....?????

>
> In your solution there's an overflow issue.
>
> Actually there's a simpler solution: you can use an array, and use the
> array index istead of the relational operators.
>
> int max(int a,int b)
> {
> int array[2];
> array[0]=a;
> array[1]=b;
> return array[(a-b)&0x80000000];
>
> }
>
> also, you can make use of the C system stack to get rid of extra
> memory space:
>
> int max(int a,int b)
> {
> // in C standard, the function parameters are pushed from right to
> left.
> // so integer b is stored in high address.
>
> return array *(&a+((a-b)&0x80000000>>31));
>
> }

Sorry, I've made a mistake, the second implementation should be:

int max(int a,int b)
{
// in C standard, the function parameters are pushed from right to
left.
// so integer b is stored in high address.
return *(&a+((a-b)&0x80000000>>31));
}

Thanks and Regards,
James Fang

James Fang, Dec 8, 2007
20. ### Flash GordonGuest

James Fang wrote, On 08/12/07 04:23:
> On Dec 8, 12:20 pm, James Fang <> wrote:
>> On Dec 7, 1:33 pm, wrote:
>>
>>> Hi all,
>>> The following question is asked frequently in interviews
>>> How to find the greatest of 2 numbers without using relational
>>> operators ?
>>> the solution i have seen is
>>> ( a+b + abs(a-b) ) /2 ;
>>> is there any better solution than this ....?????

>> In your solution there's an overflow issue.
>>
>> Actually there's a simpler solution: you can use an array, and use the
>> array index istead of the relational operators.
>>
>> int max(int a,int b)
>> {
>> int array[2];
>> array[0]=a;
>> array[1]=b;
>> return array[(a-b)&0x80000000];
>>
>> }

Did you actually test this piece of rubbish? When I try it I always get
the value of a. I'm really not sure how it is giving me that since the
code is so broken. Just to show you how bad I've added a bit of
diagnostic and here it is...

markg@brenda:~\$ cat t.c
#include<stdio.h>

int max(int a,int b)
{
int array[2];
array[0]=a;
array[1]=b;
printf("%d\n",(a-b)&0x80000000);
return array[(a-b)&0x80000000];
}

int main(void)
{
printf("%d\n",max(1,2));
return 0;
}
markg@brenda:~\$ gcc -ansi -Wall -Wextra -O t.c
markg@brenda:~\$ ./a.out
-2147483648
1
markg@brenda:~\$

Obviously the index is just a little outside the array.

>> also, you can make use of the C system stack

C does not have a system stack. Your implementation might, but equally
well it might not work as you expect.

>> to get rid of extra
>> memory space:
>>
>> int max(int a,int b)
>> {
>> // in C standard, the function parameters are pushed from right to
>> left.

Or they are passed in registers (if you take the address then obviously
it has to allocate a memory location), or the stack might not grow in
the direction you expect, or the parameters might be pushed left to right...

>> // so integer b is stored in high address.
>>
>> return array *(&a+((a-b)&0x80000000>>31));

int might not be 32 bits. It invokes undefined behaviour if you take a
pointer to a, add 1 to it, and dereference it.

>>
>> }

>
> Sorry, I've made a mistake, the second implementation should be:
>
> int max(int a,int b)
> {
> // in C standard, the function parameters are pushed from right to
> left.
> // so integer b is stored in high address.
> return *(&a+((a-b)&0x80000000>>31));
> }

No, the second implementation should be erased not corrected, and anyone
who thinks it is valid needs to learn C. The first could be corrected as
an intellectual exercise, but should never be used in real life.
--
Flash Gordon

Flash Gordon, Dec 8, 2007