a ^= b;
b ^= a;
a ^= b;
上述代码等价于std::swap(a,b) 在需要用到swap时不妨替换成这个
以下是证明过程:
已知:
1.异或的定义是只能或 不能与或者非(有点难理解 但是我的表达能力不太好 凑合着看吧)
2.且交换律 结合律 都在异或上适用
3.a ^ a = 0 且 a ^ 0 = a
所以:
在执行完a ^= b(a = a ^ b)时
a = a ^ b;
b = b;
在执行完b ^= a(b = b ^ a)时
可证:
[ b ^= a ] = [ b = b ^ (a ^ b) ] = [ b = b ^ a ^ b ] = [ b = a ^ b ^ b ] = [ b = a ^ (b ^ b) ] = [ b = a ^ 0 ] = [ b = a ]
b ^= a 等价于 b = a(原来)
因此:
a = a ^ b;
b = a(原来);
在执行完a ^= b(a = a ^ b)时:
可证:
[ a ^= b ] = [ a = (a ^ b) ^ a ] = [ a = a ^ b ^ a ] = [ a = b ^ a ^ a ] = [ a = b ^ (a ^ a) ] = [ a = b ^ 0 ] = [ a = b ]
a ^= b 等价于 a = b(原来)
因此
a = b;
b = a;
4 comments
-
陈锦润 LV 8 @ 2024-11-22 20:54:33异或的定义:
1 ^ 1因为两个值相等(都为true) 所以1 ^ 1=0
1 ^ 0因为两个值不等(一个true一个false) 所以1 ^ 0=1
0 ^ 1同理 因此0 ^ 1=1
0 ^ 0因为两个值相等(都为false) 所以0 ^ 0=0
那么a ^ b就是将a的二进制与b的二进制按位异或:
假设a和b都为8位无符号整数(0~255内的整数)
设 a = 114, b = 51
那么a ^ b = 01110010 ^ 00110011
第一位:0 ^ 1 = 1
第二位:1 ^ 1 = 0
第三位:0 ^ 0 = 0
第四位:0 ^ 0 = 0
第五位:1 ^ 1 = 0
第六位:1 ^ 1 = 0
第七位:1 ^ 0 = 1
第八位:0 ^ 0 = 0
所以114 ^ 51 = 01000001 = 65
-
@ 2024-11-17 16:31:27666
-
@ 2024-11-16 21:39:46
应用:
template <typename Num1, typename Num2> unsigned long long gcd(Num1 x, Num2 y) { if(x > y) { while(x % y != 0) { x ^= y; y ^= x; x ^= y; y = y % x; } return y; } else { while(y % x != 0) { y ^= x; x ^= y; y ^= x; x = x % y; } return x; } }优化到极致的gcd
- 1