By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,291 Members | 3,096 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,291 IT Pros & Developers. It's quick & easy.

greatest of two numbers

P: n/a
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 '07 #1
Share this Question
Share on Google+
35 Replies


P: n/a
aa*****@gmail.com 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
Dec 7 '07 #2

P: n/a
On Fri, 07 Dec 2007 07:46:04 +0000, Richard Heathfield
<rj*@see.sig.invalidwrote:
>aa*****@gmail.com 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
Dec 7 '07 #3

P: n/a
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!
Dec 7 '07 #4

P: n/a
aa*****@gmail.com 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.
Dec 7 '07 #5

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

SRY

Dec 7 '07 #6

P: n/a
On 12月7日, 下午3时46分, Richard Heathfield <r...@see.sig.invalidwrote:
aark...@gmail.com 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
Dec 7 '07 #7

P: n/a
aa*****@gmail.com 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.
Dec 7 '07 #8

P: n/a
On Dec 7, 6:33 am, aark...@gmail.com 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 '07 #9

P: n/a
On 2007-12-07, aa*****@gmail.com <aa*****@gmail.comwrote:
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
Dec 7 '07 #10

P: n/a
aa*****@gmail.com 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

Dec 7 '07 #11

P: n/a
On Dec 7, 10:59 am, Chris Dollin <chris.dol...@hp.comwrote:
aark...@gmail.com wrote:
The following question is asked frequently in interviews

How do we know this?

just google "C interview Questions"
Dec 7 '07 #12

P: n/a
On Dec 6, 9:33 pm, aark...@gmail.com 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.
Dec 7 '07 #13

P: n/a
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
Dec 7 '07 #14

P: n/a
aa*****@gmail.com wrote:
On Dec 7, 10:59 am, Chris Dollin <chris.dol...@hp.comwrote:
>aark...@gmail.com 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/

Dec 8 '07 #15

P: n/a
user923005 wrote:
aark...@gmail.com 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>
Try the download section.

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

Dec 8 '07 #16

P: n/a
[comp.lang.c] Chris Dollin <ch**********@hp.comwrote:
aa*****@gmail.com 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.
Dec 8 '07 #17

P: n/a
On Dec 7, 1:33 pm, aark...@gmail.com 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));
}

Dec 8 '07 #18

P: n/a
On Dec 8, 12:20 pm, James Fang <fangshang...@gmail.comwrote:
On Dec 7, 1:33 pm, aark...@gmail.com 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
Dec 8 '07 #19

P: n/a
James Fang wrote, On 08/12/07 04:23:
On Dec 8, 12:20 pm, James Fang <fangshang...@gmail.comwrote:
>On Dec 7, 1:33 pm, aark...@gmail.com 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
Dec 8 '07 #20

P: n/a
James Fang <fa**********@gmail.comwrites:
On Dec 7, 1:33 pm, aark...@gmail.com wrote:
>How to find the greatest of 2 numbers without using relational
operators ?
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];
}
Broken, but it does suggest a better way and does show why these
questions are so daft. Ruling out relational operators rules out a
reasonable branch-less solution (in C99 using compound literals):

((int [2]){a, b})[b a]

--
Ben.
Dec 8 '07 #21

P: n/a
On 12月8日, 下午7时22分, Flash Gordon <s...@flash-gordon.me.ukwrote:
James Fang wrote, On 08/12/07 04:23:
On Dec 8, 12:20 pm, James Fang <fangshang...@gmail.comwrote:
On Dec 7, 1:33 pm, aark...@gmail.com 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
Actually, I just missed one shift operation in the max function
because the code was written in a hurry in the bbs reply, attached
below is the corrected function int max(int,int).

My code is directly written in the bbs reply, the purpose of my code
is to illustrate new idea and algorithm, rather than help sb directly
do copy&paste job. The entire execution code is pasted below, it was
compiled with gcc and had basic functionality test on win32 system.
#include <stdio.h>

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

int main()
{
printf("%d\n",max(-1,100));
printf("%d\n",max(10000,100));
printf("%d\n",max(99,99));
getchar();
}
Dec 8 '07 #22

