位运算修行手册（一）+https://developer.aliyun.com/article/1389768
八、按位取反运算符的应用
1、0 的取反
【例题1】0 的取反结果为多少呢？
首先对原码进行取反，得到：00000000 00000000 00000000 00000000
11111111 11111111 11111111 11111111
这个问题，我们刚讨论完，这个答案为 2^32 - 1。但是实际输出时，你会发现，它的值是 -1 。
这是为什么？
原因是因为在C语言中有两种类型的 int ，分别为 unsigned int 和 signed int ，我们之前讨论的 int 都是 signed int 的简称。
1）有符号整型
对于有符号整型 signed int 而言，最高位表示符号位，所以只有 31 位能表示数值，能够表示的数值范围是：
所以，对于有符号整型，输出采用 %d ，如下：
int main() { printf("%d\n", ~0 ); return 0; }
结果为：
-1
2）无符号整型
对于无符号整型 unsigned int 而言，由于不需要符号位，所以总共有32位表示数值，数值范围为：
对于无符号整型，输出采用 %u ，如下：
int main() { printf("%u\n", ~0 ); return 0; }
结果为：
4294967295
即 2^ 32 - 1 。
2、相反数
【例题2】给定一个 int 类型的正数 x ，求 x 的相反数（注意：不能用负号）。
这里，我们可以直接利用补码的定义，对于正数 x ，它的相反数的补码就是 x 二进制取反加一。即： ~x + 1 。
int main() { int x = 18; printf("%d\n", ~x + 1 ); return 0; }
运行结果如下：
-18
3、代替减法
【例题3】给定两个 int 类型的正数 x 和 y，实现 x - y（注意：不能用减号）。
这个问题比较简单，如果上面的相反数已经理解了，那么， x - y 其实就可以表示成 x + (-y) ，而 -y 又可以表示成 ~y + 1 ，所以减法 x - y 就可以用 x + ~y + 1 来代替。
- 代码实现如下：
int main() { int a = 8; int b = 17; printf("%d\n", a + ~b + 1 ); return 0; }
运行结果为：
-9
4、代替加法
【例题4】给定两个 int 类型的正数 x 和 y ，实现 x + y （注意：不能用加号）。
我们可以把 x + y 变成 x - (-y) ，而 -y 又可以替换成 ~y + 1 ；
所以 x + y 就变成了 x - ~y - 1 ，不用加号实现了加法运算。
int main() { int x = 18; int y = 7; printf("%d\n", x - ~y - 1 ); return 0; }
运行结果为：
25
九、左移运算符
1、左移的二进制形态
左移运算符是一个二元的位运算符，也就是有两个操作数，表示为 x << y 。其中 x 和 y 均为整数。
x << y 念作：“将 x 左移 y 位”，这里的位当然就是二进制位了，那么它表示的意思也就是：先将 x 用二进制表示，然后再左移 y 位，并且在尾部添上 y 个零。
举个例子：对于二进制数 (10111) 左移 y 位的结果就是：
2、左移的执行结果
x << y 的执行结果等价于：
如下代码：
int main() { int x = 3; int y = 5; printf("%d\n", x << y); return 0; }
输出结果为：
正好符合这个左移运算符的实际含义：
最常用的就是当 x = 1 时，1 << y 代表的就是 2^y，即 2 的幂。
3、负数左移的执行结果
所谓负数左移，就是 x << y 中，当 x 为负数的情况，代码如下：
int main() { printf("%d\n", -1 << 1); return 0; }
它的输出如下：
我们发现同样是满足的，这个可以用补码来解释，-1的补码为：
左移一位后，最高位的 1 就没了，低位补上 0，得到：
而这，正好是 -2 的补码，同样，继续左移 1 位，得到：
这是 -4 的补码，以此类推，所以负整数的左移结果同样也是满足的。
可以理解成 - (x << y) 和 (-x) << y 是等价的。
4、左移负数位是什么情况
刚才我们讨论了 x < 0 的情况，那么接下来，我们试下 y < 0 的情况会是如何？
是否同样满足如下等式呢？
如果还是满足，那么两个整数的左移就有可能产生小数了。
看个例子：
int main() { printf("%d\n", 32 << -1); printf("%d\n", 32 << -2); printf("%d\n", 32 << -3); printf("%d\n", 32 << -4); printf("%d\n", 32 << -5); printf("%d\n", 32 << -6); printf("%d\n", 32 << -7); return 0; }
虽然能够正常运行，但是结果好像不是我们期望的，而且会报警告如下：
[Warning] left shift count is negative [-Wshift-count-negative]
实际上，编辑器告诉我们尽量不用左移的时候用负数，但是它的执行结果不能算错误，起码例子里面对了，结果不会出现小数，而是取整了。
左移负数位其实效果和右移对应正数数值位一致。
5、左移时溢出会如何
我们知道， int 类型的数都是 32 位的，最高位代表符号位，那么假设最高位为 1，次高位为 0，左移以后，符号位会变成 0，会产生什么问题呢？
举个例子，对于 -2^31 + 1 的二进制表示为：最高位和最低位为 1，其余为零。
int main() { int x = 0b10000000000000000000000000000001; printf("%d\n", x); return 0; }
输出结果为：
那么，将它进行左移一位以后，得到的结果是什么呢？
int main() { int x = 0b10000000000000000000000000000001; printf("%d\n", x << 1); return 0; }
我们盲猜一下，最高位的 1 被移出去，最低位补上 0，结果应该是 0b10 。
实际输出的结果，的确是：
但是如果按照之前的规则，答案应该是：
这里又回到了补码的问题上，事实上，在计算机中， int 整型其实是一个环，溢出以后又会回来，而环的长度正好是 2^32，所以 -2^32 + 2 = 2，这个就有点像同余的概念，这两个数是模 2^32 同余的。
十、左移运算符的应用
1、取模转化成位运算
对于 x 模上一个 2 的次幂的数 y，我们可以转换成位与上 2^y-1。
即在数学上的：
在计算机中就可以用一行代码表示：x & ((1 << y) - 1)。
2、生成标记码
我们可以用左移运算符来实现标记码，即 1 << k 作为第 k 个标记位的标记码，这样就可以通过一句话，实现对标记位置 0、置 1、取反等操作。
1）标记位置1
【例题1】对于 x 这个数，我们希望对它二进制位的第 k 位（从0开始，从低到高数）置为 1。
置 1 操作，让我们联想到了 位或 运算。
它的特点是：位或上 1，结果为 1；位或上0，结果不变。
所以我们对标记码的要求是：第 k 位为 1，其它位为 0，正好是 (1 << k) ，那么将 第 k 位 置为 1 的语句可以写成：x | (1 << k)。
2）标记位置0
【例题2】对于 x 这个数，我们希望对它二进制位的第 k 位（从0开始，从低到高数）置为 0。
置 0 操作，让我们联想到了 位与 运算。
它的特点是：位与上 0，结果为 0；位与上 1，结果不变。
所以在我们对标记码的要求是：第 k 位为 0，其它位为 1，我们需要的是 (~(1 << k))，那么将 第 k 位 置为 0 的语句可以写成：x & (~(1 << k))。
3）标记位取反
【例题3】对于 x 这个数，我们希望对它二进制位的第 k 位（从0开始，从低到高数）取反。
取反操作，联想到的是 异或 运算。
它的特点是：异或上 1，结果取反；异或上 0，结果不变。
所以我们对标记码的要求是：第 k 位为1，其余位为 0，其值为 (1 << k) 。那么将 第 k 位 取反的语句可以写成： x ^ (1 << k) 。
3、生成掩码
同样，我们可以用左移来生成一个掩码，完成对某个数的二进制末 k 位执行一些操作。
对于 (1 << k) 的二进制表示为：1 加上 k 个 0，那么 (1 << k) - 1 的二进制则代表 k 个 1。
把末尾的 k 位都变成 1，可以写成：x | ((1 << k) - 1)。
把末尾的 k 为都变成 0，可以写成：x & ~((1 << k) - 1)。
把末尾的 k 位都取反，可以写成：x ^ ((1 << k) - 1)。
十一、右移运算符
1、右移的二进制形态
右移运算符是一个二元的位运算符，也就是有两个操作数，表示为 x >> y。其中 x 和 y 均为整数。
x >> y 念作：“将 x 右移 y 位”，这里的位当然就是二进制位了，那么它表示的意思也就是：先将 x 用二进制表示，对于正数，右移 y 位；对于负数，右移 y 位后高位都补上 1。
举个例子：对于十进制数 87，它的二进制是 (1010111)， 左移 y 位的结果就是：
2、右移的执行结果
x >> y 的执行结果等价于：
这个符号代表取下整。如下代码：
int main() { int x = 0b1010111; int y = 3; printf("%d\n", x >> y); return 0; }
输出结果为：
正好符合这个右移运算符的实际含义：
由于除法可能造成不能整除，所以才会有 取下整 这一步运算。
3、负数右移的执行结果
所谓负数右移，就是 x >> y 中，当 x 为负数的情况，代码如下：
int main() { printf("%d\n", -1 >> 1); return 0; }
它的输出如下：
我们发现同样是满足如下式子的
这个可以用补码来解释，-1 的补码为：
右移一位后，由于是负数，高位补上 1，得到：
可以理解成 - (x >> y）和 (-x) >> y 是等价的。
然后我们来简单做道题巩固一下
【例题1】要求不运行代码，肉眼看出这段代码输出多少。
int main() { int x = (1 << 31) | (1 << 30) | 1; int y = (1 << 31) | (1 << 30) | (1 << 29); printf("%d\n", (x >> 1) / y); return 0; }
4、右移负数位是什么情况
刚才我们讨论了 x < 0 的情况，那么接下来，我们试下 y < 0 的情况会是如何？是否同样满足如下性质呢？
如果还是满足，那么两个整数的左移就有可能产生小数了。
看个例子：
int main() { printf("%d\n", 1 >> -1); printf("%d\n", 1 >> -2); printf("%d\n", 1 >> -3); printf("%d\n", 1 >> -4); printf("%d\n", 1 >> -5); printf("%d\n", 1 >> -6); printf("%d\n", 1 >> -7); return 0; }
虽然能够正常运行，但是结果好像不是我们期望的，而且会报警告如下：
[Warning] right shift count is negative [-Wshift-count-negative]
实际上，编辑器告诉我们尽量不用右移的时候用负数，但是它的执行结果不能算错误，起码例子里面对了。
右移负数位其实效果和左移对应正数数值位一致。
十二、右移运算符的应用
1、去掉低 k 位
【例题2】给定一个数 x，去掉它的低 k 位以后进行输出。
这个问题，可以直接通过右移来完成，如下：x >> k。
2、取低位连续 1
【例题3】获取一个数 x 低位连续的 1 并且输出。
对于一个数 x，假设低位有连续 k 个 1。如下：
然后我们将它加上 1 以后，得到的就是：
这时候将这两个数异或结果为：
这时候，再进行右移一位，就得到了 连续 k 个 1 的值，也正是我们所求。
所以可以用以下语句来求：(x ^ (x + 1)) >> 1。
3、取第k位的值
【例题4】获取一个数 x 的第 k(0 <= k <= 30) 位的值并且输出。
对于二进制数来说，第 k 位的值一定是 0 或者 1。
而 对于 1 到 k-1 位的数字，对于我们来说是没有意义的，我们可以用右移来去掉，再用位与运算符来获取二进制的最后一位是 0 还是 1，如下：(x >> k) & 1。
那么接下来，我们试下 y < 0 的情况会是如何？是否同样满足如下性质呢？
[外链图片转存中…(img-3wbr0PBV-1690102819771)]
如果还是满足，那么两个整数的左移就有可能产生小数了。
看个例子：
int main() { printf("%d\n", 1 >> -1); printf("%d\n", 1 >> -2); printf("%d\n", 1 >> -3); printf("%d\n", 1 >> -4); printf("%d\n", 1 >> -5); printf("%d\n", 1 >> -6); printf("%d\n", 1 >> -7); return 0; }
虽然能够正常运行，但是结果好像不是我们期望的，而且会报警告如下：
[Warning] right shift count is negative [-Wshift-count-negative]
实际上，编辑器告诉我们尽量不用右移的时候用负数，但是它的执行结果不能算错误，起码例子里面对了。
右移负数位其实效果和左移对应正数数值位一致。
十二、右移运算符的应用
1、去掉低 k 位
【例题2】给定一个数 x，去掉它的低 k 位以后进行输出。
这个问题，可以直接通过右移来完成，如下：x >> k。
2、取低位连续 1
【例题3】获取一个数 x 低位连续的 1 并且输出。
对于一个数 x，假设低位有连续 k 个 1。如下：
[外链图片转存中…(img-d1hKcnX3-1690102819771)]
然后我们将它加上 1 以后，得到的就是：
[外链图片转存中…(img-5VGxiKFY-1690102819772)]
这时候将这两个数异或结果为：
[外链图片转存中…(img-4z96Jhpo-1690102819772)]
这时候，再进行右移一位，就得到了 连续 k 个 1 的值，也正是我们所求。
所以可以用以下语句来求：(x ^ (x + 1)) >> 1。
3、取第k位的值
【例题4】获取一个数 x 的第 k(0 <= k <= 30) 位的值并且输出。
对于二进制数来说，第 k 位的值一定是 0 或者 1。
而 对于 1 到 k-1 位的数字，对于我们来说是没有意义的，我们可以用右移来去掉，再用位与运算符来获取二进制的最后一位是 0 还是 1，如下：(x >> k) & 1。
十三 leecode相关题
解题思路：
- 初始化计数器变量 count 为 0。
- 定义一个循环变量 i，并初始化为 0。
- 进入循环，判断 i 是否小于 32（因为无符号整数有 32 位）。
- 在循环内部，首先使用位运算将数字 n 的第 i 位设置为 1，并将结果与 n 进行比较。如果结果等于 n，则说明第 i 位为 1，将计数器 count 加 1。
- 循环变量 i 增加 1，继续下一次循环。
- 循环结束后，返回最终的计数值 count。
class Solution { public: int hammingWeight(uint32_t n) { int count=0; uint32_t i=0; while(i<32) { if((n | (1<<i)) == n)count++; i++; } return count; } };
解题思路：
- 初始化计数器变量 count 为 0。
- 进入循环，判断 left 是否小于 right。
- 在循环内部，将 left 和 right 都右移一位（相当于除以 2），并同时增加计数器 count。
- 循环结束后，返回 left 左移 count 位的结果。
class Solution { public: int rangeBitwiseAnd(int left, int right) { int count=0; while(left<right) { left>>=1; right>>=1; ++count; } return left<<count; } };
剑指 Offer 56 - II. 数组中数字出现的次数 II
解题思路：
- 初始化一个长度为 32 的数组 count，用于统计每一位上的出现次数。
- 初始化结果变量 result 为 0。
- 进入第一个循环，循环变量 i 控制当前统计的是第 i 位。
- 在第一个循环内部，进入第二个循环，循环变量 num 遍历数组 nums 中的每个元素。
- 在第二个循环内部，通过右移 i 位和按位与运算，将 num 的第 i 位取出并累加到 count[i] 中，即统计当前位上数字出现的次数。
- 循环结束后，进入第三个循环，循环变量 i 控制当前统计的是第 i 位。
- 在第三个循环内部，通过对 count[i] 取余 3，得到只出现一次的数字在当前位上的值，并将其左移 i 位后，通过按位或运算更新结果变量 result。
- 循环结束后，返回最终的结果变量 result。
class Solution { public: int singleNumber(std::vector<int>& nums) { int count[32] = {0}; // 用于统计每一位上的出现次数 int result = 0; for (int i = 0; i < 32; i++) { for (int num : nums) { // 统计当前位上数字出现的次数 count[i] += (num >> i) & 1; } // 对统计结果取余，得到只出现一次的数字在当前位上的值 result |= (count[i] % 3) << i; } return result; } };
解题思路：
- 初始化结果变量 ans 为 0。
- 初始化长度为 2^16（即65536）的数组 count，用于统计每个数字的按位与结果出现的次数。
- 进入第一个循环，循环变量 x 遍历数组 nums 中的每个元素。
- 在第一个循环内部，进入第二个循环，循环变量 y 遍历数组 nums 中的每个元素。
- 在第二个循环内部，通过按位与运算符将 x 和 y 按位与的结果作为索引，将 count 对应位置的值增加 1，以统计每个按位与结果出现的次数。
- 第二个循环结束后，进入第三个循环，循环变量 x 遍历数组 nums 中的每个元素。
- 在第三个循环内部，进入第四个循环，循环变量 i 遍历从 0 到 2^16-1 的所有整数。
- 在第四个循环内部，判断是否满足 (x & i) == 0 的条件，如果满足，则将 count[i] 的值累加到结果变量 ans 中。
- 第四个循环结束后，返回最终的结果变量 ans。
class Solution { public: int countTriplets(vector<int>& nums) { int ans=0; int count[1<<16]={0}; for(int x:nums) for(int y:nums) count[x&y]++; for(int x:nums) for(int i=0;i<1<<16;++i) if((x&i)==0)ans+=count[i]; return ans; } };
解题思路：
- 我们需要将数组arr1中的所有元素进行异或运算，得到一个变量a作为中间结果。这是因为异或运算满足结合律和交换律，即无论元素的顺序如何，结果都是相同的。
- 我们需要遍历数组arr2中的每个元素，并对其进行按位与运算，将结果保存回数组arr2中。这样做的目的是将arr2中的每个元素与a进行按位与运算，从而获取每个(i, j)数对的按位与结果。
- 我们再次遍历数组arr2，对其中的每个元素进行异或运算，得到最终的异或和ans。
- 我们只需要进行两次循环来完成计算，分别是遍历arr1和遍历arr2的过程，因此时间复杂度为O(N+M)，其中N是arr1的长度，M是arr2的长度。
- 这样写的原因是为了利用异或运算的性质，同时减少了额外空间的使用，直接在原数组arr2上进行操作。这样可以提高代码的效率和节省内存空间。
class Solution { public: int getXORSum(vector<int>& arr1, vector<int>& arr2) { //(a&b)^(a&c)=a&(b^c) int ans=0,a=0; for(int i=0;i<arr1.size();++i){a^=arr1[i];} for(int i=0;i<arr2.size();++i){arr2[i]&=a;} for(int i=0;i<arr2.size();++i){ans^=arr2[i];} return ans; } };
后记
刷题最重要的是基础！基础！基础！
