位運算中的異或運算 .

位運算是非常迅速的，因為它直接對記憶體中的二進制資料進行操作。 

按位運算除了，按位與，按位非，按位左移，按位右移，還有按位異或。

按位異或運算定義，

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) {  

            // 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) {  

            //說明①: in[i]的高5位給了a的低5位   

            byte b = (byte) (((((int) in[i]) << 18) ^ seed) >> (18 - 5));  

            //說明②: in[i]的低3位給了b的高3位   

            //0x1f=16+15=31=2^5-1=00011111;   

            //0xe0=11100000;   

然後就可以編寫decode函數了

        int len = in.length;// encode中的out[i]是這裡decode中的in[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   

            seed = (seed * 84723701 ^ seed ^ in[i]);  

//最後的輸出答案微雷，答案是“真雙核引擎是全球最快的浏覽器核心！！！！”  

這道題還有C++版本的，幾乎和JAVA版本一模一樣。

#include "stdafx.h"   

#include <stdio.h>     

//#include <stdlib.h>     

#include <assert.h>     

#include <string.h>     

#define uint8_t unsigned char     

#define uint32_t unsigned int     

#define size_t unsigned int    

int  encode(const  void*  raw_in,  void*  raw_out,  uint32_t  password,  size_t  len)   

{   

const  uint8_t*  in  =  (const  uint8_t*)raw_in;   

uint8_t*  out  =  (uint8_t*)raw_out;   

uint32_t  seed  =  password  ^  0x3feb3c98u;   

for  (size_t  i  =  0  ;  i  <  len;  ++i)  {   

uint8_t  a  =  (  in[i]  ^  seed  )  >>  4;   

uint8_t  b  =  (  (  ((uint32_t)in[i])  <<  17  )  ^  seed  )  >>  (17-4);   

a  &=  15;  //00001111   

b  &=  240; //11110000=2^7+2^6+2^5+2^4=128+64+32+16=240   

a  =  15  &  (  a  ^  (b  <<  3));   

out[i]  =  a  |  b;   

seed  =  (seed  *  48475829  ^  seed  ^  in[i]);   

}   

return 0;  

int  decode(const  void*  raw_in,  void*  raw_out,  uint32_t  password,  size_t  len)   

//  請在此處補全代碼 - 開始   

    uint8_t a=in[i]&15;  

    uint8_t b=in[i]&240;  

    a=((a<<4)^seed)&240;  

    b=((((uint32_t)b<<13)^seed)>>17)&15;  

    out[i]  =  a  |  b;   

    seed  =  (seed  *  48475829  ^  seed  ^  out[i]);   

//  請在此處補全代碼 - 結束   

int  main()   

const  uint8_t  buf1[]  =  {0x1e,  0x7b,  0x8f,  0x63,  0x6f,  0x69,  0x26,  0x23,  0x64,  0xe1,  0x09,  0x21,  0x13,  0x2b,  0x37,  0xdf,  0xa4,  0x7f,  0x45,  0xe3,  0x6b,  0xda,  0x6a,  0x00,  0x93,  0x4b,  0xd1,  0x81,  0x92,  0x20,  0x69,  0x74,  0xf9,  0xf1,  0x1f,  0xb9,  0x1f,  0x6d,  0x20,  0x7b,  0xe8,  0x0c,  0x89,  0x29,  0x77,  0x65,  0xaa,  0x0f,  0xdb,  0x45,  0x4e,  0x58,  0x39,  0x98,  0x7f,  0xa7,  0x04,  0x71,  0xb4,  0xe1,  0xe4,  };   

uint8_t  buf2[100]  = "";   

const  uint32_t  password  =  0xe53e6eb6u;   

const  size_t  len  =  sizeof(buf1);   

decode(buf1,  buf2,  password,  len);   

printf("%s\n",  buf2);   

//輸出答案:搜狗搜尋是全球首個中文網頁收錄量達到100億的搜尋引擎！！！！！