浅谈算法中按位与

按位与^在算法中是一个常常用到的逻辑运算符，往往可以在算法设计中起到化腐朽为神奇的潜在力量。那么究竟如何理解这个神奇的运算符呢？下面浅谈并总结一下：

一、按位与的基本介绍

按位与
// 基本运算规则
1^1 = 0
1^0 = 1
0^0 = 0

// 常用运算性质
a^0 = a
a^a = 0

// 满足的数学规律
交换律：a^b^c = a^c^b = b^a^c= ...
结合律：a^b^c = a^(b^c) = ...

二、按位与的应用（意义）

按位与运算基本学过编程基础知识之后都能掌握，但是重要的是怎么去应用他，那么就必须从某种角度去理解他。

1）交换变量值

这估计是最常用也是最简单的一种用法了！

int a = 1,
    b = 2;

// 交换变量 a 和 b 的值
a = a ^ b;
b = b ^ a;
a = a ^ b;

// 最后 a = 2, b = 1

2）奇偶校验

这是非常有意思的性质，首先我们给出以下结论：

1. a(奇数) ^ 1 = (a - 1)(偶数);
2. b(偶数) ^ 1 = (b + 1)(奇数);

并给出以下简单证明：

1. 对任意奇数，其二进制最后一位一定为 1，而 1 的二进制最后一位也为 1，那么该奇数与 1 异或后得到的二进制数最后一位一定是 0。所以，我们可以判断得到的数一定是偶数。
2. 对任意偶数，其二进制最后一位一定为 0，而 1 的二进制最后一位为 1，那么该偶数与 1 异或后得到的二进制数最后一位一定是 1。所以，我们可以判断得到的数一定是奇数。

推广：

1. 奇数 ^ 奇数 = 偶数;
2. 偶数 ^ 偶数 = 偶数;
3. 奇数 ^ 偶数 = 奇数;

证明思路和前面相似，可以自己简单思考一下。

补充：
奇偶校验我在这里还想补充一个算法，那就是按位与 &。

先看这段代码：

if (a & 1 == 1)
  printf("奇数");
else
  printf("偶数");

简单总结一下就能给出以下性质：

1. a(奇数) & 1 = 1;
2. a(偶数) & 1 = 0;

并给出以下简单证明：

1. 对任意奇数，其二进制最后一位一定为 1，而 1 的二进制最后一位也为 1，那么该奇数与 1 按位与后得到的二进制数最后一位一定是 0。同时对于 1 的二进制除了最后一位之外都为 0，即任何数与 1 按位与除了二进制的最后一位有不同之外，其余位均为 0。所以，我们可以判断得到的数一定是 1（二进制 …0001）。
2. 对任意偶数，其二进制最后一位一定为 0，而 1 的二进制最后一位为 1，那么该偶数与 1 按位与后得到的二进制数最后一位一定是 1。同时对于 1 的二进制除了最后一位之外都为 0，即任何数与 1 按位与除了二进制的最后一位有不同之外，其余位均为 0。所以，我们可以判断得到的数一定是 0（二进制 …0000）。

进阶：

想判断两个数是不是同奇或同偶（可以自己分析原理）：

判断 a 与 b 是否为同奇或同偶
if ((a ^ b) & 1)
  printf("不是");
else
  printf("是");

了解上面的内容后可以看看 LeetCode 的一个题目：
1812. 判断国际象棋棋盘中一个格子的颜色