-3

1.

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

2.

b=a+b-(a=b);

These two snippets swap values of 'a' and 'b' without a temporary third variable. Please ignore the completed nature of the second statement. Is the second statement optimal than the first one? How? Can we say the second one is optimal because it has fewer statements?

Akash Kamble
  • 5
  • 4
  • 2
    First one is better because I can more or less understand it right away. – dckuehn Sep 19 '16 at 15:02
  • 2
    Risk of overflow, I suggest a simple swap as is still only three operations and safe. – Weather Vane Sep 19 '16 at 15:03
  • 3
    We can say that it is a dumb, dangerous, possibly inefficient and needlessly complicated way of doing `tmp=a; a=b; b=tmp;`. – Lundin Sep 19 '16 at 15:05
  • 1
    Is there a case where avoiding to use a temporary variable for a value swapping has a real advantage? I'm curious because I saw this kind of question a few times here – Thomas W. Sep 19 '16 at 15:05
  • @ThomasWilmotte when there is simply no room for a temporary, for example I worked on early PICs which had a very limited number of "files", no user stack and no RAM.. – Weather Vane Sep 19 '16 at 15:07
  • @WeatherVane But in that case it might better worth working in a lower level language than C – Thomas W. Sep 19 '16 at 15:08
  • There was a "tiny C" available. – Weather Vane Sep 19 '16 at 15:09
  • 2
    C is a compiled language, and current compilers are good at optimization. The number of C statements in definitely not a good indicator of low level performance. Benchmark it if you want to know what a specific compiler under a specific configuration uses best, of use in line assembly language if you want to control the low level translation. – Serge Ballesta Sep 19 '16 at 15:10

3 Answers3

6

Neither approach is universal, because you risk numeric overflow on a+b. Since C standard considers integer overflow undefined behavior, both snippets are equally bad, and unacceptable in production code.

The best way to do it is also the most readable one:

int tmp=a;
a=b;
b=tmp;

Readers of your code will see what is going on right away, which is enough of a goal in itself. As an additional bonus, however, most compiler will see what you are doing, too, and optimize tmp variable out of the code by using an exchange instruction on platforms where it is available.

Note: One could argue that the second approach is even worse, because a is used twice in an expression that has a side effect, without a sequence point in between of two uses. This means that the compiler is allowed to compute a=b and store the result into a before computing a+b, even though the assignment is after the addition. The net result of this sequence of operations is the same as a=b even in the absence of integer overflow.

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • No, the second snippet is worse, because it has undefined behavior even in the absence of overflow. That arises from the RHS having a side effect on `a` that is unsequenced with respect to a value computation involving the value of `a`. But yes, neither is acceptable. – John Bollinger Sep 19 '16 at 15:14
2

Both are bad ways to attempt to swap two variables. If a and b are of some unsigned type, the first might work correctly in all cases (I haven't taken the time to confirm that). If they're both of some signed type, the first risks integer overflow, which has undefined behavior. If they're both of floating-point type (nothing in the question indicates that they aren't), the first risks both overflow and loss of precision, and will not handle infinities and NaNs correctly. If they're of complex type -- well, let's just assume they aren't, and that they're both of the same type.

The second has undefined behavior for any type, since it reads and modifies the value of a without an intervening sequence point. In the terms used by the C11 standard, the read and write of a are unsequenced; neither depends on the other, so they can occur in either order. (The result is not limited to the possible orders; the behavior is explicitly completely undefined.)

You're asking (I think) about the run-time efficiency of the two code snippets. The efficiency of incorrect code does not matter.

The way to swap two objects is to use a temporary:

const SOME_TYPE old_a = a;
a = b;
b = old_a;

where SOME_TYPE is the type of a and b. Silly tricks like the one in the question, or the xor trick, are a waste of time.

Keith Thompson
  • 254,901
  • 44
  • 429
  • 631
0

Is the second statement optimal than the first one?

No.

How?

It's not.

Can we say the second one is optimal because it has fewer statements?

No. The C compiler has great freedom when it comes to generating assembly. Either of these statements could be reduced to simpler assembly, or even completely removed, depending on the rest of the code.

You can not make any statements of relative efficiency between these two statements.

QuestionC
  • 10,006
  • 4
  • 26
  • 44
  • 1
    And the efficiency of *incorrect code* doesn't matter. – Keith Thompson Sep 19 '16 at 15:28
  • It's not a question about undefined behavior. Answers about undefined behavior aren't helping anyone. – QuestionC Sep 19 '16 at 15:39
  • I disagree completely. They help by letting the OP, and everyone else, know that the behavior is undefined and the code should not be used. – Keith Thompson Sep 19 '16 at 15:41
  • Rewrite the problem using `XOR` and the code no longer has undefined behavior and should still never be used. UB is just a distraction here. – QuestionC Sep 19 '16 at 15:47
  • The question wasn't about xor. The question asks about code that has undefined behavior. Pointing that out is hardly a distraction; it's absolutely necessary for a meaningful answer. – Keith Thompson Sep 19 '16 at 15:48