位运算符
位运算符在系统编程、嵌入式系统、加密程序、图形处理等需要底层数据控制和快速运算的领域中非常有用。在这些领域当中使用位运算符往往可以达到简化代码以及提升性能的作用。
但是在偏向业务逻辑开发的应用级领域则不太需要使用位运算符，因为可读性和代码可维护性的重要性往往大于微小的性能提升。总得来说，在以后的学习工作中，位运算符不算是一个频繁使用的语法点，但考虑到面试常考常问，我们仍然把位运算符当成学习的重点看待。
6个位运算符
2个移位运算符
- 左移运算符
<< - 右移运算符
>>
4个按位运算符
- 按位取反
~ - 按位与
& - 按位异或
^ - 按位或
|
首先，我们讨论两个移位运算符(因为它们最常用)，然后再讨论其他四个按位运算符。
为了更好的描述位运算符，这里给出一个概念定义：
：某个变量的位模式，指的是该变量在计算机中的二进制存储形式。对于整数变量来说，位模式也就是该整数在内存中的补码形式。
移位运算符
移位运算符可以通过将位向左或向右移动来变换整数的二进制表示。C 语言提供了左移运算符 << 和右移运算符 >> 。
i << j：将 i 的位左移 j 位，在 i 的右边补 0。i >> j：将 i 的位右移 j 位。如果 i 是无符号数或者非负值，则在左边补 0。如果 i 是负值，其结果是由实现定义的：一些实现会在左边补 0，一些实现会在左边补 1。
注意
为了可移植性，最好仅对无符号数进行移位运算。
举个例子：
unsigned short i, j;
i = 10; // 0000 0000 0000 1010
j = i << 2; // 0000 0000 0010 1000 十进制40
j = i >> 2; // 0000 0000 0000 0010 十进制2从上面的例子可以看出，对无符号整数左移 j 位，相当于乘以 2j (不发生溢出)；对无符号整数右移 j 位，相当于除以 2j。
右移的使用细节
编程语言中的右移位运算符(不仅仅C语言)，通常有两种行为表现：
- 算术右移：算术右移会在高位插入符号位的副本（对于负数是1，正数是0），算术右移位运算通常用于有符号数，因为它可以保持整数的符号不变。
- 对一个负数进行算术右移会在高位补1。
- 对一个正数进行算术右移会在高位补0。
- 逻辑右移：逻辑右移不考虑整数的符号，总是在高位补0。
当然，在大多数现代编译器和平台上（比如MSVC/GCC/Clang等），右移位运算符都是算术右移的，也就是在现代编译平台上，右移位运算符不会改变有符号数的符号。
综上所述，关于右移位运算符的使用我们提出以下建议：
- 为了更好的平台移植性和安全性，可以直接对无符号数做右移位运算，这样就不会出现符号问题了。
- 如果要对有符号数做移位运算，请自行确认编译器行为，避免跨平台时出现移位符号问题。
扩展
由于C语言在右移位运算上的灵活性，可能会导致一些"编码陷阱"，所以C以后的高级编程语言一般都会对右移位运算符做更多的限制和规定。比如：
- Java会直接提供两个右移位运算符：算术右移（
>>）和逻辑右移（>>>） - Python直接禁用了逻辑右移，总是执行算术右移。
按位运算符
按位位运算符包含：按位取反~，按位与&，按位异或^，按位或|。其中按位取反是一元运算符，其余都是二元运算符。
对于以下表达式：
~a：对a进行按位取反运算。也就是将 a 的每一位进行取反操作。即 0 变成 1，1 变成 0。i & j：对 i 和 j 的每一位进行逻辑与运算。只有两个数的相应位都为1时，结果位才为1，否则为0。i | j：对 i 和 j 的每一位进行逻辑或运算。只要两个数的相应位中有一个为1，结果位就为1，否则为0。i ^ j：对 i 和 j 的每一位进行异或运算。如果两个数的相应位一个为0，另一个为1，则结果位为1，否则为0。(对应位不同结果就是1)
注意
- 这些表达式的主要作为是返回位运算后得到的结果，没有副作用，不会改变任何一个操作数的值！！
- 在C语言中，
&、|不是逻辑运算符，而是位运算符，不要搞混淆了。
特别注意
千万不要将按位运算符 & 和 | 与逻辑运算符 && 和 || 混淆。
下面的例子演示了这些运算符的作用：
unsigned short i, j, k;
i = 21; /* 0000_0000_0001_0101 */
j = 56; /* 0000_0000_0011_1000 */
k = ~i; /* 1111_1111_1110_1010 */
k = i & j; /* 0000_0000_0001_0000 */ // 16
k = i | j; /* 0000_0000_0011_1101 */ // 61
k = i ^ j; /* 0000_0000_0010_1101 */ // 45除了按位取反运算符外，其余位运算符都有对应的复合赋值运算符：
i = 21;
j = 56;
i <<= 2;
i >>= 2;
i &= j;
i |= j;
i ^= j;其中按位异或运算有一些良好的性质 (请确认自己是否真的理解了这些性质?)：
a ^ 0 = a;
a ^ a = 0;
a ^ b = b ^ a;
(a ^ b) ^ c = a ^ (b ^ c);这些性质使得异或运算符在实际的应用中用途广泛，下面给大家讲解一些位运算相关的面试题。
常见面试题
判断奇偶性
题目 定义一个函数，判断某个整数是否为奇数。
这个函数在以前大家就都会写了，如下
bool is_odd(int num) {
// 整数num取余不为0就是一个奇数
return num % 2 != 0;
}但如果需求更好的运算效率，可以考虑用位运算符来进行奇数的判断。
用位运算符来进行奇数的判断的原理是
一个整数的位模式表示，如果它是偶数那么它二进制位的最后一个位必然是0，反之如果它是奇数最后一位必然是1。
为什么呢？
因为二进制的每一位代表的是2的幂次方，从右向左分别是 20, 21, 22, ...等等。
这些组成中，只有最低位的20不是2的整数倍，所以只要最低位是0，那么这个整数就一定是偶数。(因为更高位都是2的倍数，偶数加偶数必然还是偶数)
基于以上原理，我们就可以写出以下用位运算判断奇数的代码：
bool is_odd(int num) {
/*
* 让num按位与...0001
* 如果num是奇数，则num位模式的最后一位是1，于是相与的结果就是1，也就是true，表示num是一个奇数
* 如果num是偶数，则num位模式的最后一位是0，于是相与的结果就是0，也就是false，表示num是一个偶数
*/
return num & 1;
}这样的代码显然可读性不好，但很简洁优雅，且效率也会稍微高一点。
判断是否为2的正整数幂
题目 给定一个正整数，请定义一个函数判断它是否为2的正整数幂。例如：1, 2, 4, 8, 16, ....就是2的正整数幂。
一个非常简单易想、易实现的方式就是
只要num大于1且能被2整除，就一直将它除以2，判断最终得到的结果是不是1，若是1，则num是2的幂。
参考代码如下：
bool is_power_2(int n) {
// 只要这个数大于1且能被2整除，那就一直除以2
while (n > 1 && n % 2 == 0) {
n /= 2;
}
// 判断最终结果是不是1
return n == 1;
}这个解法可以用位运算符优化一下
可以逆向思维一下： 使用一个变量x并将初始值设为1，只要x还小于目标整数，就一直左移它（左移1位乘以2），最终得到的x如果和目标整数相同，那么目标整数就是2的正整数幂。
参考代码如下：
bool is_power_2(int n) {
int x = 1;
// 只要x比n小就左移1位，乘以2
while (x < n){
x <<= 1;
} // 结束while的条件是x >= n
// 如果n是2的幂，那么x和n相等
return n == x;
}但这些解法都还不是最优的，下面我们先观察一下2的幂整数的位模式：
1：0001
2：0010
4：0100
8：1000
....很显然一个正整数，如果它是2的幂，那么它的二进制位表示中仅有一位是1，其余位都是0。
利用这个性质，我们将该整数和该整数减1做按位与运算，结果是0就说明该整数是2的幂。如下：
4 (0100) & 3 (0011) = 0
8 (1000) & 7 (0111) = 0具体实现的参考代码如下：
bool is_power_2(int n) {
return (n & (n - 1)) == 0;
}这个实现代码更简洁，效率更高。
求LSB
题目 给定一个不为0的整数，编写函数找出它值为1的最低有效位 (称之为Last Set Bit)。比如：LSB的结果是1表示此整数的最低位就是1, 2则表示倒数第二位是第一个1, 4表示倒数第三位是第一个1....
一个示例如下
输入：n = 24
输出：8
解释：24的二进制表示为 11000，值为 1 的最低有效位是倒数第四位，则输出 2^3，那么lsb就是8。
理解LSB的意思后，那么如何实现求LSB呢？
一个仍然比较易想易实现的思路是
将num与1、2、4、8...等整数逐一做按位与运算，当结果不为0时，num的LSB就是这个整数值。
举例：
8：二进制表示为1000 LSB是8
8 & 1 = 1000 & 0001 = 0
8 & 2 = 1000 & 0010 = 0
...
8 & 8 = 1000 & 1000 != 0于是LSB就是8，整数8值为1的最低有效位就是
参考代码如下：
int find_last_set_bit(int n) {
int x = 1;
while ((n & x) == 0) {
x <<= 1;
}
return x;
}这种实现实际上已经很不错了，效率已经不错了，代码也很简洁，但它还不是最优解。
要想搞清楚最优解的思路，我们再来复习一个前面课程提到过的问题：给出一个整数的补码，请求它相反数的补码。
例如
x 的补码形式：0101 1100
-x 的补码形式，可以利用补码的一个性质来直接求解：
x + (-x) = 1, 000...02进制补码(其中0一共有n个，高位的1溢出被舍掉) = 0
于是我们可以找到x的二进制补码中，值为1的最低有效位(也就是last set bit)，那么它的相反数的补码就是：
- last set bit位保持不变
- 从last set bit的高一位开始，所有高位取反
于是 -x 的补码就是：1010 0100
通过这个案例，我们就发现：x 和 -x 的位模式，last set bit是一致的，高于last set bit的位全部相反，低于last set bit的位全部是0。
所以只需要将 x 和 -x 进行按位与操作，就可以找到last set bit了。
参考代码如下：
int find_last_set_bit(int n) {
return n & (-n);
}这个实现就非常简洁优雅以及高效了！
交换两个元素
题目 给定两个不同的整数 a 和 b，请交换它们两个的值。(这里不要定义函数)
这个题目，也就是交换两个元素，相信大家都会以下解法
int a = 100, b = 200;
int tmp = a;
a = b;
b = tmp;这种方式要求大家必须掌握，因为它具有以下优点：
- 代码可读性很强，任何程序员一眼都能看明白。
- 不限制被交换元素的类型，可以交换任何类型的两个元素。
当然它的缺点是：需要一个临时变量tmp，这可能会导致额外的内存空间占用。
所以在早期，出于节省内存空间，简化代码的考量，出现了下面利用异或位运算符交换两个元素的编程技巧 (惯用法)
int a = 100, b = 200;
a = a ^ b;
b = a ^ b;
a = a ^ b;这种写法之所以能够完成两个数的交换，利用的是异或运算符^的性质。计算过程分析如下：
我们将原始的a 和 b的值记为a0，b0
第一个表达式执行后的a和b的值，记为a1和b1
...
于是整个计算过程为：
- 第一个表达式执行完毕后：a1 = a0 ^ b0，b1 = b0
- 第二个表达式执行完毕后：
- b2 = a1 ^ b1 = a0 ^ b0 ^ b1 = a0 ^ b0 ^ b0 = a0 ^ (b0 ^ b0) = a0 ^ 0 = a0。于是第二个表达式执行完毕后，b的结果就等于原始a了。
- a2 = a1 = a0 ^ b0
- 第三个表达式执行完毕后：
- a3 = a2 ^ b2 = a0 ^ b0 ^ a0 = (a0 ^ a0) ^ b0 = 0 ^ b0 = b0。于是第三个表达式执行完毕后，a的结果就等于原始b了。
- b3不变，b的值仍然等于原始a的值。
以上，三个表达式执行完毕后，a和b在不利用额外空间的前提下就完成了交换，nice！
这种使用位运算符交换元素的方式有什么优缺点呢？
优点是：
- 逼格十足，这就是最大优点！
- 没有使用第三者元素，减少了内存占用。（但实际上占用额外局部变量并没有太大影响）
缺点是：
- 可读性不好，不懂位运算符的人看不懂。
- 只能用于交换整数类型元素，因为位运算符只能计算整数！
最后我们做一个总结，交换元素是程序中特别常见和重要的操作，在大多数情况下：
我们还是建议大家用临时变量的形式交换元素。因为它可读性更好，且不受元素类型限制，并且效率几乎没有差异。只是占用了一些微不足道的额外空间罢了。
而且用^交换元素还可能导致交换两个相同元素导致结果为0的情况出现，这也为程序带来了极大的风险。
找出数组中出现一次的元素
题目 给定一个非空的整数数组nums，已知某个元素只出现了一次，其余元素均出现两次，那么请你找出这个只出现一次的元素。
怎么做呢？
使用异或运算即可，因为异或运算有以下性质：
- 自己和自己异或为0，0和别人异或都是别人。
- 异或运算还满足交换律和结合律。
于是只需要将数组中的所有元素，全部用^运算符链接起来，这样最终的结果就是那个唯一的元素。
例如：
// 数组nums：
[1, 4, 2, 1, 2]
// 将所有元素都^链接起来
1 ^ 4 ^ 2 ^ 1 ^ 2 = (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4于是4就是数组中仅存在一个的元素。
参考代码如下：
int nums[] = { 1, 4, 2 ,1, 2 };
/*
* result就是最终找出的出现一次的元素
* 对于异或运算来说，0异或其它值都是其它值本身
* 所以result的初始值设置为0
*/
int result = 0;
// 遍历将数组中的所有元素都链接起来
for (int i = 0; i < 5; i++){
result ^= nums[i];
}
printf("数组中的唯一元素就是 %d.\n", result);找出数组中出现一次的元素
题目 给定一个非空的整数数组nums，已知某两个元素只出现了一次，其余元素均出现两次，那么请你找出这两个只出现一次的元素。
怎么做呢？
其实我们可以利用上一题的解题思路，将数组中的所有元素都异或起来，得到的结果就是那两个只出现一次的元素的异或结果。假设这两个元素分别是a和b，那么最终的结果就是：a ^ b。但我们现在的问题是，如何将这两个元素从a ^ b中分离出来呢？
我们可以考虑以下思路：
- 因为a和b是两个不同的元素，所以它们的异或结果一定不为0。
- 我们可以找到a和b的异或结果的二进制表示中，值为1的最低有效位(也就是last set bit)，记为
lsb。 - 我们可以将数组中的元素分为两类：
- 一类是lsb位为1的元素，记为
a - 一类是lsb位为0的元素，记为
b
- 一类是lsb位为1的元素，记为
- 我们可以将
a和b分别与原数组中的元素异或起来，得到的结果就是a和b。
具体实现的参考代码如下：
#include <stdio.h>
int main(void) {
int nums[] = { 1, 2, 3, 2, 5, 1 };
int xor = 0; // 记录两个不重复值异或的结果
int len = sizeof nums / sizeof nums[0];
for (int i = 0; i < len; ++i) {
xor ^= nums[i];
}
// 记录两个不重复值异或时相同位数值不同的那一个最小有效位
int lsb = xor & -xor;
// 分类求两个值
int a = 0, b = 0;
for(int i = 0; i < len; ++i){
if(nums[i] & lsb){
a ^= nums[i];
}else{
b ^= nums[i];
}
}
printf("a=%d, b=%d\n", a, b);
return 0;
}