0

I read many answers on SO explaining the code using bitwise XOR operator to solve the above problem but none of them seems to explain how to come up with that code.

For example, the following solution uses arithmetic to solve the same problem and I can intuitively think this one.

// C++ Program to swap two numbers without
// using temporary variable
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int x = 10, y = 5;

    // Code to swap 'x' and 'y'
    x = x + y; // x now becomes 15
    y = x - y; // y becomes 10
    x = x - y; // x becomes 5
    cout << "After Swapping: x =" << x << ", y=" << y;
}

Output

After Swapping: x =5, y=10

& The following is the code for solving above problem using XOR

// C++ code to swap using XOR
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int x = 10, y = 5;
    // Code to swap 'x' (1010) and 'y' (0101)
    x = x ^ y; // x now becomes 15 (1111)
    y = x ^ y; // y becomes 10 (1010)
    x = x ^ y; // x becomes 5 (0101)
    cout << "After Swapping: x =" << x << ", y=" << y;
    return 0;
}

Output:

 After Swapping: x =5, y=10

I understand what the above code is doing line by line, but how do I come up with this logic? I had spent hours on this problem in trying to figure out a way to solve it using XOR but couldn't really get it.

shubham singh
  • 11
  • 1
  • 2
    There's no pattern for how solutions present themselves other than deep knowledge of whatever is being done, an ability to think outside the box, and experimentation. – Dave Newton Apr 27 '22 at 15:51
  • 2
    I recommend you get out of the habit of using [`using namespace std;`](https://stackoverflow.com/q/1452721/10077) and [`#include `](https://stackoverflow.com/q/31816095/10077). They're bad individually, but especially insidious together. – Fred Larson Apr 27 '22 at 15:52
  • Given that you know what the code is doing, it may be difficult to answer the question _"How do I come up with this?"_ Are you asking - in general - how to invent algorithms? Are you asking what thoughts lead to discovering this solution? – Drew Dormann Apr 27 '22 at 15:52
  • 1
    It’s not intuition, it’s logic. Instead of looking at it from a decimal number, look at it from the standpoint of what you are doing to the individual bits. It is, after-all, a bit-wise operation. – Taekahn Apr 27 '22 at 15:53
  • *but none of them seems to explain how to come up with that code* -- And most problems will never explain how the solution was "thought up". Maybe trial and error? Maybe the person took a nap or went into deep thought and meditation, and dreamed up the solution? (and yes, this has happened). – PaulMcKenzie Apr 27 '22 at 15:53
  • @Dave Newton So how should I solve a problem which requires me to use a bitwise XOR operator to solve it efficiently if I don't know that I can use it in the first place? What do you suggest? – shubham singh Apr 27 '22 at 15:55
  • 2
    Bitwise swap is dangerous. Try swapping `x` with itself. This is a gimmick; nobody should use it in serious code. – Pete Becker Apr 27 '22 at 15:55
  • @shubhamsingh *if I don't know that I can use it in the first place* -- Everything we do now in C++, and computer programming in general. came from experience because "we didn't know how to do something in the first place". This is no different. – PaulMcKenzie Apr 27 '22 at 15:57
  • @shubhamsingh that’s the neat part, you don’t have to. The day of programmers having to know stuff like this isn’t really true anymore. Unless you specifically want to specialize in low level logic, in which case you have a long road ahead. But I’d start with fundamental understanding of how computers work. – Taekahn Apr 27 '22 at 15:57
  • 2
    To be clear - if you want to swap two values, use [`std::swap`](https://en.cppreference.com/w/cpp/algorithm/swap). This problem does **not** "require bitwise XOR to solve it efficiently". – Drew Dormann Apr 27 '22 at 15:58
  • @shubhamsingh a problem requiring you to use XOR has nothing to do with XOR swap, they're just normal bitwise operators. [XOR swap is terrible](https://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice) and no one uses it in real life code – phuclv Apr 27 '22 at 15:58
  • 1
    @shubhamsingh The XOR swap "trick" may have been popular back in the 70's and 80's, but that really is no longer necessary, given the advancement of optimizing compilers and CPU's. The days of trying to beat the compiler at the optimization game are basically long gone. – PaulMcKenzie Apr 27 '22 at 16:03
  • @shubhamsingh I have no suggestions :) There's only experience and knowledge: the more one knows the more they can bring that knowledge to bear on whatever problem is in front of them. – Dave Newton Apr 27 '22 at 16:18
  • The gag here is you can perform the swap without a third variable. Back in the old days before we could throw kilobyes of RAM at a problem sometimes you needed to do operations like this. but today we can often throw gigabyes of RAM at even the most trivial problems. – user4581301 Apr 27 '22 at 16:26
  • @DrewDormann _Are you asking what thoughts lead to discovering this solution?_ Yes – shubham singh Apr 28 '22 at 06:44
  • I guess now I have a better understanding of my question. Thank you so much guys for taking in the effort to give me the right direction and the general suggestions! You are awesome <3 – shubham singh Apr 28 '22 at 06:48

0 Answers0