Mixing
Logic behind bitwise operators in C
Clash Royale CLAN TAG#URR8PPP
up vote
10
down vote
favorite
I came across bitwise operations in C programming, and I realized that XOR operator can be used to swap 2 numbers in their binary bases. For example let $$i=(65)_10=(1000001)_2, text and j=(120)_10=(1111000)_2$$.
Let $oplus$ be the XOR operator, then observe that if I started with any one of them, say $i$ and following the following procedure:
1)replace its value with the $oplus$ value, yielding $$i=(0111001)_2,j=(1111000)_2$$
2) replace the other variable($j$) with another $oplus$ value derived from the new $i$ and old $j$, yielding $$i=(0111001)_2,j=(1000001)_2$$
3)replace the original variable $i$ with $oplus$ value again, yielding $$i=(1111000)_2,j=(1000001)_2$$
which shows that we would somehow have their values swapped. I found this way of programming online and I definitely can’t understand how people think of the logic aspect of this. I would think it’s linked to the truth table as follows, which shows by division of cases that the values can be swapped.
However, I am still uncertain about the full reasoning why this works, like whether there is any mathematical theorems that I should know that can aid me in my understanding.
PS: Sorry if the question is off-topic here, it feels like a programming question, but I feel that I more concerned about the “logic†rather than the programming. I also drew the table myself on MS word since I can't get the latex one to work somehow.
logic bit-strings
edited 2 days ago
Rodrigo de Azevedo
12.7k41751
asked Sep 2 at 13:30
Prashin Jeevaganth
10410
 |Â
show 1 more comment
up vote
10
down vote
favorite
I came across bitwise operations in C programming, and I realized that XOR operator can be used to swap 2 numbers in their binary bases. For example let $$i=(65)_10=(1000001)_2, text and j=(120)_10=(1111000)_2$$.
Let $oplus$ be the XOR operator, then observe that if I started with any one of them, say $i$ and following the following procedure:
1)replace its value with the $oplus$ value, yielding $$i=(0111001)_2,j=(1111000)_2$$
2) replace the other variable($j$) with another $oplus$ value derived from the new $i$ and old $j$, yielding $$i=(0111001)_2,j=(1000001)_2$$
3)replace the original variable $i$ with $oplus$ value again, yielding $$i=(1111000)_2,j=(1000001)_2$$
which shows that we would somehow have their values swapped. I found this way of programming online and I definitely can’t understand how people think of the logic aspect of this. I would think it’s linked to the truth table as follows, which shows by division of cases that the values can be swapped.
However, I am still uncertain about the full reasoning why this works, like whether there is any mathematical theorems that I should know that can aid me in my understanding.
PS: Sorry if the question is off-topic here, it feels like a programming question, but I feel that I more concerned about the “logic†rather than the programming. I also drew the table myself on MS word since I can't get the latex one to work somehow.
logic bit-strings
edited 2 days ago
Rodrigo de Azevedo
12.7k41751
asked Sep 2 at 13:30
Prashin Jeevaganth
10410
Beware that this doesn't work ifiandjhappen to be the same variable!
– Henning Makholm
Sep 2 at 13:59
@HenningMakholm ah ok noted, applying it 3 times has the same effect as applying 1 time and that will cause one of the values to be full of zeroes
– Prashin Jeevaganth
Sep 2 at 14:03
2
It works for $i = j$ too.
– mbjoe
Sep 2 at 14:11
@mbjoe oh ok just noticed
– Prashin Jeevaganth
Sep 2 at 15:09
9
@mbjoe: It works foriandjhaving the same value, but not for them being the same variable.
– celtschk
Sep 2 at 15:59
 |Â
