位运算中的异或运算 .

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

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

按位异或运算定义,

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版本)如下

 

[java] view plaincopyprint?

  1. public class Test {  
  2.   
  3.     public static void encode(byte[] in, byte[] out, int password) {  
  4.         int len = in.length;  
  5.   
  6.         int seed = password ^ 0x3e1e25e6;  
  7.         for (int i = 0; i < len; ++i) {  
  8.             byte a = (byte) ((in[i] ^ seed) >> 3);  
  9.             byte b = (byte) (((((int) in[i]) << 18) ^ seed) >>> (18 - 5));  
  10.             a &= 0x1f;  
  11.             b &= 0xe0;  
  12.             out[i] = (byte) (a | b);  
  13.             seed = (seed * 84723701 ^ seed ^ out[i]);  
  14.         }  
  15.     }  
  16.   
  17.     public static void decode(byte[] in, byte[] out, int password) {  
  18.         int len = in.length;  
  19.         int seed = password ^ 0x3e1e25e6;  
  20.         for (int i = 0; i < len; ++i) {  
  21.             // fill the code here   
  22.         }  
  23.     }  
  24.   
  25.     public static void main(String[] args) throws Exception {  
  26.         int password = 0xfdb4d0e9;  
  27.         byte[] buf1 = { -5, 9, -62, -122, 50, 122, -86, 119, -101, 25, -64,  
  28.                 -97, -128, 95, 85, 62, 99, 98, -94, 76, 12, 127, 121, -32,  
  29.                 -125, -126, 15, 18, 100, 104, -32, -111, -122, 110, -4, 60, 57,  
  30.                 21, 36, -82, };  
  31.         byte[] buf2 = new byte[buf1.length];  
  32.         decode(buf1, buf2, password);  
  33.         System.out.println(new String(buf2, "GBK"));  
  34.     }  
  35. }  
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函数。

 

[java] view plaincopyprint?

  1. public static void encode(byte[] in, byte[] out, int password) {  
  2.         int len = in.length;  
  3.   
  4.         int seed = password ^ 0x3e1e25e6;  
  5.         for (int i = 0; i < len; ++i) {  
  6.             byte a = (byte) ((in[i] ^ seed) >> 3);  
  7.             //说明①: in[i]的高5位给了a的低5位   
  8.             byte b = (byte) (((((int) in[i]) << 18) ^ seed) >> (18 - 5));  
  9.             //说明②: in[i]的低3位给了b的高3位   
  10.             a &= 0x1f;  
  11.             //0x1f=16+15=31=2^5-1=00011111;   
  12.             b &= 0xe0;  
  13.             //0xe0=11100000;   
  14.             out[i] = (byte) (a | b);  
  15.             seed = (seed * 84723701 ^ seed ^ out[i]);  
  16.         }  
  17.     }  
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函数了

 

[java] view plaincopyprint?

  1.     public static void decode(byte[] in, byte[] out, int password) {  
  2.         int len = in.length;// encode中的out[i]是这里decode中的in[i]   
  3.         int seed = password ^ 0x3e1e25e6;  
  4.         for (int i = 0; i < len; ++i) {  
  5.             byte a = (byte) (in[i] & 0x1f);  
  6. //参照式⑤,还原输出结果,取in[i]的低5位   
  7.             byte b = (byte) (in[i] & 0xe0);   
  8. //参照式⑤,还原输出结果,取in[i]的高3位   
  9.             a = (byte) (((a <<3) ^ seed) & 248);   
  10. //参照定理三B ^ A^ A = B,参照式①byte a = (byte) ((in[i] ^ seed) >>> 3)   
  11. //式①中的in[i]相当于B,seed相当于A,(a<<3)相当 B ^ A 故((a <<3) ^ seed)表示in[i]高5   
  12. //位的这5个数字,为了将这5个数字放入高5位的位置上,还需&11111000,即&248。   
  13. //11111000=2^7+2^6+2^5+2^4+2^3=128+64+32+16+8=248   
  14.             b = (byte) ((((((int) b) << (18 - 5)) ^ seed) >> 18) & 7);  
  15. //类似地,逆向式②,得到的结果将放入out[i]的低3位,故&00000111,即&7。   
  16. //00000111=2^0+2^1+2^2=1+2+4=7   
  17.             out[i] = (byte) (a | b);  
  18.             seed = (seed * 84723701 ^ seed ^ in[i]);  
  19.         }  
  20.     }  
  21.   
  22. //最后的输出答案微雷,答案是“真双核引擎是全球最快的浏览器内核!!!!”  
    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版本一模一样。

 

