Velocity Reviews > greatest of two numbers

# greatest of two numbers

Chris Dollin
Guest
Posts: n/a

 12-07-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) 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

aarklon@gmail.com
Guest
Posts: n/a

 12-07-2007
On Dec 7, 10:59 am, Chris Dollin <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > The following question is asked frequently in interviews

>
> How do we know this?
>
>

user923005
Guest
Posts: n/a

 12-07-2007
On Dec 6, 9:33 pm, (E-Mail Removed) 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.

Willem
Guest
Posts: n/a

 12-07-2007
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
Guest
Posts: n/a

 12-07-2007
[comp.lang.c] Chris Dollin <(E-Mail Removed)> wrote:
> (E-Mail Removed) 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.

CBFalconer
Guest
Posts: n/a

 12-08-2007
user923005 wrote:
> (E-Mail Removed) 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

Chris Dollin
Guest
Posts: n/a

 12-08-2007
(E-Mail Removed) wrote:

> On Dec 7, 10:59 am, Chris Dollin <(E-Mail Removed)> wrote:
>> (E-Mail Removed) 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

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/

James Fang
Guest
Posts: n/a

 12-08-2007
On Dec 7, 1:33 pm, (E-Mail Removed) 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
Guest
Posts: n/a

 12-08-2007
On Dec 8, 12:20 pm, James Fang <(E-Mail Removed)> wrote:
> On Dec 7, 1:33 pm, (E-Mail Removed) 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

Flash Gordon
Guest
Posts: n/a

 12-08-2007
James Fang wrote, On 08/12/07 04:23:
> On Dec 8, 12:20 pm, James Fang <(E-Mail Removed)> wrote:
>> On Dec 7, 1:33 pm, (E-Mail Removed) 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