位运算中的异或运算 .

位运算是非常迅速的，因为它直接对内存中的二进制数据进行操作。 

按位运算除了，按位与，按位非，按位左移，按位右移，还有按位异或。

按位异或运算定义，

1 ^ 1=0

1 ^ 0=1

0 ^ 1=1

0 ^ 0=0

异或，就是“看看你们到底一样不一样。不一样就为1，一样就为0。”

按位异或运算的规律是

定理一a ^ b = b ^ a

定理二 a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;

定理三 a ^ b ^ a = b, a ^ a^ b = b, b ^ a^ a = b

定理四若d = a ^ b ^ c，则a = d ^ b ^ c

证明:

在d = a ^ b ^ c两边同时异或^ b ^ c，得

d ^ b ^ c =a ^ b ^ c ^ b ^ c

d ^ b ^ c =a ^ b ^ b ^ c ^ c，由定理三得

d ^ b ^ c =a ^ c ^ c，同样由定理三得

d ^ b ^ c =a

异或的几个常见用途:

(1) 实现两个值的交换，而不必使用临时变量。

    例如交换两个整数a=10100001，b=00000110的值，可通过下列语句实现：

　　　　a = a^b；　　//a=10100111

　　　　b = b^a；　　//b=10100001

　　　　a = a^b；　　//a=00000110

(2) 在汇编语言中经常用于将变量置零：

   xor   a，a

(3) 使某些特定的位翻转

    例如对数10100001的第2位和第3位翻转，则可以将该数与00000110进行按位异或运算。

　　　　　  10100001^00000110 = 10100111

(4)使用定理三进行编码解码

由B ^ A^ A = B，我们可以假设一聊天记录是B，密钥是A。现在B ^ A之后，成了密文了。为了解密，对密文再使用密钥A进行一次异或运算即可。也即是B ^ A^ A = B。

看看今年SOGOU校招在线测试的一道编码解码题目。原题(JAVA版本)如下

public class Test {

    public static void encode(byte[] in, byte[] out, int password) {
        int len = in.length;

        int seed = password ^ 0x3e1e25e6;
        for (int i = 0; i < len; ++i) {
            byte a = (byte) ((in[i] ^ seed) >> 3);
            byte b = (byte) (((((int) in[i]) << 18) ^ seed) >>> (18 - 5));
            a &= 0x1f;
            b &= 0xe0;
            out[i] = (byte) (a | b);
            seed = (seed * 84723701 ^ seed ^ out[i]);
        }
    }

    public static void decode(byte[] in, byte[] out, int password) {
        int len = in.length;
        int seed = password ^ 0x3e1e25e6;
        for (int i = 0; i < len; ++i) {
            // fill the code here
        }
    }

    public static void main(String[] args) throws Exception {
        int password = 0xfdb4d0e9;
        byte[] buf1 = { -5, 9, -62, -122, 50, 122, -86, 119, -101, 25, -64,
                -97, -128, 95, 85, 62, 99, 98, -94, 76, 12, 127, 121, -32,
                -125, -126, 15, 18, 100, 104, -32, -111, -122, 110, -4, 60, 57,
                21, 36, -82, };
        byte[] buf2 = new byte[buf1.length];
        decode(buf1, buf2, password);
        System.out.println(new String(buf2, "GBK"));
    }
}

题目要求补充decode函数。那么根据encode函数就可以补充decode函数。解题要点是位运算中的左移，右移，按位与，按位异或，按位异或定理三。

 先来理解encode函数。

public static void encode(byte[] in, byte[] out, int password) {
        int len = in.length;

        int seed = password ^ 0x3e1e25e6;
        for (int i = 0; i < len; ++i) {
            byte a = (byte) ((in[i] ^ seed) >> 3);
            //说明①: in[i]的高5位给了a的低5位
            byte b = (byte) (((((int) in[i]) << 18) ^ seed) >> (18 - 5));
            //说明②: in[i]的低3位给了b的高3位
            a &= 0x1f;
            //0x1f=16+15=31=2^5-1=00011111;
            b &= 0xe0;
            //0xe0=11100000;
            out[i] = (byte) (a | b);
            seed = (seed * 84723701 ^ seed ^ out[i]);
        }
    }

然后就可以编写decode函数了

    public static void decode(byte[] in, byte[] out, int password) {
        int len = in.length;// encode中的out[i]是这里decode中的in[i]
        int seed = password ^ 0x3e1e25e6;
        for (int i = 0; i < len; ++i) {
        	byte a = (byte) (in[i] & 0x1f);
//参照式⑤，还原输出结果，取in[i]的低5位
        	byte b = (byte) (in[i] & 0xe0); 
//参照式⑤，还原输出结果，取in[i]的高3位
        	a = (byte) (((a <<3) ^ seed) & 248); 
//参照定理三B ^ A^ A = B，参照式①byte a = (byte) ((in[i] ^ seed) >>> 3)
//式①中的in[i]相当于B，seed相当于A，(a<<3)相当 B ^ A 故((a <<3) ^ seed)表示in[i]高5
//位的这5个数字，为了将这5个数字放入高5位的位置上，还需&11111000，即&248。
//11111000=2^7+2^6+2^5+2^4+2^3=128+64+32+16+8=248
        	b = (byte) ((((((int) b) << (18 - 5)) ^ seed) >> 18) & 7);
//类似地，逆向式②，得到的结果将放入out[i]的低3位，故&00000111，即&7。
//00000111=2^0+2^1+2^2=1+2+4=7
        	out[i] = (byte) (a | b);
        	seed = (seed * 84723701 ^ seed ^ in[i]);
        }
    }

//最后的输出答案微雷，答案是“真双核引擎是全球最快的浏览器内核！！！！”

这道题还有C++版本的，几乎和JAVA版本一模一样。