在C/C++中，有比较丰富的位运算操作符，常见的有：

&：按位与 |：按位或 ~：按位取反 ^：按位异或 ：右移操作符

这些操作符的用法就不详细讲解了，本博客主要围绕算法来讲解。

先概述一下位运算中常会用到的操作与算法。

给一个数n，求它二进制的第x位是0还是1

只需要将n右移x位，然后与1按位与即可，也就是：

如果结果是1，那么第x位就是1，反之为0。

给一个数n，将它二进制的第x位修改为1

如果要把第x位修改为1

对于x以外的位，不能被影响，它们要与0进行按位或。

而对于第x位，想要变成1，就与1按位或

也就是说我们现在要得到x位为1，其他位为0的数据，也就是1 int count = 0; for (int i = 0; i public: int hammingWeight(int n) { int count = 0; while (n) { n &= n - 1; count++; } return count; } };

这种写法，每一次都固定消除一位1，提高了效率。另外地，任何长度的整型都可以用这个方法来计算。

LeetCode 338. 比特位计数

本题要求出一个[0, n]所有值的1的个数，并返回一个数组。

对于这道题，可以用暴力的解法，直接遍历数组，每一个数字都单独求一次1的个数。

但是由于数字是连续的，其实我们可以通过前面的值来简化求后面值的操作。

比如说00010010，由于最后一位是0，其+1后，下一位数字00010011刚好比其多一位1。

也就是说：一个奇数的二进制的1的个数，比前面那个数（一定是偶数）的二进制的1的个数多一个。

由于奇数的最后一位一定是1，那么奇数+1一定会发生进位，进位的时候会有1会被消除，而被消除的1的数目是不确定的，因此一个偶数的二进制1的个数，与前面那个数的二进制1的个数，没有必然联系。

但是一个数字×2，其二进制的表现为：所有位整体左移一位。比如00110011乘以二，得到01100110，这个过程只发生移位，1的个数不会改变。而一个偶数一定是2的倍数，所以一个偶数n的二进制的1的个数，等于n/2的二进制的1的个数。

代码逻辑如下：

代码如下：

LeetCode 371. 两整数之和

本题要求不用+和-完成两数的加法。想要解决这道题，那就要再理解一下按位异或的其他含义了。

按位异或基本规则为：相同为0，相异为1，从数学角度也可以理解为不进位加法。

比如00110011与01010101进行异或：

两个数的最低位都是1，如果执行加法，那么1 + 1 = 2会导致进位，本位余0，向上进1 。但是按位异或 只余0，不进1。

两数的第二位，分别是0和1，如果执行加法，0 + 1 = 1，本位余1，不进位。按位异或也可以理解为只余1，不进位。

因此，按位异或可以理解为一个不进位的加法。

那么现在给我们两个数a和b，我们要用位运算来模拟加法，现在我们可以通过按位异或执行一个不进位的加法。那么进位应该怎么办呢？

如果在二进制计算中发生了进位，那么两个位一定都是1，进位也就是把多出来的1加到高位去。因此我们可以通过按位与a & b，得到两个位都为1的位，也就是需要进位的位。然后将其左移一位(a & b) while (b) { int tmp = a ^ b; // 不进位加法 int carry = (a & b) int ret = 0; for (auto& e : nums) // 遍历数组 ret ^= e; return ret; } };

LeetCode 260. 只出现一次的数字 III

本题中有两个数字只出现了一次，其他数字都出现了两次。

与之前思路一样，假设我们要求的目标值为a和b，把所有值都异或起来，结果就是a ^ b。

那么问题就来了，我们要如何从a ^ b中拆分出a和b呢？

按位异或的规则为：相同为0，相异为1，也就是说a ^ b中为1的地方，就是a与b不同的位，我们可以通过这个位来区分两者。

假设我们求出了，a ^ b的第x位为1，那么整个数组的数据就可以拆分为两份：第x位为1，第x位为0。而a和b就分别在这两份中。假设a在第一份元素中，b在第二份元素中。

第x位为1：a + 其它第x位为1 第x位为0：b + 其它第x位为0

因为除了a和b，其他数字都出现两次，相同的数字第x位也相同，会被分到同一份中。

因此第一份数据中，除了a以外，其他数字都出现两次；第二份数据中，除了b以外，其他数字也出现两次。

我们将第一份数据中所有元素异或起来，得到的就是a，第二份数据中的所有元素异或起来，得到的就是b。

逻辑：

代码：

这里我额外说明一句代码：

其目的在于，得到a ^ b中的最右侧的一位1，也就是tmp & -tmp，并赋值给x。但是如果tmp的值是int类型的最小值，其二进制就是：

也就是，除了第一位，其它位都是0，此时-tmp是超过了int的存储范围的，会发生进位。

其取反，+1后为：

可以看出来发生了越界。

而我们的目的只是为了提取tmp最右侧的一个1，如果tmp是INT_MIN，本身就只有一个1，因此不用额外提取，直接x = tmp即可。

LeetCode 137. 只出现一次的数字 II

本题中，目标元素出现一次，其它元素出现三次，都是奇数次，那么我们就不能用异或来区分它们了。

这种情况下，就要用位图的思想，来单独统计每一个位的情况。

因为输入的数据是int类型，那么就固定只有32个位，对于每个位，我们都单独统计。

创建一个32个元素的整型数组bitmap，每个元素代表一个比特位。

遍历数组，对于每个元素，将其所有位的值加进bitmap中。

比如某个元素第0位是1，那么bitmap[0] += 1，第1位为0，那么bitmapp[1] += 0，以此类推，直到第31位。每个元素都执行一次该操作。

最后bitmap数组中，就统计到了对应位上出现的1个数。由于其它元素都出现了三次，对于每一位数据，都是3的倍数 + 目标值在该位的值0/1

那么bitmap[i] % 3就可以还原出目标元素第i位是0还是1。

代码逻辑：

代码：

给一个数n，将它二进制的第x位修改为1