greatest of two numbers

[aarklon]

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 ....?????

 

[Richard Heathfield]

(e-mail address removed) 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."

 

[jaysome]

(e-mail address removed) said:


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


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

 

[Klutz_wd]

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!

 

[Marco Manfredini]

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]

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

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

SRY

 

[Thomas X. Iverson]

(e-mail address removed) said:




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




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

 

[James Kuyper]

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.

 

[stdazi]

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;}

 

[Neil Cerutti]

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?

 

[Chris Dollin]

The following question is asked frequently in interviews

How do we know this?

 

[aarklon]

How do we know this?

just google "C interview Questions"

 

[user923005]

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.

 

[Willem]

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

 

[Christopher Benson-Manica]

(e-mail address removed) wrote:

The following question is asked frequently in interviews

How do we know this?

It certainly seems to be asked frequently by instructors.

 

[CBFalconer]

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;
}

 

[Chris Dollin]

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.

 

[James Fang]

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]

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

 

[Flash Gordon]

James Fang wrote, On 08/12/07 04:23:

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.

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

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...

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.