P: n/a
On Dec 8, 9:35 am, James Fang <fangshang...@gmail.comwrote:
Thanks for your correction...

int get_max(int a,int b)
{
int array[2];
array[0]=a;
array[1]=b;
return array[( (a-b)& (UINT_MAX/2+1U) ) >>
((sizeof(int)*8)-1)];}

int main()
{
printf("%d\n",get_max(-190,-100));
printf("%d\n",get_max(10000,100));
printf("%d\n",get_max(99,199));

}
Still wrong. With your code,
printf("%d
\n",get_max(2147483647,-1));
will print -1 as the answer.

Your entire attempt is stupid, and the OP's requirement
is stupid. Your whole attempt is pointless,
and encourages stupid programming.

Dec 8 '07 #23

P: n/a
On 12月8日, 下午10时46分, ptkmar...@gmail.com wrote:
On Dec 8, 9:35 am, James Fang <fangshang...@gmail.comwrote:
Thanks for your correction...
int get_max(int a,int b)
{
int array[2];
array[0]=a;
array[1]=b;
return array[( (a-b)& (UINT_MAX/2+1U) ) >>
((sizeof(int)*8)-1)];}
int main()
{
printf("%d\n",get_max(-190,-100));
printf("%d\n",get_max(10000,100));
printf("%d\n",get_max(99,199));
}

Still wrong. With your code,
printf("%d
\n",get_max(2147483647,-1));
will print -1 as the answer.

Your entire attempt is stupid, and the OP's requirement
is stupid. Your whole attempt is pointless,
and encourages stupid programming.
You are right, I omitted the overflow condition in the code, and it
can be workarounded as follow:
int get_max(int a,int b)
{
long long divisor = (long long)a-(long long)b;
int array[2];
array[0]=a;
array[1]=b;
return array[( divisor & (ULLONG_MAX/2+1U) ) >((sizeof(long
long)*8)-1)];
}

As far as I am concerned, this question is rather an excersice than
what will be used in the real engineering environment. It forces the
coder to implement an "if(a<b){....}" expression with high level
programming language C rather than the compiler generated assembly.
In the assembly we can get the value of the status-register, which
will help us know the overflow in the last caculation. but with pure C
it is hard to get this valuable information(if I am wrong please
correct me).So it's impossible to implement a perfect "if(a<b){...}"
without knowing the processor details. And it's impossible for a
program caring the processor details be portable!

If we see the question as an excersice for "if(a<b){....}" and an
interesting puzzle, it is worthwhile to have a try and have some fun.

The "if(a>b){return a;}..." like impl is surely not stupid for the
real-world engineering, but it is surely not a clever answer for a
puzzle, right?

Anyway, I am with this answer just because that I am with this sounds-
interesting-question, not means that I support this kind of coding
standard in the project. I take your point that in engineering
practice, simply is the best.

BTW, is there any perfect solution to implement the "if(a<b){....}"
without any Relational Operator?
Dec 8 '07 #24

P: n/a
On 12月8日, 下午10时46分, ptkmar...@gmail.com wrote:
On Dec 8, 9:35 am, James Fang <fangshang...@gmail.comwrote:
Thanks for your correction...
int get_max(int a,int b)
{
int array[2];
array[0]=a;
array[1]=b;
return array[( (a-b)& (UINT_MAX/2+1U) ) >>
((sizeof(int)*8)-1)];}
int main()
{
printf("%d\n",get_max(-190,-100));
printf("%d\n",get_max(10000,100));
printf("%d\n",get_max(99,199));
}

Still wrong. With your code,
printf("%d
\n",get_max(2147483647,-1));
will print -1 as the answer.

Your entire attempt is stupid, and the OP's requirement
is stupid. Your whole attempt is pointless,
and encourages stupid programming.
You are right, I omitted the overflow condition in the code, and it
can be workarounded as follow:
int get_max(int a,int b)
{
long long divisor = (long long)a-(long long)b;
int array[2];
array[0]=a;
array[1]=b;
return array[( divisor & (ULLONG_MAX/2+1U) ) >((sizeof(long
long)*8)-1)];
}

As far as I am concerned, this question is rather an excersice than
what will be used in the real engineering environment. It forces the
coder to implement an "if(a<b){....}" expression with high level
programming language C rather than the compiler generated assembly.
In the assembly we can get the value of the status-register, which
will help us know the overflow in the last caculation. but with pure C
it is hard to get this valuable information(if I am wrong please
correct me).So it's impossible to implement a perfect "if(a<b){...}"
without knowing the processor details. And it's impossible for a
program caring the processor details be portable!

If we see the question as an excersice for "if(a<b){....}" and an
interesting puzzle, it is worthwhile to have a try and have some fun.

The "if(a>b){return a;}..." like impl is surely not stupid for the
real-world engineering, but it is surely not a clever answer for a
puzzle, right?

Anyway, I am with this answer just because that I am with this sounds-
interesting-question, not means that I support this kind of coding
standard in the project. I take your point that in engineering
practice, simply is the best.

BTW, is there any perfect solution to implement the "if(a<b){....}"
without any Relational Operator?
Dec 8 '07 #25

P: n/a
On 12月8日, 下午10时46分, ptkmar...@gmail.com wrote:
On Dec 8, 9:35 am, James Fang <fangshang...@gmail.comwrote:
Thanks for your correction...
int get_max(int a,int b)
{
int array[2];
array[0]=a;
array[1]=b;
return array[( (a-b)& (UINT_MAX/2+1U) ) >>
((sizeof(int)*8)-1)];}
int main()
{
printf("%d\n",get_max(-190,-100));
printf("%d\n",get_max(10000,100));
printf("%d\n",get_max(99,199));
}

Still wrong. With your code,
printf("%d
\n",get_max(2147483647,-1));
will print -1 as the answer.

Your entire attempt is stupid, and the OP's requirement
is stupid. Your whole attempt is pointless,
and encourages stupid programming.
Just omitted the overflow condition in the code, and it can be
workarounded as follow:
int get_max(int a,int b)
{
long long divisor = (long long)a-(long long)b;
int array[2];
array[0]=a;
array[1]=b;
return array[( divisor & (ULLONG_MAX/2+1U) ) >((sizeof(long
long)*8)-1)];
}

As far as I am concerned, this question is rather an excersice than
what will be used in the real engineering environment. It forces the
coder to implement an "if(a<b){....}" expression with high level
programming language C rather than the compiler generated assembly.
In the assembly we can get the value of the status-register, which
will help us know the overflow in the last caculation. but with pure C
it is hard to get this valuable information(if I am wrong please
correct me).So it's impossible to implement a perfect "if(a<b){...}"
without knowing the processor details. And it's impossible for a
program caring the processor details be portable!

If we see the question as an excersice for "if(a<b){....}" and an
interesting puzzle, it is worthwhile to have a try and have some fun.

The "if(a>b){return a;}..." like impl is surely not stupid for the
real-world engineering, but it is surely not a clever answer for a
puzzle, right?

Anyway, I am with this answer just because that I am with this sounds-
interesting-question, not means that I support this kind of coding
standard in the project. I take your point that in engineering
practice, simply is the best.

BTW, is there any perfect solution to implement the "if(a<b){....}"
without any Relational Operator?
Dec 8 '07 #26

P: n/a
James Fang wrote:
>
.... snip ...
>
My code is directly written in the bbs reply, the purpose of my code
is to illustrate new idea and algorithm, rather than help sb directly
do copy&paste job. The entire execution code is pasted below, it was
compiled with gcc and had basic functionality test on win32 system.

#include <stdio.h>

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

int main() {
printf("%d\n",max(-1,100));
printf("%d\n",max(10000,100));
printf("%d\n",max(99,99));
getchar();
}
And how does it work on sign magnitude systems, or 16 bit integer
systems, or any non-32 bit integer systems, etc.? What is the
useless 'getchar' for? Are there prizes for deleting blanks?

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

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

Dec 8 '07 #27

P: n/a
On 12月8日, 下午11时17分, CBFalconer <cbfalco...@yahoo.comwrote:
James Fang wrote:

... snip ...
My code is directly written in the bbs reply, the purpose of my code
is to illustrate new idea and algorithm, rather than help sb directly
do copy&paste job. The entire execution code is pasted below, it was
compiled with gcc and had basic functionality test on win32 system.
#include <stdio.h>
int max(int a,int b) {
int array[2];
array[0]=a;
array[1]=b;
return array[((a-b)&0x80000000)>>31];
}
int main() {
printf("%d\n",max(-1,100));
printf("%d\n",max(10000,100));
printf("%d\n",max(99,99));
getchar();
}

And how does it work on sign magnitude systems, or 16 bit integer
systems, or any non-32 bit integer systems, etc.? What is the
useless 'getchar' for? Are there prizes for deleting blanks?

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

--
Posted via a free Usenet account fromhttp://www.teranews.com
hi Chuck,
the getchar() is only used to facilitate test in windows command
prompt(as I don't want the command prompt window disapear after
process exits)

This code is absolutely un-portable due to the limitation of the
question itself. It need to be re-considered for each type of
processor(maybe use a macro to control them).

Dec 8 '07 #28

P: n/a
James Fang wrote, On 08/12/07 13:33:
On 12月8日, 下午7时22分, Flash Gordon <s...@flash-gordon.me.ukwrote:
>James Fang wrote, On 08/12/07 04:23:
>>On Dec 8, 12:20 pm, James Fang <fangshang...@gmail.comwrote:
On Dec 7, 1:33 pm, aark...@gmail.com 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

Actually, I just missed one shift operation in the max function
because the code was written in a hurry in the bbs reply, attached
below is the corrected function int max(int,int).
No, you have several other errors. With assume int is 32 bits as I
already stated, your code will invoke undefined behaviour due to
overflow with some values. It may well have other problems, your second
example certainly does.
My code is directly written in the bbs reply, the purpose of my code
I have no idea what you mean by bbs.
is to illustrate new idea and algorithm, rather than help sb directly
do copy&paste job. The entire execution code is pasted below, it was
compiled with gcc and had basic functionality test on win32 system.
Specific implementations are not relevant.
#include <stdio.h>

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

int main()
{
printf("%d\n",max(-1,100));
printf("%d\n",max(10000,100));
printf("%d\n",max(99,99));
#include <limits.h>
printf("%d\n",max(INT_MIN,INT_MAX);

I get the value of INT_MIN printed which is just a little incorrect.
getchar();
}
Basically the only sensible answer is that it is a stupid question.
--
Flash Gordon
Dec 8 '07 #29

P: n/a
James Fang wrote:
....
BTW, since "!=" is also in the Relational Operator Set which is also
disatisfied with the question requirement, a better way may be like
No, the C standard restricts the term "relational operator" to '<', '>',
'<=' and '>=' (6.5.8). '!=' is an equality operator, a category that
also includes '==' (6.5.9).
Dec 8 '07 #30

P: n/a
"Flash Gordon" <sp**@flash-gordon.me.ukschrieb im Newsbeitrag
news:03************@news.flash-gordon.me.uk...
James Fang wrote, On 08/12/07 13:33:
>My code is directly written in the bbs reply, the purpose of my code
I have no idea what you mean by bbs.
I presume he means "Bulletin Board System", in the (wrong) assumption that
Usenet is just that.

Bye, Jojo
Dec 8 '07 #31

P: n/a
On 12月9日, 上午12时24分, Flash Gordon <s...@flash-gordon.me.ukwrote:
James Fang wrote, On 08/12/07 13:33:
On 12月8日, 下午7时22分, Flash Gordon <s...@flash-gordon.me.ukwrote:
James Fang wrote, On 08/12/07 04:23:
>On Dec 8, 12:20 pm, James Fang <fangshang...@gmail.comwrote:
On Dec 7, 1:33 pm, aark...@gmail.com 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
Actually, I just missed one shift operation in the max function
because the code was written in a hurry in the bbs reply, attached
below is the corrected function int max(int,int).

No, you have several other errors. With assume int is 32 bits as I
already stated, your code will invoke undefined behaviour due to
overflow with some values. It may well have other problems, your second
example certainly does.
My code is directly written in the bbs reply, the purpose of my code

I have no idea what you mean by bbs.
is to illustrate new idea and algorithm, rather than help sb directly
do copy&paste job. The entire execution code is pasted below, it was
compiled with gcc and had basic functionality test on win32 system.

Specific implementations are not relevant.
#include <stdio.h>
int max(int a,int b)
{
int array[2];
array[0]=a;
array[1]=b;
return array[((a-b)&0x80000000)>>31];
}
int main()
{
printf("%d\n",max(-1,100));
printf("%d\n",max(10000,100));
printf("%d\n",max(99,99));

#include <limits.h>
printf("%d\n",max(INT_MIN,INT_MAX);

I get the value of INT_MIN printed which is just a little incorrect.
getchar();
}

Basically the only sensible answer is that it is a stupid question.
--
Flash Gordon
You are right, detection of arithmetical overflow with portable
solution should be a problem.
The following code can handle the arithmetical overflow, but it still
assumes that the sign bit is the high bit, which might be non-portable
on some CPUs.
In fact,these processor specific differences should be concealed by
the C compiler,right?

int get_max(int a,int b)
{
long long divisor = (long long)a-(long long)b;
int array[2];
array[0]=a;
array[1]=b;
return array[( divisor & (ULLONG_MAX/2+1U) ) >((sizeof(long
long)*8)-1)];
}
Thanks and Regards,
James
Dec 9 '07 #32

P: n/a
James Fang <fangshang...@gmail.comwrote:
ptkmar...@gmail.com wrote:
...
Your entire attempt is stupid, and the OP's requirement
is stupid. Your whole attempt is pointless,
and encourages stupid programming.
Depends how you look at it. The irony is that you need to
be reasonably skilled to actually get this done portably.
Of course, it's highly unlikely that people asking the
question in an interview are actually in a position to
grade the attempts.
You are right, I omitted the overflow condition in the
code, and it can be workarounded as follow:
int get_max(int a,int b)
{
long long divisor = (long long)a-(long long)b;
What if the range of int is the same as long long?
int array[2];
array[0]=a;
array[1]=b;
return array[( divisor & (ULLONG_MAX/2+1U) ) >((sizeof(long
long)*8)-1)];

}
The version at...

<http://groups.google.com/group/comp.lang.c/msg/5aeee18e55ea156c>

Should be maximally portable, though it's obviously not
maximally readable. :-)

--
Peter
Dec 10 '07 #33

P: n/a
On Dec 7, 7:52 am, "std...@gmail.com" <std...@gmail.comwrote:
On Dec 7, 6:33 am, aark...@gmail.com 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;}
what about this solution

http://cpuzz.blogspot.com/2005/07/ma...elational.html
Dec 17 '07 #34

P: n/a
On Dec 17, 2:18 pm, aark...@gmail.com wrote:
How to find the greatest of 2 numbers without using relational
operators ?

what about this solution

http://cpuzz.blogspot.com/2005/07/ma...thout-relation
I've not been following this discussion, but ...

when a has no side-effects (and is unaffected by
evaluating b), and the net expression's value
is discarded or treated as a boolean,
and missing parentheses are not an issue, then
(a && b || !a && c)
is equivalent to
a ? b : c

I don't know if C's "?" is considered a "relational
operator" but if so, to say that the first expression
above "avoids the relational operator" in the second
seems quite frivolous.

James
Dec 17 '07 #35

P: n/a
>On Dec 6, 9:33 pm, aark...@gmail.com wrote:
>The question [of branchless min and max] is asked frequently
in interviews ...
In article <e7**********************************@a35g2000prf. googlegroups.com>
user923005 <dc*****@connx.comwrote:
>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/
[snippage]
>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.
Indeed. However, questions like that might make sense in interviews
for compiler-writing positions. :-)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Dec 29 '07 #36

This discussion thread is closed

Replies have been disabled for this discussion.