*明明自觉学会了不少知识，可真正开始做题时，却还是出现了“一支笔，一双手，一道力扣（Leetcode）做一宿”的窘境？你是否也有过这样的经历，题型不算很难，看题解也能弄明白，可一到自己做就变成了与题面面相觑无从下手。这就是基础知识掌握不扎实、不牢固导致的，我们以位运算为例，我将把位运算基础给你清楚讲述，再以例题带你实战体验。
一、位与运算符
位与运算符是一个二元的位运算符，也就是有两个操作数，表示为 x & y。
位与运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共 4 种情况。
通过这个表，我们得出一些结论：
1）无论是 0 或 1，只要位与上 1，还是它本身；
2）无论是 0 或 1，只要位与上 0，就变成 0；
所以对于位与来说，只要这一位上有一个 0，这一位的结果就会变成 0。
int main() { int a = 0b1010; int b = 0b0110; printf("%d\n", (a & b) ); return 0; }
- (1) 在C语言中，以 0b 作为前缀，表示这是一个二进制数。那么 a 的实际值就是 (1010) 。
- (2) 同样的， b 的实际值就是 (0110) ；
- (3) 那么这里 a & b 就是对 (1010) 和 (0110) 的每一位做表格中的 & 运算。
- 所以最后输出结果为：
- 因为输出的是十进制数，它的二进制表示为： (0010)_2。
- 注意：这里的 前导零 可有可无，作者写上前导零只是为了对齐以及让读者更加清楚位与的运算方式。
二、位与运算符的应用
1、奇偶性判定
- 我们判断一个数是奇数还是偶数，往往是通过取模 %来判断的，如下：
int main() { if(5 % 2 == 1) { printf("5是奇数\n"); } if(6 % 2 == 0) { printf("6是偶数\n"); } return 0; }
- 然而，我们也可以这么写：
int main() { if(5 & 1) { printf("5是奇数\n"); } if( (6 & 1) == 0 ) { printf("6是偶数\n"); } return 0; } 1.
- 这是利用了奇数和偶数分别的二进制数的特性，如下表所示：
- 所以，我们对任何一个数，通过将它和 0b1 进行位与，结果为零，则必然这个数的二进制末尾位为0，根据以上表就能得出它是偶数了；否则，就是奇数。
- 注意，由于 if 语句我们还没有实际提到过，所以这里简单提一下，后面会有系统的讲解：
- 对于以上语句，expr 代表的是一个表达式，表达式的值最后只有 零 或 非零，如果值为非零，才会执行 body中的内容。
2、取末五位
【例题1】给定一个数，求它的二进制表示的末五位，以十进制输出即可。
- 这个问题的核心就是：我们只需要末五位，剩下的位我们是不需要的，所以可以将给定的数 位与上0b11111，这样一来就直接得到末五位的值了。
- 代码实现如下：
int main() { int x; scanf("%d", &x); printf("%d\n", (x & 0b11111) ); return 0; }
那么如果问题变成下面的形式，代码又要怎么写呢？
【例题2】如果是想得到末七位、末九位、末十四位、末 K 位，应该如何实现呢？
3、消除末尾五位
【例题3】给定一个 32 位整数，要求消除它的末五位。
- 还是根据位与的性质，消除末五位的含义，有两层：
- 1）末五位，要全变成零；
- 2）剩下的位不变；
- 那么，根据位运算的性质，我们需要数，它的高27位都为1，低五位都为 0，则这个数就是：
- 但是如果要这么写，代码不疯掉，人也会疯掉，所以一般我们把它转成十六进制，每四个二进制位可以转成一个十六进制数，所以得到十六进制数为 0xffffffe0。
- 代码实现如下：
int main() { int x; scanf("%d", &x); printf("%d\n", (x & 0xffffffe0) ); return 0; }
提示： f 代表 4 个1； e 代表 3个1,1个0； 0 代表 4 个 0；
4、消除末尾连续1
【例题4】给出一个整数，现在要求将这个整数转换成二进制以后，将末尾连续的1都变成0，输出改变后的数（以十进制输出即可）。
- 我们知道，这个数的二进制表示形式一定是：
- 如果，我们把这个二进制数加上1，得到的就是：
- 我们把这两个数进行位与运算，得到：
- 所以，你学会了吗？
5、2的幂判定
【例题5】请用一句话，判断一个正数是不是2的幂。
- 如果一个数是 2 的幂，它的二进制表示必然为以下形式：
- 这个数的十进制值为 2 的 k 次。
- 那么我们将它减一，即 2 的 k 次 减一 的二进制表示如下（参考二进制减法的借位）：
- 于是 这两个数位与的结果为零，于是我们就知道了如果一个数 x 是 2 的幂，那么 x & (x-1) 必然为零。而其他情况则不然。所以本题的答案为：
三、位或运算符
位或运算符是一个二元的位运算符，也就是有两个操作数，表示为 x | y。位或运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共 4 种情况。
通过这个表，我们得出一些结论：
1）无论是 0 或 1，只要位或上 1，就变成1；
2）只有当两个操作数都是0的时候，才变成 0；
int main() { int a = 0b1010; int b = 0b0110; printf("%d\n", (a | b) ); return 0; }
(1) 在C语言中，以 0b 作为前缀，表示这是一个二进制数。那么 a 的实际值就是 (1010);
(2) 同样的，b 的实际值就是 (0110)；
(3) 那么这里 a | b 就是对 (1010) 和 (0110) 的每一位做表格中的 | 运算。
所以最后输出结果为：
因为输出的是十进制数，它的二进制表示为： (1110)。
四、位或运算符的应用
1、设置标记位
【例题1】给定一个数，判断它二进制低位的第 5 位，如果为 0，则将它置为 1。
这个问题，我们很容易联想到位或。我们分析一下题目意思，如果第 5 位为 1，不用进行任何操作；如果第 5 位为 0，则置为 1。言下之意，无论第五位是什么，我们都直接置为 1 即可，代码如下：
int main() { int x; scanf("%d", &x); printf("%d\n", x | 0b10000); return 0; }
2、置空标记位
【例题2】给定一个数，判断它二进制低位的第 5 位，如果为 1，则将它置为 0。
当我们学过位与以后，很容易得出这样一种做法：
int main() { int x; scanf("%d", &x); printf("%d\n", x & 0b11111111111111111111111111101111); return 0; }
其它位不能变，所以 位与 上1；第5位要置零，所以 位与 上0；这样写有个问题，就是这串数字太长了，一点都不美观，而且容易写错，当然我们也可以转换成 十六进制，转换的过程也有可能出错。
而我们利用位或，只能将第5位设置成1，怎么把它设置成0呢？
我们可以配合减法来用。分成以下两步：
1）首先，强行将低位的第5位置成1；
2）然后，强行将低位的第5位去掉；
第 (1) 步可以采用位或运算，而第 (2) 步，我们可以直接用减法即可。代码实现如下：
int main() { int x; int a = 0b10000; scanf("%d", &x); printf("%d\n", (x | a) - a ); return 0; }
注意：直接减是不行的，因为我们首先要保证那一位为 1，否则贸然减会产生借位，和题意不符。
3、低位连续零变一
【例题3】给定一个整数 x，将它低位连续的 0 都变成 1。
假设这个整数低位连续有 k 个零，二进制表示如下：
那么，如果我们对它进行减一操作，得到的二进制数就是：
我们发现，只要对这两个数进行位或，就能得到：
也正是题目所求，所以代码实现如下：
int main() { int x; scanf("%d", &x); printf("%d\n", x | (x-1) ); return 0; }
(1) x | (x-1) 就是题目所求的 “低位连续零变一” 。
4、低位首零变一
【例题4】给定一个整数 x，将它低位第一个 0 变成 1。
记得在评论区留下你的答案哦 ~
五、异或运算符
异或运算符是一个二元的位运算符，也就是有两个操作数，表示为 x ^ y。
异或运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共 4 种情况。
通过这个表，我们得出一些结论：
1）两个相同的十进制数异或的结果一定为零。
2）任何一个数和 0 的异或结果一定是它本身。
3）异或运算满足结合律和交换律。
int main() { int a = 0b1010; int b = 0b0110; printf("%d\n", (a ^ b) ); return 0; }
(1) 在C语言中，以 0b 作为前缀，表示这是一个二进制数。那么 a 的实际值就是 (1010) 。
(2) 同样的， b 的实际值就是 (0110) ；
(3) 那么这里 a ^ b 就是对 (1010) 和 (0110) 的每一位做表格中的 ^ 运算。
所以最后输出结果为：
因为输出的是十进制数，它的二进制表示为： (1100)。
六、异或运算符的应用
1、标记位取反
【例题1】给定一个数，将它的低位数起的第 4 位取反，0 变 1，1 变 0。
这个问题，我们很容易联想到异或。我们分析一下题目意思，如果第 4 位为 1，则让它异或上 0b1000 就能变成 0；如果第 4 位 为 0，则让它异或上 0b1000 就能变成 1，也就是无论如何都是异或上 0b1000 ，代码如
int main() { int x; scanf("%d", &x); printf("%d\n", x ^ 0b1000); return 0; }
2、变量交换
【例题2】给定两个数 a 和 b，用异或运算交换它们的值。
这个是比较老的面试题了，直接给出代码：
int main() { int a, b; while (scanf("%d %d", &a, &b) != EOF) { a = a ^ b; b = a ^ b; a = a ^ b; printf("%d %d\n", a, b); } return 0; }
我们直接来看 (1) 和 (2) 这两句话，相当于 b 等于 a ^ b ^ b ，根据异或的几个性质，我们知道，这时候的 b 的值已经变成原先 a 的值了。
而再来看第 (3) 句话，相当于 a 等于 a ^ b ^ a，还是根据异或的几个性质，这时候，a 的值已经变成了原先 b 的值。
从而实现了变量 a 和 b 的交换。
3、出现奇数次的数
【例题3】输入 n 个数，其中只有一个数出现了奇数次，其它所有数都出现了偶数次。求这个出现了奇数次的数。
根据异或的性质，两个一样的数异或结果为零。也就是所有出现偶数次的数异或都为零，那么把这 n 个数都异或一下，得到的数就一定是一个出现奇数次的数了。
int main() { int n, x, i, ans; scanf("%d", &n); ans = 0; for(i = 0; i < n; ++i) { scanf("%d", &x); ans = (ans ^ x); } printf("%d\n", ans); return 0; }
4、丢失的数
【例题4】给定一个 n-1 个数，分别代表 1 到 n 的其中 n-1 个，求丢失的那个数。
记得在评论区留下你的答案哦 ~
5、简单加密
基于 两个数异或为零，任何数和零异或为其本身 这两个特点，异或还可以用来做简单的加密。将明文异或上一个固定的数变成密文以后，可以通过继续异或上这个数，再将密文转变成明文。
七、按位取反运算符
取反运算符是一个单目位运算符，也就是只有一个操作数，表示为 ~x。取反运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况。
int main() { int a = 0b1; printf("%d\n", ~a ); return 0; }
这里 ~a 代表的是对二进制数 1 进行取反，直观感受应该是 0。但是实际输出的却是：
-2
这是为什么呢？那是因为，这是一个 32 位整数，实际的取反操作是这样的：00000000 00000000 00000000 00000001
11111111 11111111 11111111 11111110
32位整数的二进制表示，前导零也要参与取反。而对于一个有符号的 32 位整数，我们需要用最高位来代表符号位，即最高位为 0，则代表正数；最高位为 1，则代表负数；
这时候我们就需要引入补码的概念了。
1、补码的概念
在计算机中，二进制编码是采用补码的形式表示的，补码定义如下：
正数的补码是它本身，符号位为 0；负数的补码为正数数值二进制位取反后加一，符号位为一；
2、补码举例
根据补码的定义，-2的补码计算，需要经过两步：
1）对 2 的二进制进行按位取反，如下：00000000 00000000 00000000 00000010
11111111 11111111 11111111 11111101
2）然后加上 1，如下：
11111111 11111111 11111111 11111101
- 00000000 00000000 00000000 00000001
11111111 11111111 11111111 11111110
结果正好为我们开始提到的 ~1 的结果。
3、补码的真实含义
补码的真实含义，其实体现在 “补” 这个字上，在数学上，两个互为相反数的数字相加等于 0，而在计算机中，两个互为相反数的数字相加等于 2 的 n 次。
换言之，互为相反数的两个数互补，补成 2 的 n 次。
对于 32位整型，n = 32；对于 64 位整型，n = 64。所以补码也可以表示成如下形式：
于是，对于 int 类型，就有：
即：
于是，我们开始数数……
2^32 = 1 00000000 00000000 00000000 00000000
2^32 - 1 = 11111111 11111111 11111111 11111111
2^32 - 2 = 11111111 11111111 11111111 11111110
近一步了解了 -2 的二进制表示。
位运算修行手册（一）+https://developer.aliyun.com/article/1389769
