Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #26608 > unrolled thread

Swapping logic

Back to article view | Back to comp.lang.c

Contents

  Swapping logic ZUBAIR TRALI <bhat.zubair789@gmail.com> - 2012-09-23 05:48 -0700
    Re: Swapping logic Richard Damon <news.x.richarddamon@xoxy.net> - 2012-09-23 09:04 -0400
    Re: Swapping logic Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-09-23 09:15 -0400
      Re: Swapping logic Noob <root@127.0.0.1> - 2012-09-24 12:56 +0200
    Re: Swapping logic Casey Carter <Casey_at_Carter_dot_net@dontspam.me.invalid> - 2012-09-23 11:35 -0500
      Re: Swapping logic Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-09-23 14:19 -0400
        Re: Swapping logic Nobody <nobody@nowhere.com> - 2012-09-24 10:57 +0100
        Re: Swapping logic Andrew Smallshaw <andrews@sdf.lonestar.org> - 2012-09-26 05:20 +0000
          Re: Swapping logic Gareth Owen <gwowen@gmail.com> - 2012-09-26 06:46 +0100
            Re: Swapping logic David Brown <david@westcontrol.removethisbit.com> - 2012-09-26 08:16 +0200
              Re: Swapping logic Gareth Owen <gwowen@gmail.com> - 2012-09-26 17:51 +0100
    Re: Swapping logic Kaz Kylheku <kaz@kylheku.com> - 2012-09-23 18:19 +0000

#26608 — Swapping logic

#include<stdio.h>
/*new logic for swapping*/
#include<conio.h>
void main()
 {
   int x=20,y=30;
printf("nos before swapping are %d and %d\n",x,y);
    x=x*y/(y=x);
printf("nos after swapping are %d and %d\n",x,y);
getch();
}

[toc] | [next] | [standalone]

#26609

On 9/23/12 8:48 AM, ZUBAIR TRALI wrote:
> #include<stdio.h>
> /*new logic for swapping*/
> #include<conio.h>
> void main()
>  {
>    int x=20,y=30;
> printf("nos before swapping are %d and %d\n",x,y);
>     x=x*y/(y=x);
> printf("nos after swapping are %d and %d\n",x,y);
> getch();
> }
> 

This invokes undefined behavior, as you set the value of y, and also use
the value of y (for a purpose other than getting the value to set y to).
The language does not promise that the sub expression x*y will be
executed before the sub expression y=x.

Also, x*y needs to fit withing the range of an int, so it will only work
for "small" numbers, and it fails if y == 0 (as 0/0 again invokes
undefined behavior).

[toc] | [prev] | [next] | [standalone]

#26611

On 9/23/2012 8:48 AM, ZUBAIR TRALI wrote:
> #include<stdio.h>
> /*new logic for swapping*/
> #include<conio.h>
> void main()
>   {
>     int x=20,y=30;
> printf("nos before swapping are %d and %d\n",x,y);
>      x=x*y/(y=x);
> printf("nos after swapping are %d and %d\n",x,y);
> getch();
> }

     Wonderful![*]  Splendid![*]  You're a genius![*]

     Unfortunately, my stupid computer misbehaves when I use
your brilliant technique with x=0.  It even misbehaves when
both x and y are 50000 to start with (which ought to be
trivial to "swap").  Also, my compiler complains

	foo.c:6: warning: operation on 'y' may be undefined

What am I[*] doing wrong?

     [*] <http://dictionary.reference.com/browse/irony>

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#26647

Eric Sosman wrote:

> Wonderful![*]  Splendid![*]  You're a genius![*]

YHBT.

[toc] | [prev] | [next] | [standalone]

#26612

On 2012-09-23 07:48, ZUBAIR TRALI wrote:
> #include<stdio.h>
> /*new logic for swapping*/
> #include<conio.h>
> void main()
>   {
>     int x=20,y=30;
> printf("nos before swapping are %d and %d\n",x,y);
>      x=x*y/(y=x);
> printf("nos after swapping are %d and %d\n",x,y);
> getch();
> }
>
I think you're looking for:
x ^= y;
y ^= x;
x ^= y;

[toc] | [prev] | [next] | [standalone]

#26618

On 9/23/2012 12:35 PM, Casey Carter wrote:
> On 2012-09-23 07:48, ZUBAIR TRALI wrote:
>> #include<stdio.h>
>> /*new logic for swapping*/
>> #include<conio.h>
>> void main()
>>   {
>>     int x=20,y=30;
>> printf("nos before swapping are %d and %d\n",x,y);
>>      x=x*y/(y=x);
>> printf("nos after swapping are %d and %d\n",x,y);
>> getch();
>> }
>>
> I think you're looking for:
> x ^= y;
> y ^= x;
> x ^= y;

     Don't do this.  See Question 20.15c on the comp.lang.c
Frequently Asked Questions (FAQ) page, <http://www.c-faq.com/>.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#26645

On Sun, 23 Sep 2012 14:19:51 -0400, Eric Sosman wrote:

>> I think you're looking for:
>> x ^= y;
>> y ^= x;
>> x ^= y;
> 
>      Don't do this.  See Question 20.15c on the comp.lang.c
> Frequently Asked Questions (FAQ) page, <http://www.c-faq.com/>.

And especially don't do this (or equivalent):

	*p ^= *q;
	*q ^= *p;
	*p ^= *q;

as it's equivalent to *p=0 if p==q.

[toc] | [prev] | [next] | [standalone]

#26705

On 2012-09-23, Eric Sosman <esosman@ieee-dot-org.invalid> wrote:

