位运算是非常迅速的，因为它直接对内存中的二进制数据进行操作。
按位运算除了，按位与，按位非，按位左移，按位右移，还有按位异或。
按位异或运算定义，
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?
- 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"));
- }
- }
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?
- 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]);
- }
- }
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?
- 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]);
- }
- }
- //最后的输出答案微雷，答案是“真双核引擎是全球最快的浏览器内核！！！！”
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?
- #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)
- {
- 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]&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]);
- // 请在此处补全代码 - 结束
- }
- return 0;
- }
- 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);
- return 0;
- }
- //输出答案:搜狗搜索是全球首个中文网页收录量达到100亿的搜索引擎！！！！！
时间： 2024-10-01 07:15:47