Re: Sort 3 numbers in a single line.

Discussion in 'C++' started by Hasan Ammar, Sep 16, 2004.

  1. Hasan  Ammar

    Hasan Ammar Guest

    This was a Puzzle question presented to us to determine if it could be
    done in a single return statement. The sorting should be done in such a
    way that your return value becomes (a < b) < c hence the result is a
    boolean value.
     
    Hasan Ammar, Sep 16, 2004
    #1
    1. Advertising

  2. Hasan  Ammar

    chris Guest

    Hasan Ammar wrote:

    > This was a Puzzle question presented to us to determine if it could be
    > done in a single return statement. The sorting should be done in such a
    > way that your return value becomes (a < b) < c hence the result is a
    > boolean value.
    >


    I'm still not positive what you mean. However I can tell you in theory
    you can do anything at all in one return statement :)

    The following are your friends:

    the ?: operator, often used normally.

    the , operator: not used that often normally, it acts most like a
    semi-colon, but only the last part of it is returned:

    Remember with a && b, the b part is only run if a was true, and for a ||
    b, b is only run if a is false.

    To start you off, here is a little example:

    #include <stdio.h>
    int swap(int &a,int &b,int &c){
    return (
    ((a>b)&&(a+=b,b-=a,b=-b,a-=b)),((b>c)&&(b+=c,c-=b,c=-c,b-=c)),((a>b)&&(a+=b,b-=a,b=-b,a-=b)));
    }

    int main(void) {
    int a=3,b=2,c=1;
    swap(a,b,c);
    printf("%d,%d,%d",a,b,c);
    }

    This program actually ignores the return value of swap, and pass a,b and
    c by reference. It gives you the idea of what to do tho.

    Note that (a+=b,b-=a,b=-b,a-=b) is one way of swapping the values of a
    and b (not a very good way actually, as it breaks if the sum overflows
    somewhere in the middle, but to be honest this whole idea is quite stupid).

    As you can probably guess, using , && and || it is actually possible to
    write entire programs which don't appear to actually have any "normal"
    instructions in them. Writing one or two is quite fun, although you
    shouldn't show such code to other people, except to confuse them.

    Chris
     
    chris, Sep 16, 2004
    #2
    1. Advertising

  3. Hasan  Ammar

    steve Guest

    Hi,

    Just a note, since you are being given puzzle's I assume that you are
    learning to code ( University I guess ). Enjoy the puzzle and the
    interesting new functionality that it introduces you to ( i.e. ? : , ^ ).

    BUT..

    Doing stuff like this has got very VERY little to do with developing
    software, and more to do with developing egos.
    It would be a very bad habit to get into if you started to look for way to
    "shorten" code. "Short" code is not fast code.
    The code below while it may work is nothing short of poor code ( as Chris
    suggested "...shouldn't show such code to other people" )

    -Steve

    "chris" <> wrote in message
    news:cic74n$bjl$...
    > Hasan Ammar wrote:
    >
    > > This was a Puzzle question presented to us to determine if it could be
    > > done in a single return statement. The sorting should be done in such a
    > > way that your return value becomes (a < b) < c hence the result is a
    > > boolean value.
    > >

    >
    > I'm still not positive what you mean. However I can tell you in theory
    > you can do anything at all in one return statement :)
    >
    > The following are your friends:
    >
    > the ?: operator, often used normally.
    >
    > the , operator: not used that often normally, it acts most like a
    > semi-colon, but only the last part of it is returned:
    >
    > Remember with a && b, the b part is only run if a was true, and for a ||
    > b, b is only run if a is false.
    >
    > To start you off, here is a little example:
    >
    > #include <stdio.h>
    > int swap(int &a,int &b,int &c){
    > return (
    >

    ((a>b)&&(a+=b,b-=a,b=-b,a-=b)),((b>c)&&(b+=c,c-=b,c=-c,b-=c)),((a>b)&&(a+=b,
    b-=a,b=-b,a-=b)));
    > }
    >
    > int main(void) {
    > int a=3,b=2,c=1;
    > swap(a,b,c);
    > printf("%d,%d,%d",a,b,c);
    > }
    >
    > This program actually ignores the return value of swap, and pass a,b and
    > c by reference. It gives you the idea of what to do tho.
    >
    > Note that (a+=b,b-=a,b=-b,a-=b) is one way of swapping the values of a
    > and b (not a very good way actually, as it breaks if the sum overflows
    > somewhere in the middle, but to be honest this whole idea is quite

    stupid).
    >
    > As you can probably guess, using , && and || it is actually possible to
    > write entire programs which don't appear to actually have any "normal"
    > instructions in them. Writing one or two is quite fun, although you
    > shouldn't show such code to other people, except to confuse them.
    >
    > Chris
     
    steve, Sep 16, 2004
    #3
  4. Hasan  Ammar

    chris Guest

    steve wrote:

    > Hi,
    >
    > Just a note, since you are being given puzzle's I assume that you are
    > learning to code ( University I guess ). Enjoy the puzzle and the
    > interesting new functionality that it introduces you to ( i.e. ? : , ^ ).
    >
    > BUT..
    >
    > Doing stuff like this has got very VERY little to do with developing
    > software, and more to do with developing egos.
    > It would be a very bad habit to get into if you started to look for way to
    > "shorten" code. "Short" code is not fast code.
    > The code below while it may work is nothing short of poor code ( as Chris
    > suggested "...shouldn't show such code to other people" )
    >


    Yes, I should probably have said this steve :) thanks!

    One of the most important things is that in c++, if you want to swap two
    integers a and b, then {int temp=a; a=b; b=temp;} is the FASTEST way of
    doing it. It's faster than stupid XORing tricks. It's faster than stupid
    addition / subtraction tricks. Worry about the algorithms and let your
    comppiler worry about bit-twiddling (OK there are exceptions like there
    are to everything, but in general) :)
     
    chris, Sep 16, 2004
    #4
  5. Hasan  Ammar

    Method Man Guest

    "Hasan Ammar" <> wrote in message
    news:cic5vj$...
    > This was a Puzzle question presented to us to determine if it could be
    > done in a single return statement. The sorting should be done in such a
    > way that your return value becomes (a < b) < c hence the result is a
    > boolean value.
    >


    You're still not making the problem clear. Do you want the function to
    return true if a < b < c ? If so:

    bool sort(int a, int b, int c) {
    return ((a < b) ? (b < c) : 0);
    }

    Or do you want the single statement to perform a sort? In which case, why
    would your function return a 'bool'?
     
    Method Man, Sep 16, 2004
    #5
  6. Hasan  Ammar

    Method Man Guest

    - snip -

    > Note that (a+=b,b-=a,b=-b,a-=b) is one way of swapping the values of a
    > and b (not a very good way actually, as it breaks if the sum overflows
    > somewhere in the middle, but to be honest this whole idea is quite

    stupid).

    Since we're trying to shorten code, why not implement that swap in 3
    statements instead of 4?

    a = a + b;
    b = a - b;
    a = a - b;
     
    Method Man, Sep 16, 2004
    #6
  7. Method Man wrote:
    >
    > - snip -
    >
    > > Note that (a+=b,b-=a,b=-b,a-=b) is one way of swapping the values of a
    > > and b (not a very good way actually, as it breaks if the sum overflows
    > > somewhere in the middle, but to be honest this whole idea is quite

    > stupid).
    >
    > Since we're trying to shorten code, why not implement that swap in 3
    > statements instead of 4?
    >
    > a = a + b;
    > b = a - b;
    > a = a - b;


    Because it is still a bad way of swapping :)

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Sep 17, 2004
    #7
  8. Hasan  Ammar

    JKop Guest


    > Note that (a+=b,b-=a,b=-b,a-=b) is one way of swapping the values of a
    > and b (not a very good way actually, as it breaks if the sum overflows
    > somewhere in the middle, but to be honest this whole idea is quite
    > stupid).


    BULLSHIT

    Try this on an 8-Bit char system, like Windows.

    The range of unsigned char will be 0 to 255.


    unsigned char a = 250;
    unsigned char b = 100;


    The swap will still work. Why? Here's a clue: defined over-flow.


    -JKop
     
    JKop, Sep 17, 2004
    #8
  9. JKop wrote:
    >
    > > Note that (a+=b,b-=a,b=-b,a-=b) is one way of swapping the values of a
    > > and b (not a very good way actually, as it breaks if the sum overflows
    > > somewhere in the middle, but to be honest this whole idea is quite
    > > stupid).

    >
    > BULLSHIT
    >
    > Try this on an 8-Bit char system, like Windows.
    >
    > The range of unsigned char will be 0 to 255.
    >
    > unsigned char a = 250;
    > unsigned char b = 100;
    >
    > The swap will still work. Why? Here's a clue: defined over-flow.
    >


    Now try the same with double values.
    Good luck.

    Note: When talking about a swap function, most programmers
    think about a function (or as in C++: a tamplate) that works
    with each and every data type. Granted, there are special cases where
    all those swap_hacks work, but in practice this is completely
    unimportant, since the 3 assignment sequence paired with a temporary
    works well enough in 99.999999% of all cases.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Sep 17, 2004
    #9
  10. Hasan  Ammar

    Andre Heinen Guest

    On Fri, 17 Sep 2004 12:13:49 GMT, JKop <> wrote:

    >BULLSHIT
    >
    >Try this on an 8-Bit char system, like Windows.
    >
    >The range of unsigned char will be 0 to 255.
    >
    >unsigned char a = 250;
    >unsigned char b = 100;
    >
    >The swap will still work. Why? Here's a clue: defined over-flow.


    The example Chris gave uses int's. In signed arithmetic,
    overflow is undefined behaviour.

    --
    Andre Heinen
    My address, rot13-encoded: n qbg urvara ng rhebcrnayvax qbg pbz
     
    Andre Heinen, Sep 17, 2004
    #10
  11. Hasan  Ammar

    JKop Guest

    Karl Heinz Buchegger posted:

    > JKop wrote:
    >>
    >> > Note that (a+=b,b-=a,b=-b,a-=b) is one way of swapping

    the values of a
    >> > and b (not a very good way actually, as it breaks if

    the sum overflows
    >> > somewhere in the middle, but to be honest this whole

    idea is quite
    >> > stupid).

    >>
    >> BULLSHIT
    >>
    >> Try this on an 8-Bit char system, like Windows.
    >>
    >> The range of unsigned char will be 0 to 255.
    >>
    >> unsigned char a = 250;
    >> unsigned char b = 100;
    >>
    >> The swap will still work. Why? Here's a clue: defined

    over-flow.
    >>

    >
    > Now try the same with double values.
    > Good luck.
    >
    > Note: When talking about a swap function, most

    programmers
    > think about a function (or as in C++: a tamplate) that

    works
    > with each and every data type. Granted, there are special

    cases where
    > all those swap_hacks work, but in practice this is

    completely
    > unimportant, since the 3 assignment sequence paired with

    a temporary
    > works well enough in 99.999999% of all cases.
    >


    Karl and Andre, I'm off to write some code. Back in a few
    mins...

    -JKop
     
    JKop, Sep 17, 2004
    #11
  12. Hasan  Ammar

    JKop Guest

    > Karl Heinz Buchegger posted:

    >> Now try the same with double values.
    >> Good luck.


    void SwapMemory(void* const p_x, void* const p_y, unsigned amount_bytes);

    int main()
    {
    double* const p_blah = new double[500];
    double* const p_blue = new double[500];

    SwapMemory(p_blah,p_blue,sizeof(double) * 500);

    delete [] p_blah;
    delete [] p_blue;
    }

    void SwapMemory(void* const p_x, void* const p_y, unsigned amount_bytes)
    {
    unsigned int i;
    unsigned int amount_units_to_be_swapped;

    {
    amount_units_to_be_swapped = amount_bytes / sizeof(unsigned);

    if ( amount_units_to_be_swapped )
    {
    unsigned int * const &x = reinterpret_cast<unsigned int* const&>
    (p_x);
    unsigned int * const &y = reinterpret_cast<unsigned int* const&>
    (p_y);

    for (i = 0; i < amount_units_to_be_swapped; ++i)
    {
    x = y ^ x;
    y = x ^ y;
    x = y ^ x;
    }
    }
    }


    {
    //still contains previous value
    i = amount_units_to_be_swapped * sizeof(unsigned);
    //don't decrement

    amount_units_to_be_swapped = amount_bytes % sizeof(unsigned);

    if (amount_units_to_be_swapped)
    {
    unsigned char * const &x = reinterpret_cast<unsigned char*
    const&>(p_x);
    unsigned char * const &y = reinterpret_cast<unsigned char*
    const&>(p_y);

    do
    {
    x = y ^ x;
    y = x ^ y;
    x = y ^ x;
    } while ( ++i < amount_units_to_be_swapped );
    }
    }

    }


    Machines work with int's more efficiently, that's why I use them first in
    the above, then moving on to bytes.

    -JKop
     
    JKop, Sep 17, 2004
    #12
  13. Hasan  Ammar

    JKop Guest

    That code was a little half-baked, I haven't checked the
    array indexes.


    -JKop
     
    JKop, Sep 17, 2004
    #13
  14. JKop wrote:
    >
    > > Karl Heinz Buchegger posted:

    >
    > >> Now try the same with double values.
    > >> Good luck.

    >
    > void SwapMemory(void* const p_x, void* const p_y, unsigned amount_bytes);
    >
    > int main()
    > {
    > double* const p_blah = new double[500];
    > double* const p_blue = new double[500];
    >
    > SwapMemory(p_blah,p_blue,sizeof(double) * 500);
    >
    > delete [] p_blah;
    > delete [] p_blue;
    > }
    >
    > void SwapMemory(void* const p_x, void* const p_y, unsigned amount_bytes)
    > {
    > unsigned int i;
    > unsigned int amount_units_to_be_swapped;
    >
    > {
    > amount_units_to_be_swapped = amount_bytes / sizeof(unsigned);
    >
    > if ( amount_units_to_be_swapped )
    > {
    > unsigned int * const &x = reinterpret_cast<unsigned int* const&>
    > (p_x);
    > unsigned int * const &y = reinterpret_cast<unsigned int* const&>
    > (p_y);
    >
    > for (i = 0; i < amount_units_to_be_swapped; ++i)
    > {
    > x = y ^ x;
    > y = x ^ y;
    > x = y ^ x;


    Not so fast.
    Your comment was aimed at the reply which used the
    'arithmetic swap hack':

    (a+=b,b-=a,b=-b,a-=b)

    And that's the one to which I replied:
    'Try with double. Good Luck'


    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Sep 17, 2004
    #14
  15. Hasan  Ammar

    JKop Guest

    > Your comment was aimed at the reply which used the
    > 'arithmetic swap hack':


    It's no hack, integer overflow is defined.

    > (a+=b,b-=a,b=-b,a-=b)
    >
    > And that's the one to which I replied:
    > 'Try with double. Good Luck'


    Ultimately, I used that method, albeit not on a double
    itself (or 500 :p )

    -JKop
     
    JKop, Sep 17, 2004
    #15
  16. Karl Heinz Buchegger wrote:
    >
    > JKop wrote:
    > >
    > > > Karl Heinz Buchegger posted:

    > >
    > > >> Now try the same with double values.
    > > >> Good luck.

    > >
    > > void SwapMemory(void* const p_x, void* const p_y, unsigned amount_bytes);
    > >
    > > int main()
    > > {
    > > double* const p_blah = new double[500];
    > > double* const p_blue = new double[500];
    > >
    > > SwapMemory(p_blah,p_blue,sizeof(double) * 500);
    > >
    > > delete [] p_blah;
    > > delete [] p_blue;
    > > }
    > >
    > > void SwapMemory(void* const p_x, void* const p_y, unsigned amount_bytes)
    > > {
    > > unsigned int i;
    > > unsigned int amount_units_to_be_swapped;
    > >
    > > {
    > > amount_units_to_be_swapped = amount_bytes / sizeof(unsigned);
    > >
    > > if ( amount_units_to_be_swapped )
    > > {
    > > unsigned int * const &x = reinterpret_cast<unsigned int* const&>
    > > (p_x);
    > > unsigned int * const &y = reinterpret_cast<unsigned int* const&>
    > > (p_y);
    > >
    > > for (i = 0; i < amount_units_to_be_swapped; ++i)
    > > {
    > > x = y ^ x;
    > > y = x ^ y;
    > > x = y ^ x;

    >
    > Not so fast.
    > Your comment was aimed at the reply which used the
    > 'arithmetic swap hack':
    >
    > (a+=b,b-=a,b=-b,a-=b)
    >
    > And that's the one to which I replied:
    > 'Try with double. Good Luck'
    >


    To continue:
    To this one, I comment: Fine. Now try calling it with:

    SwapMemory(p_blah,p_blah,sizeof(double) * 500);



    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Sep 17, 2004
    #16
  17. Hasan  Ammar

    JKop Guest

    JKop posted:

    >> Your comment was aimed at the reply which used the

    'arithmetic swap
    >> hack':

    >
    > It's no hack, integer overflow is defined.
    >
    >> (a+=b,b-=a,b=-b,a-=b)
    >>
    >> And that's the one to which I replied:
    >> 'Try with double. Good Luck'

    >
    > Ultimately, I used that method, albeit not on a double
    > itself (or 500 :p )
    >
    > -JKop


    Okay, I'll rephrase:

    x = y ^ x;
    y = x ^ y;
    x = y ^ x;

    to:

    x += y;
    y -= x;
    y = -y;
    x -= y;



    -JKop
     
    JKop, Sep 17, 2004
    #17
  18. Hasan  Ammar

    Guest

    Karl Heinz Buchegger posted:

    > Karl Heinz Buchegger wrote:
    >>
    >> JKop wrote:
    >> >
    >> > > Karl Heinz Buchegger posted:
    >> >
    >> > >> Now try the same with double values.
    >> > >> Good luck.
    >> >
    >> > void SwapMemory(void* const p_x, void* const p_y,

    unsigned
    >> > amount_bytes);
    >> >
    >> > int main()
    >> > {
    >> > double* const p_blah = new double[500];
    >> > double* const p_blue = new double[500];
    >> >
    >> > SwapMemory(p_blah,p_blue,sizeof(double) * 500);
    >> >
    >> > delete [] p_blah;
    >> > delete [] p_blue; }
    >> >
    >> > void SwapMemory(void* const p_x, void* const p_y,

    unsigned
    >> > amount_bytes) {
    >> > unsigned int i;
    >> > unsigned int amount_units_to_be_swapped;
    >> >
    >> > {
    >> > amount_units_to_be_swapped = amount_bytes /
    >> > sizeof(unsigned);
    >> >
    >> > if ( amount_units_to_be_swapped )
    >> > {
    >> > unsigned int * const &x = reinterpret_cast

    <unsigned int*
    >> > const&> (p_x); unsigned int * const &y =
    >> > reinterpret_cast<unsigned int* const&>

    (p_y);
    >> >
    >> > for (i = 0; i <

    amount_units_to_be_swapped; ++i)
    >> > {
    >> > x = y ^ x;
    >> > y = x ^ y; x = y ^ x

    ;
    >>
    >> Not so fast.
    >> Your comment was aimed at the reply which used the
    >> 'arithmetic swap hack':
    >>
    >> (a+=b,b-=a,b=-b,a-=b)
    >>
    >> And that's the one to which I replied:
    >> 'Try with double. Good Luck'
    >>

    >
    > To continue:
    > To this one, I comment: Fine. Now try calling it with:
    >
    > SwapMemory(p_blah,p_blah,sizeof(double) * 500);
    >
    >
    >


    Ha ha! I got my foot in the door before you, I said it was
    half-baked before you posted that!

    -JKop
     
    , Sep 17, 2004
    #18
  19. JKop wrote:
    >
    > > Your comment was aimed at the reply which used the
    > > 'arithmetic swap hack':

    >
    > It's no hack,


    I use 'hack' in the pristine meaning: A clever invention which
    is not obvious to everybody and looks like magic to those who
    don't know how it works.

    > integer overflow is defined.


    unsigned int - yes
    signed int - no

    Your program uses unsigned. That's fine, but ...

    >
    > > (a+=b,b-=a,b=-b,a-=b)
    > >
    > > And that's the one to which I replied:
    > > 'Try with double. Good Luck'

    >
    > Ultimately, I used that method, albeit not on a double
    > itself (or 500 :p )
    >


    How come?

    To quote your program:

    x = y ^ x;
    y = x ^ y;
    x = y ^ x;

    That's the 'XOR hack'. I don't see some addition
    or subtraction with that.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Sep 17, 2004
    #19
  20. JKop wrote:
    >
    > JKop posted:
    >
    > >> Your comment was aimed at the reply which used the

    > 'arithmetic swap
    > >> hack':

    > >
    > > It's no hack, integer overflow is defined.
    > >
    > >> (a+=b,b-=a,b=-b,a-=b)
    > >>
    > >> And that's the one to which I replied:
    > >> 'Try with double. Good Luck'

    > >
    > > Ultimately, I used that method, albeit not on a double
    > > itself (or 500 :p )
    > >
    > > -JKop

    >
    > Okay, I'll rephrase:
    >
    > x = y ^ x;
    > y = x ^ y;
    > x = y ^ x;
    >
    > to:
    >
    > x += y;
    > y -= x;
    > y = -y;
    > x -= y;
    >


    Oh. I see now what you are getting at. You used to 'cast'
    the double to unsigned int for swapping purposes only. Since
    you know that the result is really just a byte swap, you end
    up with the 'bytes' reversed. Since you used unsigned (I guess
    right now), I think you can be sure that there are no trap values
    in the byte representations for doubles. Clever. But: The
    above uses 4 operations. Have you timed that this is faster then

    tmp = x;
    x = y;
    y[i] = tmp;

    which uses only 3 operations and has the advantage that actually more
    bytes are swapped at each repetition since sizeof(double) > sizeof(unsigned int)
    on most machines ?

    --
    Karl Heinz Buchegger
    [email][/email][/i]
     
    Karl Heinz Buchegger, Sep 17, 2004
    #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. Hugo
    Replies:
    10
    Views:
    1,325
    Matt Humphrey
    Oct 18, 2004
  2. Hasan  Ammar

    Sort 3 numbers in a single line.

    Hasan Ammar, Sep 16, 2004, in forum: C++
    Replies:
    9
    Views:
    461
    Ioannis Vranos
    Sep 17, 2004
  3. Navin
    Replies:
    1
    Views:
    705
    Ken Schaefer
    Sep 9, 2003
  4. GIMME
    Replies:
    5
    Views:
    188
    Thomas 'PointedEars' Lahn
    Jul 26, 2004
  5. ela
    Replies:
    12
    Views:
    351
    Uri Guttman
    Apr 6, 2009
Loading...

Share This Page