>> I think you're looking for:
>> x ^= y;
>> y ^= x;
>> x ^= y;
>
>      Don't do this.  See Question 20.15c on the comp.lang.c
> Frequently Asked Questions (FAQ) page, <http://www.c-faq.com/>.

Which is of course complete nonsense.  It's the kind of thing that
happens when somone's _opinion_ that is implictly based on one
specific use case gets treated as undisputable and universal fact.
The smallest system I've ever used C on had 53 bytes of RAM.  You
try making the argument that the correct solution is _always_ a
temporary variable in that kind of environment.

-- 
Andrew Smallshaw
andrews@sdf.lonestar.org

[toc] | [prev] | [next] | [standalone]

#26707

Andrew Smallshaw <andrews@sdf.lonestar.org> writes:

> Which is of course complete nonsense.  It's the kind of thing that
> happens when somone's _opinion_ that is implictly based on one
> specific use case gets treated as undisputable and universal fact.
> The smallest system I've ever used C on had 53 bytes of RAM.  You try
> making the argument that the correct solution is _always_ a temporary
> variable in that kind of environment.

The argument isn't that the temporary is the best (object code)
solution, the argument is that a "good enough" compiler will optimise
the C-code-with-temporary into optimal object code.

The problem is that the "good enough compiler", like the "True
Scotsman", is frequently a mythical beast.

[toc] | [prev] | [next] | [standalone]

#26708

On 26/09/2012 07:46, Gareth Owen wrote:
 > Andrew Smallshaw <andrews@sdf.lonestar.org> writes:
 >
 >> Which is of course complete nonsense.  It's the kind of thing that
 >> happens when somone's _opinion_ that is implictly based on one
 >> specific use case gets treated as undisputable and universal fact.
 >> The smallest system I've ever used C on had 53 bytes of RAM.  You try
 >> making the argument that the correct solution is _always_ a temporary
 >> variable in that kind of environment.

I've worked on a system without any ram at all, baring the 32 8-bit 
registers.  I used gcc.  It was special kind of fun.

 >
 > The argument isn't that the temporary is the best (object code)
 > solution, the argument is that a "good enough" compiler will optimise
 > the C-code-with-temporary into optimal object code.

When you have particular specialised needs, you have to work very 
closely with the compiler - playing with command line switches and code 
layout, and analysing the exact generated assembly code.  For small 
embedded systems, or very time-critical code, many rules no longer apply 
(even if they are _always_ valid).

But for general programming - as done by the majority of programmers for 
the majority of the time - rules like this apply.  The compiler /will/ 
generate better code than the smart-ass programmer copying swap tricks 
from the web.  This is because the compiler does a better job when it 
has more information, more "natural" code, and more "recognizable" code. 
  A common case here is that compilers will generally generate better 
code with arrays rather than when a programmer has "optimised" it into 
pointer code.

Of course, this assumes that the programmer knows how to use the 
compiler, and doesn't cripple it by not enabling optimisations...

So the FAQ is appropriate here - and programmers who really know better 
will break those rules if necessary.

 >
 > The problem is that the "good enough compiler", like the "True
 > Scotsman", is frequently a mythical beast.
 >

A /true/ Scotsman never reveals whether or not he is a "true" Scotsman - 
it's the mystery that makes us irresistible to the opposite sex.

Hopefully that does not apply to compilers...

[toc] | [prev] | [next] | [standalone]

#26713

David Brown <david@westcontrol.removethisbit.com> writes:

> When you have particular specialised needs, you have to work very
> closely with the compiler - playing with command line switches and
> code layout, and analysing the exact generated assembly code.  For
> small embedded systems, or very time-critical code, many rules no
> longer apply

Right.  I agree completely. When Eric said "Don't do this", he
implicitly meant "Don't do this unless you really, really know why you".

Writing fancy-dan XOR exchange routines without first proving they're
necessary is classic premature optimisation, and we all know what
premature optimisation is.

> But for general programming - as done by the majority of programmers
> for the majority of the time - rules like this apply.  

Right. I agree completely. 

<RANT type=OT>

(And I speak as someone who's spent the day
trying to squeeze individual clock cycles out of an ARM7 routine because
the proprietary compiler does not optimise well -- the kind of day when
you're profiling branch probabilities to determine which branch is the
hot path, but have no way to communicate this to the compiler, which has
decided that no matter what you it's going to guess wrong :( ).  

I  freaking hate *compiler name elided*
</RANT>

[toc] | [prev] | [next] | [standalone]

#26617

On 2012-09-23, ZUBAIR TRALI <bhat.zubair789@gmail.com> wrote:
> #include<stdio.h>
> /*new logic for swapping*/
> #include<conio.h>
> void main()
>  {
>    int x=20,y=30;
> printf("nos before swapping are %d and %d\n",x,y);
>     x=x*y/(y=x);

The problem here is that you're accessing y in an expression where y is
modified.  That is undefined behavior.

More precisely, your accessing y for a purpose other than determining a new
value to be stored into y. 

The following also accesses y in an expression where it is modified:

  y = y + 1;

However, the access in "y + 1" is a necessary operand for computing the value
stored in the assignment. This imposes an order, which makes it well defined.

This one is not defined:

  y + (y = 3);

The y on the left of the + is accessed, but that access is not necessary for
the y = 3 assignment on the right. Because it is not necessary, it does not
have to be ordered relative to the assignment, and so we do not know when that
access occurs: before, during or after the completion of assignment to y?

If you write such ambiguous expressions in your C programs, they will be
nonportable between compilers and possibly unreliable even on one compiler.
For instance, if you change some code-generation options such as optimization
settings, the behavior might change.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web