[cpp] view plaincopyprint?

  1. #include "stdafx.h"   
  2. #include <stdio.h>     
  3. //#include <stdlib.h>     
  4. #include <assert.h>     
  5. #include <string.h>     
  6.   
  7. #define uint8_t unsigned char     
  8. #define uint32_t unsigned int     
  9. #define size_t unsigned int    
  10.   
  11.   
  12. int  encode(const  void*  raw_in,  void*  raw_out,  uint32_t  password,  size_t  len)   
  13. {   
  14. const  uint8_t*  in  =  (const  uint8_t*)raw_in;   
  15. uint8_t*  out  =  (uint8_t*)raw_out;   
  16.   
  17. uint32_t  seed  =  password  ^  0x3feb3c98u;   
  18. for  (size_t  i  =  0  ;  i  <  len;  ++i)  {   
  19. uint8_t  a  =  (  in[i]  ^  seed  )  >>  4;   
  20. uint8_t  b  =  (  (  ((uint32_t)in[i])  <<  17  )  ^  seed  )  >>  (17-4);   
  21. a  &=  15;  //00001111   
  22. b  &=  240; //11110000=2^7+2^6+2^5+2^4=128+64+32+16=240   
  23. a  =  15  &  (  a  ^  (b  <<  3));   
  24. out[i]  =  a  |  b;   
  25. seed  =  (seed  *  48475829  ^  seed  ^  in[i]);   
  26. }   
  27. return 0;  
  28. }   
  29.   
  30.   
  31. int  decode(const  void*  raw_in,  void*  raw_out,  uint32_t  password,  size_t  len)   
  32. {   
  33. const  uint8_t*  in  =  (const  uint8_t*)raw_in;   
  34. uint8_t*  out  =  (uint8_t*)raw_out;   
  35.   
  36. uint32_t  seed  =  password  ^  0x3feb3c98u;   
  37. for  (size_t  i  =  0  ;  i  <  len;  ++i)  {   
  38. //  请在此处补全代码 - 开始   
  39.     uint8_t a=in[i]&15;  
  40.     uint8_t b=in[i]&240;  
  41.     a=((a<<4)^seed)&240;  
  42.     b=((((uint32_t)b<<13)^seed)>>17)&15;  
  43.     out[i]  =  a  |  b;   
  44.     seed  =  (seed  *  48475829  ^  seed  ^  out[i]);   
  45. //  请在此处补全代码 - 结束   
  46. }   
  47. return 0;  
  48. }   
  49. int  main()   
  50. {   
  51. 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,  };   
  52. uint8_t  buf2[100]  = "";   
  53. const  uint32_t  password  =  0xe53e6eb6u;   
  54. const  size_t  len  =  sizeof(buf1);   
  55. decode(buf1,  buf2,  password,  len);   
  56. printf("%s\n",  buf2);   
  57. return 0;  
  58. }   
  59.   
  60. //输出答案:搜狗搜索是全球首个中文网页收录量达到100亿的搜索引擎!!!!!  
时间: 2013-03-16

位运算中的异或运算 .的相关文章

位运算反(~)与(&amp;)异或(^)或(|)右移(&gt;&gt;)左移(&lt;&lt;)

