@JohnRennie Hi

do u know how to swap two numbers using bit operations

Hi :-)

Do you mean you have two variables x and y and you have to swap them without using a third variable?

yes

without third variable

I have read this but I cannot remember exactly how it's done so I'd have to Google it. It's done using some complicated sequence of ANDs and ORs.

I can try and Google it if you want ...

yea i didnt really get it

javatpoint.com/…

heres the steps

do u know why they work

Ah yes, I remember.

The way to understand this is to consider a single bit. The numbers are made up from a sequence of bits, and swapping the numbers means swapping the bits.

So if we understand how the swap works for a single bit then that explains how it works for numbers made up from many bits.

OK so far?

ok

So suppose we have two bits A and B and we have to swap them. There are only four possibilities:

A  B
0  0
0  1
1  0
1  1

Yes?

yes

Suppose we start with the first possibility A = 0 and B = 0 then we get:

          A  B
Start     0  0
A = A^B   0  0
B = A^B   0  0
A = A^B   0  0

Yes?

Because 0 xor 0 = 0

yes

So we get the same result as swapping the bits, though since both are zero swapping didn't actually do anything.

So now let's take A = 1 and B = 1

          A  B
Start     1  1
A = A^B   0  1
B = A^B   0  1
A = A^B   1  1

Do you want to go through each operation and check I did it correctly?

whats the table in the right

The table on the right shows the results of the logical operation.

We start with A = 1 and B = 1

ok

Then at the first row we do A = A^B = 1^1 = 0 so we get A = 0 and B is unchanged at B = 1.

Yes?

yes

At the second row we do B = A^B = 0^1 = 1. So we get B = 1 and A is unchanged at A = 0.

yes

Then at the third row we do A = A^B again, so A = 0^1 = 1 and B is unchanged at B = 1.

So we end up with A = 1 and B =1.

And again A and b were swapped but since both are equal to 1 it makes no difference.

yes

So the sequence of three XORs does swap the bits if they are both 0 or both 1.

Does this make sense so far?

Yes

Do you want to try it for yourself with A = 0 and B = 1?

          A  B
Start     0  1
A = A^B
B = A^B
A = A^B

Ok

Let me try it real quick

Yes it swapped it

Is there a generalization on why this works

It's because the XOR is its own inverse.

If you do A^B^A the A^A always gives zero and we end up with just B i.e. A^B^A = B

@Aladdin Yes?

Ahh ok

And the B^B cancels to give just B = A

This makes sense

Yes?

Yes

got it

This was very clever method

It's one of those sneaky tricks that no-one would ever actually use in real life :-)