show 1 more comment
up vote
10
down vote
favorite
up vote
10
down vote
favorite
I came across bitwise operations in C programming, and I realized that XOR operator can be used to swap 2 numbers in their binary bases. For example let $$i=(65)_10=(1000001)_2, text and j=(120)_10=(1111000)_2$$.
Let $oplus$ be the XOR operator, then observe that if I started with any one of them, say $i$ and following the following procedure:
1)replace its value with the $oplus$ value, yielding $$i=(0111001)_2,j=(1111000)_2$$
2) replace the other variable($j$) with another $oplus$ value derived from the new $i$ and old $j$, yielding $$i=(0111001)_2,j=(1000001)_2$$
3)replace the original variable $i$ with $oplus$ value again, yielding $$i=(1111000)_2,j=(1000001)_2$$
which shows that we would somehow have their values swapped. I found this way of programming online and I definitely can’t understand how people think of the logic aspect of this. I would think it’s linked to the truth table as follows, which shows by division of cases that the values can be swapped.
However, I am still uncertain about the full reasoning why this works, like whether there is any mathematical theorems that I should know that can aid me in my understanding.
PS: Sorry if the question is off-topic here, it feels like a programming question, but I feel that I more concerned about the “logic†rather than the programming. I also drew the table myself on MS word since I can't get the latex one to work somehow.
logic bit-strings
edited 2 days ago
Rodrigo de Azevedo
12.7k41751
asked Sep 2 at 13:30
Prashin Jeevaganth
10410
I came across bitwise operations in C programming, and I realized that XOR operator can be used to swap 2 numbers in their binary bases. For example let $$i=(65)_10=(1000001)_2, text and j=(120)_10=(1111000)_2$$.
Let $oplus$ be the XOR operator, then observe that if I started with any one of them, say $i$ and following the following procedure:
1)replace its value with the $oplus$ value, yielding $$i=(0111001)_2,j=(1111000)_2$$
2) replace the other variable($j$) with another $oplus$ value derived from the new $i$ and old $j$, yielding $$i=(0111001)_2,j=(1000001)_2$$
3)replace the original variable $i$ with $oplus$ value again, yielding $$i=(1111000)_2,j=(1000001)_2$$
which shows that we would somehow have their values swapped. I found this way of programming online and I definitely can’t understand how people think of the logic aspect of this. I would think it’s linked to the truth table as follows, which shows by division of cases that the values can be swapped.
However, I am still uncertain about the full reasoning why this works, like whether there is any mathematical theorems that I should know that can aid me in my understanding.
PS: Sorry if the question is off-topic here, it feels like a programming question, but I feel that I more concerned about the “logic†rather than the programming. I also drew the table myself on MS word since I can't get the latex one to work somehow.
logic bit-strings
edited 2 days ago
Rodrigo de Azevedo
12.7k41751
asked Sep 2 at 13:30
Prashin Jeevaganth
10410
edited 2 days ago
Rodrigo de Azevedo
12.7k41751
edited 2 days ago
Rodrigo de Azevedo
12.7k41751
edited 2 days ago
Rodrigo de Azevedo
12.7k41751
12.7k41751
asked Sep 2 at 13:30
Prashin Jeevaganth
10410
asked Sep 2 at 13:30
Prashin Jeevaganth
10410
asked Sep 2 at 13:30
Prashin Jeevaganth
10410
10410
Beware that this doesn't work ifiandjhappen to be the same variable!
– Henning Makholm
Sep 2 at 13:59
@HenningMakholm ah ok noted, applying it 3 times has the same effect as applying 1 time and that will cause one of the values to be full of zeroes
– Prashin Jeevaganth
Sep 2 at 14:03
2
It works for $i = j$ too.
– mbjoe
Sep 2 at 14:11
@mbjoe oh ok just noticed
– Prashin Jeevaganth
Sep 2 at 15:09
9
@mbjoe: It works foriandjhaving the same value, but not for them being the same variable.
– celtschk
Sep 2 at 15:59
 |Â
