位运算(C/C++)

1. 基础知识

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True）。

在一个二进制数中，最右边的位称为第 0 位，从右往左一次递增。

 

2. 位运算的常见运用

2.1 求一个数N的二进制表示中第k位是几？

解题步骤：1：把二进制数的第 k 位移动到第 0 位，即：N >> k。

                  2：将移动后的结果 & 1，得到的数即是最的结果。

例如：一个整数10，求它的二进制表示中第三位是几？10 的二进制表示为：1010，向右移动 3 位：0001。0001 & 1 = 1，故 10 的第三位是 1。

2.2 一个数N的二进制中最右侧的1

例如：一个数的二进制表示为：10101000，则将最右侧的 1 连同后面的 0 一起，输出该二进制串表示的数字，即：1000 表示的数字 8。

解题方法：将该数去进行一个 lowbit 操作就行。lowbit(x) : x & (-x)。

下面以整数 int N = 40 来举例分析。我们可以先求出结果：40 的二进制表示为：101000，最终结果就是1000 表示的数字 8 。

 

剑指 Offer 15. 二进制中1的个数 - 力扣（LeetCode）

题目描述：编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。

有了上面 lowbit(N) 的思路，相比之前的讲解又可以得到一种新的解法了。

http://t.csdn.cn/oIMpdhttp://t.csdn.cn/oIMpd解题思路：我们将 n 进行 lowbit 操作，然后让 n 减去 lowbit 的结果，直到 n 为0，统计减去的次数即为结果。

uint32_t lowbit(uint32_t x)
{return x & -x;
}int hammingWeight(uint32_t n) {int count = 0;while(n){n -= lowbit(n);count++;}return count;
}

 2.3 交换两个数

有道笔试题是这样的：给你两个数 A，B，在不使用第三个变量的前提下交换 A，B。

这道题可以用 加法的方式求解。我们这里讲解位运算的方式哈。代码如下：

int main()
{int A = 1, B = 0;A = A ^ B;B = A ^ B;A = A ^ B;printf("A: %d B: %d", A, B);return 0;
}

 关于这个就是：B ^ B = 0。A ^ B ^ B = A ^ 0 = A。只需要把握住这一点就行了。

原题链接：

面试题 17.04. 消失的数字 - 力扣（LeetCode）

题目描述：数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

将缺少一个元素的数组全部异或，结果在与不缺少的数组异或，其中相等的数字会被异或掉，剩下的就是缺失的数字(两次异或中只有一个的数字)。注意：异或是支持交换律和结合律的。

例如：缺失的数组为：0 1 3，那么缺失的数字就是：0 ^ 1 ^ 3 ^ 0 ^ 1 ^ 2 ^ 3 = 2。将缺失的数组与完整的数组异或。

int missingNumber(int* nums, int numsSize){int r = 0;for(int i = 0; i< numsSize;i++){r^=nums[i];}for(int i = 0; i <= numsSize;i++){r^=i;}return r;
}