android 程序员计算器异或计算 手机xor异或计算器手机计算器「android 程序员计算器异或计算 手机xor异或计算器」

大家比较熟悉的逻辑运算，主要是"与运算"(AND)和"或运算"(OR)，还有一种"异或运算"(XOR)，也非常重要。

本文介绍异或运算的含义和应用。

XOR 是 exclusive OR 的缩写。英语的 exclusive 意思是"专有的，独有的"，可以理解为 XOR 是更单纯的 OR 运算。

我们知道，OR 运算的运算子有两种情况，计算结果为。

(1)一个为 true，另一个为 false;

(2)两个都为 true。

上面两种情况，有时候需要明确区分，所以引入了 XOR。

XOR 排除了第二种情况，只有第一种情况(一个运算子为，另一个为)才会返回 true，所以可以看成是更单纯的 OR 运算。也就是说， XOR 主要用来判断两个值是否不同。

XOR 一般使用插入符号(caret)表示。如果约定 为 false， 为 true，那么 XOR 的运算真值表如下。

0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0

XOR 运算有以下的运算定律。由于非常简单，这里就省略证明了。

(1)一个值与自身的运算，总是为 false。

x ^ x = 0

(2)一个值与 0 的运算，总是等于其本身。

x ^ 0 = x

(3)可交换性

x ^ y = y ^ x

(4)结合性

x ^ (y ^ z) = (x ^ y) ^ z

根据上面的这些运算定律，可以得到异或运算的很多重要应用。

3.1 简化计算

多个值的异或运算，可以根据运算定律进行简化。

a ^ b ^ c ^ a ^ b = a ^ a ^ b ^ b ^ c = 0 ^ 0 ^ c = c

3.2 交换值

两个变量连续进行三次异或运算，可以互相交换值。

假设两个变量是和，各自的值是和。下面就是和进行三次异或运算，注释部分是每次运算后两个变量的值。

x = x ^ y // (a ^ b, b) y = x ^ y // (a ^ b, a ^ b ^ b) => (a ^ b, a) x = x ^ y // (a ^ b ^ a, a) => (b, a)

这是两个变量交换值的最快方法，不需要任何额外的空间。

3.3 加密

异或运算可以用于加密。

第一步，明文(text)与密钥(key)进行异或运算，可以得到密文(cipherText)。

text ^ key = cipherText

第二步，密文与密钥再次进行异或运算，就可以还原成明文。

cipherText ^ key = text

原理很简单，如果明文是 x，密钥是 y，那么 x 连续与 y 进行两次异或运算，得到自身。

(x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x

3.4 数据备份

异或运算可以用于数据备份。

文件 x 和文件 y 进行异或运算，产生一个备份文件 z。

x ^ y = z

以后，无论是文件 x 或文件 y 损坏，只要不是两个原始文件同时损坏，就能根据另一个文件和备份文件，进行还原。

x ^ z = x ^ (x ^ y) = (x ^ x) ^ y = 0 ^ y = y

上面的例子是 y 损坏，x 和 z 进行异或运算，就能得到 y。

一些面试的算法题，也能使用异或运算快速求解。

请看下面这道题。

一个数组包含 n-1 个成员，这些成员是 1 到 n 之间的整数，且没有重复，请找出缺少的那个数字。

最快的解答方法，就是把所有数组成员(A[0] 一直到 A[n-2])与 1 到 n 的整数全部放在一起，进行异或运算。

A[0] ^ A[1] ^ ... ^ A[n-2] ^ 1 ^ 2 ^ ... ^ n

上面这个式子中，每个数组成员都会出现两次，相同的值进行异或运算就会得到 0。只有缺少的那个数字出现一次，所以最后得到的就是这个值。

你可能想到了，加法也可以解这道题。

1 + 2 + ... + n - A[0] - A[1] - ... - A[n-2]

但是，加法的速度没有异或运算快，而且需要额外的空间。如果数字比较大，还有溢出的可能。

下面是一道类似的题目，大家可以作为练习。

一个数组包含 n+1 个成员，这些成员是 1 到 n 之间的整数。只有一个成员出现了两次，其他成员都只出现一次，请找出重复出现的那个数字。

• That XOR Trick

阿勒泰版权声明：本网信息来自于互联网，目的在于传递更多信息，并不代表本网赞同其观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，并请自行核实相关内容。本站不承担此类作品侵权行为的直接责任及连带责任。如若本网有任何内容侵犯您的权益，请及时联系我们，本站将会在24小时内处理完毕，E-mail：xinmeigg88@163.com