show 1 more comment
Beware that this doesn't work ifiandjhappen to be the same variable!
– Henning Makholm
Sep 2 at 13:59
@HenningMakholm ah ok noted, applying it 3 times has the same effect as applying 1 time and that will cause one of the values to be full of zeroes
– Prashin Jeevaganth
Sep 2 at 14:03
2
It works for $i = j$ too.
– mbjoe
Sep 2 at 14:11
@mbjoe oh ok just noticed
– Prashin Jeevaganth
Sep 2 at 15:09
9
@mbjoe: It works foriandjhaving the same value, but not for them being the same variable.
– celtschk
Sep 2 at 15:59
Beware that this doesn't work if
i and j happen to be the same variable!– Henning Makholm
Sep 2 at 13:59
Beware that this doesn't work if
i and j happen to be the same variable!– Henning Makholm
Sep 2 at 13:59
@HenningMakholm ah ok noted, applying it 3 times has the same effect as applying 1 time and that will cause one of the values to be full of zeroes
– Prashin Jeevaganth
Sep 2 at 14:03
@HenningMakholm ah ok noted, applying it 3 times has the same effect as applying 1 time and that will cause one of the values to be full of zeroes
– Prashin Jeevaganth
Sep 2 at 14:03
2
2
It works for $i = j$ too.
– mbjoe
Sep 2 at 14:11
It works for $i = j$ too.
– mbjoe
Sep 2 at 14:11
@mbjoe oh ok just noticed
– Prashin Jeevaganth
Sep 2 at 15:09
@mbjoe oh ok just noticed
– Prashin Jeevaganth
Sep 2 at 15:09
9
9
@mbjoe: It works for
i and j having the same value, but not for them being the same variable.– celtschk
Sep 2 at 15:59
@mbjoe: It works for
i and j having the same value, but not for them being the same variable.– celtschk
Sep 2 at 15:59
 |Â
