有关XOR运算
XOR又称为异或运算。
运算规则为:和自己相同的数值异或运算为0,不同的为1。
异或运算满易做图换律,结合律。即 a^(b^a) = b^(a^a)
由于异或运算的自反性和满易做图换律、结合律,常常被用于一些技巧性较强的应用中,如面试题。下面举几个应用:
1,不用中间变量的两个变量交换数值:
void inplace_swap(int* x, int* y)
{
// x y
*y = *x ^ *y;// a a^b
*x = *x ^ *y;// a^a^b a^b
*y = *x ^ *y;// a^a^b=b a^a^b^(a^b) = a^(a^a)^(b^b) = a^0^0 = a
}
2,编程之美中应用XOR的题目:
1.11 NIM(1)
4.6 桶中取黑白球
3, 找唯一重复的数字:1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,设计一种算法找出来?
利用了异或运算的交换律和结合律。
3,另外,异或运算还可应用于数据校验和数据加密。
如:网络传输中的帧数据异或结果作为一个校验值。
C=P^K其中P为明文、K为密钥、C为密文
两边同时做K的异或运算: C^K = P^K^K = P ,运用自反性解密。得到明文。
摘自 bestwolf1983的专栏
补充:软件开发 , Vc ,