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
    #1
    1. Advertising

  2. 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
    Richard Heathfield, Dec 7, 2007
    #2
    1. Advertising

  3. jaysome Guest

    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
    #3
  4. Klutz_wd Guest


    > 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
    #4
  5. 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
    #5
  6. 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
    #6
  7. 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
    #7
  8. James Kuyper Guest

    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
    #8
  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
    #9
  10. Neil Cerutti Guest

    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
    #10
  11. Chris Dollin Guest

    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
    #11
  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
    #12
  13. user923005 Guest

    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
    #13
  14. Willem Guest

    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
    #14
  15. [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
    #15
  16. CBFalconer Guest

    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>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Dec 8, 2007
    #16
  17. Chris Dollin Guest

    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
    #17
  18. James Fang Guest

    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
    #18
  19. James Fang Guest

    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
    #19
  20. Flash Gordon Guest

    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
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    12
    Views:
    540
    Jonathan Turkanis
    Dec 13, 2004
  2. Frederick Gotham

    Greatest number divisible by Y

    Frederick Gotham, Jul 1, 2006, in forum: C Programming
    Replies:
    21
    Views:
    820
    Dave Thompson
    Jul 10, 2006
  3. puzzlecracker
    Replies:
    8
    Views:
    310
    werasm
    May 11, 2006
  4. tomek milewski

    stl map - the lowest and greatest key

    tomek milewski, Feb 20, 2007, in forum: C++
    Replies:
    4
    Views:
    1,092
    Chris Theis
    Feb 21, 2007
  5. Amar Kumar Dubedy

    Greatest of three numbers

    Amar Kumar Dubedy, Jul 1, 2007, in forum: C Programming
    Replies:
    30
    Views:
    1,288
    Peter Nilsson
    Jul 4, 2007
Loading...

Share This Page