show 1 more comment
3 Answers
3
active
oldest
votes
up vote
9
down vote
accepted
In algebraic terms, the XOR operator (or $oplus$) is nothing other than addition modulo $2$: use $1$ and $0$ for true and false, along with $1 oplus 1 = 0$.
Now, since addition modulo $2$ is associative and commutative, and both elements are their own inverses, we have
$$beginalign
d &= b oplus c\
&= b oplus (a oplus b)\
&= b oplus (b oplus a)\
&= (b oplus b) oplus a\
&= a.\
endalign$$
We can show $e = b$ using similar reasoning.
answered Sep 2 at 13:45
Théophile
17.1k12438
1
I prefer this to the accepted answer, since it mentions associativity and commutativity. Also, while obvious, I imagine the note that XOR is the same as addition modulo 2, might be helpful to readers.
– Demosthenes
Sep 3 at 11:33
add a comment |Â
up vote
16
down vote
Note that you can do the same thing without bitwise operators (at least for unsigned integer types since they can't overflow into undefined behavior):
// i == x j == y
i += j; // i == x+y j == y
j -= i; // i == x+y j == -x
i += j; // i == y j == -x
j = -j; // i == y j == x
Now if we do this bit for bit, but modulo 2 instead of modulo UINT_MAX+1, the XOR operation implements both addition and subtraction, and the final negation is a no-op because $-1equiv 1$ and $-0equiv 0 pmod 2$. So what is left in the bitwise version is exactly
i ^= j; j ^= i; i ^= j;
answered Sep 2 at 14:06
Henning Makholm
230k16296527
1
Thanks for the alternative solution to swap 2 numbers, this is insightful.
– Prashin Jeevaganth
Sep 2 at 14:08
add a comment |Â
up vote
7
down vote
You already answered your question, but if you want an algebraic explanation note that for any $x$:
$$x oplus 0 = x$$
$$x oplus x = 0$$
So:
$$i_0 = i, j_0 = j$$
$$i_1 = i_0 oplus j_0, j_1 = j_0$$
$$i_2 = i_1, j_2 = i_1 oplus j_1 = i_0 oplus j_0 oplus j_0 = i_0$$
$$i_3 = i_2 oplus j_2 = i_1 oplus i_0 = i_0 oplus j_0 oplus i_0 = j_0, j_3 = j_2 = i_0$$
answered Sep 2 at 13:55
mbjoe
15419
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
9
down vote
accepted
In algebraic terms, the XOR operator (or $oplus$) is nothing other than addition modulo $2$: use $1$ and $0$ for true and false, along with $1 oplus 1 = 0$.
Now, since addition modulo $2$ is associative and commutative, and both elements are their own inverses, we have
$$beginalign
d &= b oplus c\
&= b oplus (a oplus b)\
&= b oplus (b oplus a)\
&= (b oplus b) oplus a\
&= a.\
endalign$$
We can show $e = b$ using similar reasoning.
answered Sep 2 at 13:45
Théophile
17.1k12438
1
I prefer this to the accepted answer, since it mentions associativity and commutativity. Also, while obvious, I imagine the note that XOR is the same as addition modulo 2, might be helpful to readers.
– Demosthenes
Sep 3 at 11:33
add a comment |Â
up vote
9
down vote
accepted
In algebraic terms, the XOR operator (or $oplus$) is nothing other than addition modulo $2$: use $1$ and $0$ for true and false, along with $1 oplus 1 = 0$.
Now, since addition modulo $2$ is associative and commutative, and both elements are their own inverses, we have
$$beginalign
d &= b oplus c\
&= b oplus (a oplus b)\
&= b oplus (b oplus a)\
&= (b oplus b) oplus a\
&= a.\
endalign$$
We can show $e = b$ using similar reasoning.
answered Sep 2 at 13:45
Théophile
17.1k12438
1
I prefer this to the accepted answer, since it mentions associativity and commutativity. Also, while obvious, I imagine the note that XOR is the same as addition modulo 2, might be helpful to readers.
– Demosthenes
Sep 3 at 11:33
add a comment |Â
up vote
9
down vote
accepted
up vote
9
down vote
accepted
In algebraic terms, the XOR operator (or $oplus$) is nothing other than addition modulo $2$: use $1$ and $0$ for true and false, along with $1 oplus 1 = 0$.
Now, since addition modulo $2$ is associative and commutative, and both elements are their own inverses, we have
$$beginalign
d &= b oplus c\
&= b oplus (a oplus b)\
&= b oplus (b oplus a)\
&= (b oplus b) oplus a\
&= a.\
endalign$$
We can show $e = b$ using similar reasoning.
answered Sep 2 at 13:45
Théophile
17.1k12438
In algebraic terms, the XOR operator (or $oplus$) is nothing other than addition modulo $2$: use $1$ and $0$ for true and false, along with $1 oplus 1 = 0$.
Now, since addition modulo $2$ is associative and commutative, and both elements are their own inverses, we have
$$beginalign
d &= b oplus c\
&= b oplus (a oplus b)\
&= b oplus (b oplus a)\
&= (b oplus b) oplus a\
&= a.\
endalign$$
We can show $e = b$ using similar reasoning.
answered Sep 2 at 13:45
Théophile
17.1k12438
answered Sep 2 at 13:45
Théophile
17.1k12438
answered Sep 2 at 13:45
Théophile
17.1k12438
answered Sep 2 at 13:45
Théophile
17.1k12438
17.1k12438
1
I prefer this to the accepted answer, since it mentions associativity and commutativity. Also, while obvious, I imagine the note that XOR is the same as addition modulo 2, might be helpful to readers.
– Demosthenes
Sep 3 at 11:33
add a comment |Â
1
I prefer this to the accepted answer, since it mentions associativity and commutativity. Also, while obvious, I imagine the note that XOR is the same as addition modulo 2, might be helpful to readers.
– Demosthenes
Sep 3 at 11:33
1
1
I prefer this to the accepted answer, since it mentions associativity and commutativity. Also, while obvious, I imagine the note that XOR is the same as addition modulo 2, might be helpful to readers.
– Demosthenes
Sep 3 at 11:33
I prefer this to the accepted answer, since it mentions associativity and commutativity. Also, while obvious, I imagine the note that XOR is the same as addition modulo 2, might be helpful to readers.
– Demosthenes
Sep 3 at 11:33
add a comment |Â
up vote
16
down vote
Note that you can do the same thing without bitwise operators (at least for unsigned integer types since they can't overflow into undefined behavior):
// i == x j == y
i += j; // i == x+y j == y
j -= i; // i == x+y j == -x
i += j; // i == y j == -x
j = -j; // i == y j == x
Now if we do this bit for bit, but modulo 2 instead of modulo UINT_MAX+1, the XOR operation implements both addition and subtraction, and the final negation is a no-op because $-1equiv 1$ and $-0equiv 0 pmod 2$. So what is left in the bitwise version is exactly
i ^= j; j ^= i; i ^= j;
answered Sep 2 at 14:06
Henning Makholm
230k16296527
1
Thanks for the alternative solution to swap 2 numbers, this is insightful.
– Prashin Jeevaganth
Sep 2 at 14:08
add a comment |Â
up vote
16
down vote
Note that you can do the same thing without bitwise operators (at least for unsigned integer types since they can't overflow into undefined behavior):
// i == x j == y
i += j; // i == x+y j == y
j -= i; // i == x+y j == -x
i += j; // i == y j == -x
j = -j; // i == y j == x
Now if we do this bit for bit, but modulo 2 instead of modulo UINT_MAX+1, the XOR operation implements both addition and subtraction, and the final negation is a no-op because $-1equiv 1$ and $-0equiv 0 pmod 2$. So what is left in the bitwise version is exactly
i ^= j; j ^= i; i ^= j;
answered Sep 2 at 14:06
Henning Makholm
230k16296527
1
Thanks for the alternative solution to swap 2 numbers, this is insightful.
– Prashin Jeevaganth
Sep 2 at 14:08
add a comment |Â
up vote
16
down vote
up vote
16
down vote
Note that you can do the same thing without bitwise operators (at least for unsigned integer types since they can't overflow into undefined behavior):
// i == x j == y
i += j; // i == x+y j == y
j -= i; // i == x+y j == -x
i += j; // i == y j == -x
j = -j; // i == y j == x
Now if we do this bit for bit, but modulo 2 instead of modulo UINT_MAX+1, the XOR operation implements both addition and subtraction, and the final negation is a no-op because $-1equiv 1$ and $-0equiv 0 pmod 2$. So what is left in the bitwise version is exactly
i ^= j; j ^= i; i ^= j;
answered Sep 2 at 14:06
Henning Makholm
230k16296527
Note that you can do the same thing without bitwise operators (at least for unsigned integer types since they can't overflow into undefined behavior):
// i == x j == y
i += j; // i == x+y j == y
j -= i; // i == x+y j == -x
i += j; // i == y j == -x
j = -j; // i == y j == x
Now if we do this bit for bit, but modulo 2 instead of modulo UINT_MAX+1, the XOR operation implements both addition and subtraction, and the final negation is a no-op because $-1equiv 1$ and $-0equiv 0 pmod 2$. So what is left in the bitwise version is exactly
i ^= j; j ^= i; i ^= j;
answered Sep 2 at 14:06
Henning Makholm
230k16296527
answered Sep 2 at 14:06
Henning Makholm
230k16296527
answered Sep 2 at 14:06
Henning Makholm
230k16296527
answered Sep 2 at 14:06
Henning Makholm
230k16296527
230k16296527
1
Thanks for the alternative solution to swap 2 numbers, this is insightful.
– Prashin Jeevaganth
Sep 2 at 14:08
add a comment |Â
1
Thanks for the alternative solution to swap 2 numbers, this is insightful.
– Prashin Jeevaganth
Sep 2 at 14:08
1
1
Thanks for the alternative solution to swap 2 numbers, this is insightful.
– Prashin Jeevaganth
Sep 2 at 14:08
Thanks for the alternative solution to swap 2 numbers, this is insightful.
– Prashin Jeevaganth
Sep 2 at 14:08
add a comment |Â
up vote
7
down vote
You already answered your question, but if you want an algebraic explanation note that for any $x$:
$$x oplus 0 = x$$
$$x oplus x = 0$$
So:
$$i_0 = i, j_0 = j$$
$$i_1 = i_0 oplus j_0, j_1 = j_0$$
$$i_2 = i_1, j_2 = i_1 oplus j_1 = i_0 oplus j_0 oplus j_0 = i_0$$
$$i_3 = i_2 oplus j_2 = i_1 oplus i_0 = i_0 oplus j_0 oplus i_0 = j_0, j_3 = j_2 = i_0$$
answered Sep 2 at 13:55
mbjoe
15419
add a comment |Â
up vote
7
down vote
You already answered your question, but if you want an algebraic explanation note that for any $x$:
$$x oplus 0 = x$$
$$x oplus x = 0$$
So:
$$i_0 = i, j_0 = j$$
$$i_1 = i_0 oplus j_0, j_1 = j_0$$
$$i_2 = i_1, j_2 = i_1 oplus j_1 = i_0 oplus j_0 oplus j_0 = i_0$$
$$i_3 = i_2 oplus j_2 = i_1 oplus i_0 = i_0 oplus j_0 oplus i_0 = j_0, j_3 = j_2 = i_0$$
answered Sep 2 at 13:55
mbjoe
15419
add a comment |Â
up vote
7
down vote
up vote
7
down vote
You already answered your question, but if you want an algebraic explanation note that for any $x$:
$$x oplus 0 = x$$
$$x oplus x = 0$$
So:
$$i_0 = i, j_0 = j$$
$$i_1 = i_0 oplus j_0, j_1 = j_0$$
$$i_2 = i_1, j_2 = i_1 oplus j_1 = i_0 oplus j_0 oplus j_0 = i_0$$
$$i_3 = i_2 oplus j_2 = i_1 oplus i_0 = i_0 oplus j_0 oplus i_0 = j_0, j_3 = j_2 = i_0$$
answered Sep 2 at 13:55
mbjoe
15419
You already answered your question, but if you want an algebraic explanation note that for any $x$:
$$x oplus 0 = x$$
$$x oplus x = 0$$
So:
$$i_0 = i, j_0 = j$$
$$i_1 = i_0 oplus j_0, j_1 = j_0$$
$$i_2 = i_1, j_2 = i_1 oplus j_1 = i_0 oplus j_0 oplus j_0 = i_0$$
$$i_3 = i_2 oplus j_2 = i_1 oplus i_0 = i_0 oplus j_0 oplus i_0 = j_0, j_3 = j_2 = i_0$$
answered Sep 2 at 13:55
mbjoe
15419
answered Sep 2 at 13:55
mbjoe
15419
answered Sep 2 at 13:55
mbjoe
15419
answered Sep 2 at 13:55
mbjoe
15419
15419
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2902731%2flogic-behind-bitwise-operators-in-c%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Beware that this doesn't work if
iandjhappen to be the same variable!– Henning Makholm
Sep 2 at 13:59
@HenningMakholm ah ok noted, applying it 3 times has the same effect as applying 1 time and that will cause one of the values to be full of zeroes
– Prashin Jeevaganth
Sep 2 at 14:03
2
It works for $i = j$ too.
– mbjoe
Sep 2 at 14:11
@mbjoe oh ok just noticed
– Prashin Jeevaganth
Sep 2 at 15:09
9
@mbjoe: It works for
iandjhaving the same value, but not for them being the same variable.– celtschk
Sep 2 at 15:59