# Re: Sort 3 numbers in a single line.

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

1. ### Hasan AmmarGuest

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

2. ### chrisGuest

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

3. ### steveGuest

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
4. ### chrisGuest

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
comppiler worry about bit-twiddling (OK there are exceptions like there
are to everything, but in general)

chris, Sep 16, 2004
5. ### Method ManGuest

"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
6. ### Method ManGuest

- 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

a = a + b;
b = a - b;
a = a - b;

Method Man, Sep 16, 2004
7. ### Karl Heinz BucheggerGuest

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
>
> 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
8. ### JKopGuest

> 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
9. ### Karl Heinz BucheggerGuest

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
10. ### Andre HeinenGuest

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
11. ### JKopGuest

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
12. ### JKopGuest

> 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
13. ### JKopGuest

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

-JKop

JKop, Sep 17, 2004
14. ### Karl Heinz BucheggerGuest

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.
'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
15. ### JKopGuest

> '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 )

-JKop

JKop, Sep 17, 2004
16. ### Karl Heinz BucheggerGuest

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.
> '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
17. ### JKopGuest

JKop posted:

'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 )
>
> -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
18. ### 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.
>> '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
19. ### Karl Heinz BucheggerGuest

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

How come?

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
20. ### Karl Heinz BucheggerGuest

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