原文:位运算反(~)与(&)异或(^)或(|)右移(>>)左移(<<) 先知道这两个二进制数据的特点:   1=0000 0000 0000 0000 0000 0000 0000 0001                                               -1=1000 0000 0000 0000 0000 0000 0000 0001              1.最高位(首位)表示正负(0为正,1为负)             2.最低位(

mfc-串口通信中 将接收编辑框的数据进行异或运算

问题描述 串口通信中 将接收编辑框的数据进行异或运算 目前呢思路是将编辑框的数据获取过来 赋予一个变量 将变量输出到另一编辑框 可是具体的过程怎么实现?异或运算符具体怎么实现这个?求大神指教 解决方案 将数据写入文本框 setdlgitemint 读取 getdlgitemint 异或 ^ 解决方案二: http://blog.csdn.net/zacklin/article/details/7454735 解决方案三: 那么异或可以对一组数据进行运算么?具体该怎么使用? 解决方案四: 那么异或

位运算-char类型的两个数经过异或运算之后数据类型怎么变成int类型了?

问题描述 char类型的两个数经过异或运算之后数据类型怎么变成int类型了? #include int main(void){ char a = 0xa2; char b = 0x32; char test = a ^ b; printf(""%#x"" test); return 0; } 我期望的打印结果是:0x90结果打印的是:0xffffff90 好像数据变成int类型了,这个是怎么回事? 解决方案 c int or wint_t When used wit

java-两个很长的16进制字符串怎么进行异或运算?

问题描述 两个很长的16进制字符串怎么进行异或运算? str1=""0d1fe39e573488cf"" str2=""0d1fe39e573488ee595acd5c6d4ce0f445476794"" 怎不进行异或运算? 由于太长不能转化成long 解决方案 每2个一组,存入数组,然后循环异或. 解决方案二: byte[] array1 = str1.getBte();byte[] array2 = str2.getByt

c异或运算 c异或运算符号_C 语言

与运算:&两者都为1为1,否则为0 1&1=1,  1&0=0,  0&1=0,  0&0=0 或运算:|两者都为0为0,否则为11|1 = 1,  1|0 = 1,  0|1 = 1, 0|0 = 0 非运算:~1取0,0取1~1 = 0, ~0 = 1~(10001) = 01110 异或运算两者相等为0,不等为11^1=0, 1^0=1, 0^1=1, 0^0=0 下面是详细的解释: 位运算    位运算的运算分量只能是整型或字符型数据,位运算把运算对象看作是

HDOJ 1287 破译密码(异或运算)

Problem Description 有个叫"猪头帮"的国家,采用一种简单的文法加密,他们所用的语言里面只有大写字母,没有其他任何字符:现在还知道他们加密的方法是:只用一个大写字母和原文进行异或运算生成密文.请你帮忙解开. Input 有若干组,每组输入有2行,第一行整数N表示有N个密文,接着一行有N个整数分别表示N个密文. Output 输出仅有大写字母组成的原文. Sample Input 30 17 6 9 8 3 0 1 6 7 4 5 10 11 8 9 14 15 12

authcode函数使用异或运算进行加密和解密

康盛的 authcode 函数可以说对中国的PHP界作出了重大贡献.包括康盛自己的产品,以及大部分中国使用PHP的公司都用这个函数进行加密,authcode 是使用异或运算进行加密和解密. 原理如下,假如: 加密 明文:1010 1001 密匙:1110 0011 密文:0100 1010 得出密文0100 1010,解密之需和密匙异或下就可以了 解密 密文:0100 1010 密匙:1110 0011 明文:1010 1001 并没有什么高深的算法,密匙重要性很高,所以,关键在于怎么生成密匙.

java中Double类型的运算精度丢失的问题 (小数点多出99999999999999)

 在使用Java,double 进行运算时,经常出现精度丢失的问题,总是在一个正确的结果左右偏0.0000**1. 特别在实际项目中,通过一个公式校验该值是否大于0,如果大于0我们会做一件事情,小于0我们又处理其他事情. 这样的情况通过double计算出来的结果去和0比较大小,尤其是有小数点的时候,经常会因为精度丢失而导致程序处理流程出错.  首先贴一个使用的代码: /** * 将double类型数据转为字符串(如将18.4转为1840,如果需要1840.0,把int强转去掉即可) * @par

Python中实现三目运算的方法

  这篇文章主要介绍了Python中实现三目运算的方法,本文用and/or 运算符模拟实现三目运算,需要的朋友可以参考下 C语言中三目运算符 代码如下: expression ?expr1:expr2; //expression 为真则取表达式expr1的值,否则取expr2的值 python三目实现方法: (1) expr=判断表达式 and expr1 or expr2 判断表达式为真,此时如果expr1为真则expr=expr1,为假则变成False or expr2,expr=expr2