有关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的专栏
- 上一篇：利用google获取二级域名
- 下一篇：ubuntu安装graphviz
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