位运算修行手册

爱被打了一巴掌 2023-10-13 22:37 78阅读 0赞

\*明明自觉学会了不少知识，可真正开始做题时，却还是出现了“一支笔，一双手，一道力扣（Leetcode）做一宿”的窘境？你是否也有过这样的经历，题型不算很难，看题解也能弄明白，可一到自己做就变成了与题面面相觑无从下手。这就是基础知识掌握不扎实、不牢固导致的，我们以位运算为例，我将把位运算基础给你清楚讲述，再以例题带你实战体验。

### 一、位与运算符 ###

位与运算符是一个二元的位运算符，也就是有两个操作数，表示为 x & y。

位与运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共 4 种情况。

![https://article-images.zsxq.com/FuK9MkdBw13Y-L9Hmp176jUtqoKi][https_article-images.zsxq.com_FuK9MkdBw13Y-L9Hmp176jUtqoKi]

通过这个表，我们得出一些结论：

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.  (1) 在C语言中，以 0b 作为前缀，表示这是一个二进制数。那么 a 的实际值就是 (1010) 。
2.  (2) 同样的， b 的实际值就是 (0110) ；
3.  (3) 那么这里 a & b 就是对 (1010) 和 (0110) 的每一位做表格中的 & 运算。
4.  所以最后输出结果为：
5.  因为输出的是十进制数，它的二进制表示为： (0010)\_2。
6.  注意：这里的 **前导零** 可有可无，作者写上前导零只是为了对齐以及让读者更加清楚位与的运算方式。

### 二、位与运算符的应用 ###

#### 1、奇偶性判定 ####

1.  我们判断一个数是奇数还是偶数，往往是通过取模 %来判断的，如下：

int main() {
    
        if(5 % 2 == 1) {
    
            printf("5是奇数\n");
    
        }
    
        if(6 % 2 == 0) {
    
            printf("6是偶数\n");
    
        }
    
        return 0;
    
    }

1.  然而，我们也可以这么写：

int main() {
    
        if(5 & 1) {
    
            printf("5是奇数\n");
    
        }
    
        if( (6 & 1) == 0 ) {
    
            printf("6是偶数\n");
    
        }
    
        return 0;
    
    }
    
    1.

1.  这是利用了奇数和偶数分别的二进制数的特性，如下表所示：

![https://article-images.zsxq.com/Fr3FEevcsw6AGwMedmlYozR8fBWD][https_article-images.zsxq.com_Fr3FEevcsw6AGwMedmlYozR8fBWD]

1.  所以，我们对任何一个数，通过将它和 0b1 进行位与，结果为零，则必然这个数的二进制末尾位为0，根据以上表就能得出它是偶数了；否则，就是奇数。
2.  注意，由于 if 语句我们还没有实际提到过，所以这里简单提一下，后面会有系统的讲解：
3.  对于以上语句，expr 代表的是一个表达式，表达式的值最后只有 零 或 非零，如果值为非零，才会执行 body中的内容。

#### 2、取末五位 ####

> 【例题1】给定一个数，求它的二进制表示的末五位，以十进制输出即可。

1.  这个问题的核心就是：我们只需要末五位，剩下的位我们是不需要的，所以可以将给定的数 位与上0b11111，这样一来就直接得到末五位的值了。
2.  代码实现如下：

int main() {
    
        int x;
    
        scanf("%d", &x);
    
        printf("%d\n", (x & 0b11111) );
    
        return 0;
    
    }

那么如果问题变成下面的形式，代码又要怎么写呢？

> 【例题2】如果是想得到末七位、末九位、末十四位、末 K 位，应该如何实现呢？

#### 3、消除末尾五位 ####

> 【例题3】给定一个 32 位整数，要求消除它的末五位。

1.  还是根据位与的性质，消除末五位的含义，有两层：
2.  1）末五位，要全变成零；
3.  2）剩下的位不变；
4.  那么，根据位运算的性质，我们需要数，它的高27位都为1，低五位都为 0，则这个数就是：

![https://article-images.zsxq.com/Fgop5R\_LxyZtPF70Vs-VdDN51j\_x][https_article-images.zsxq.com_Fgop5R_LxyZtPF70Vs-VdDN51j_x]

1.  但是如果要这么写，代码不疯掉，人也会疯掉，所以一般我们把它转成十六进制，每四个二进制位可以转成一个十六进制数，所以得到十六进制数为 0xffffffe0。
2.  代码实现如下：

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.  我们知道，这个数的二进制表示形式一定是：

![https://article-images.zsxq.com/FjNYjX6GoiKRmv13CEGybKCt0Qe5][https_article-images.zsxq.com_FjNYjX6GoiKRmv13CEGybKCt0Qe5]

1.  如果，我们把这个二进制数加上1，得到的就是：

![https://article-images.zsxq.com/FjFgw6gfXY6yEU2lGniGHpOVdaL4][https_article-images.zsxq.com_FjFgw6gfXY6yEU2lGniGHpOVdaL4]

1.  我们把这两个数进行位与运算，得到：

![https://article-images.zsxq.com/FivTjeFY443LOb1bqqNav9LkrIpD][https_article-images.zsxq.com_FivTjeFY443LOb1bqqNav9LkrIpD]

1.  所以，你学会了吗？

#### 5、2的幂判定 ####

> 【例题5】请用一句话，判断一个正数是不是2的幂。

1.  如果一个数是 2 的幂，它的二进制表示必然为以下形式：

![https://article-images.zsxq.com/FuSMvHw-X3ZrceocHXM8XJQvjkY2][https_article-images.zsxq.com_FuSMvHw-X3ZrceocHXM8XJQvjkY2]

1.  这个数的十进制值为 2 的 k 次。
2.  那么我们将它减一，即 2 的 k 次 减一 的二进制表示如下（参考二进制减法的借位）：

![https://article-images.zsxq.com/Fp4a8QJapXNc0ry4bnQ3yEhYc5fY][https_article-images.zsxq.com_Fp4a8QJapXNc0ry4bnQ3yEhYc5fY]

1.  于是 这两个数位与的结果为零，于是我们就知道了如果一个数 x 是 2 的幂，那么 x & (x-1) 必然为零。而其他情况则不然。所以本题的答案为：

### 三、位或运算符 ###

位或运算符是一个二元的位运算符，也就是有两个操作数，表示为 x | y。位或运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共 4 种情况。

![https://article-images.zsxq.com/FvpY3Ck4J9BVcaWPDjwehJJbclwg][https_article-images.zsxq.com_FvpY3Ck4J9BVcaWPDjwehJJbclwg]

通过这个表，我们得出一些结论：

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 个零，二进制表示如下：

![https://article-images.zsxq.com/FiPsRdLga5cfh8-4OBQc7DIMfrKD][https_article-images.zsxq.com_FiPsRdLga5cfh8-4OBQc7DIMfrKD]

那么，如果我们对它进行减一操作，得到的二进制数就是：

![https://article-images.zsxq.com/Fr1cTE2CXyRhlBgZUPFfJRwwDG56][https_article-images.zsxq.com_Fr1cTE2CXyRhlBgZUPFfJRwwDG56]

我们发现，只要对这两个数进行位或，就能得到：

![https://article-images.zsxq.com/Fi4GQ3jvcIupCmwF3tDYwl1\_fjKC][https_article-images.zsxq.com_Fi4GQ3jvcIupCmwF3tDYwl1_fjKC]

也正是题目所求，所以代码实现如下：

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 种情况。

![https://article-images.zsxq.com/FiBrFELi58vEcQmME5\_CcnoTv5dW][https_article-images.zsxq.com_FiBrFELi58vEcQmME5_CcnoTv5dW]

通过这个表，我们得出一些结论：

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 两种情况。

![https://article-images.zsxq.com/FqGHMjJbeJzIbbRMwyx6vVUtpGbP][https_article-images.zsxq.com_FqGHMjJbeJzIbbRMwyx6vVUtpGbP]

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。所以补码也可以表示成如下形式：

![https://article-images.zsxq.com/FtYp9xvEhlduj1YtCnEf0vB1UBwf][https_article-images.zsxq.com_FtYp9xvEhlduj1YtCnEf0vB1UBwf]

于是，对于 int 类型，就有：

![https://article-images.zsxq.com/Fv6q2Vd9LSbDZwSCdHhlaf6xKqP3][https_article-images.zsxq.com_Fv6q2Vd9LSbDZwSCdHhlaf6xKqP3]

即：

![https://article-images.zsxq.com/Fh68gYeZdzO0W4Dmw6pwnO02h09n][https_article-images.zsxq.com_Fh68gYeZdzO0W4Dmw6pwnO02h09n]

于是，我们开始数数……

2^32 = 1 00000000 00000000 00000000 00000000

2^32 - 1 = 11111111 11111111 11111111 11111111

2^32 - 2 = 11111111 11111111 11111111 11111110

近一步了解了 -2 的二进制表示。

### 八、按位取反运算符的应用 ###

#### 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 位能表示数值，能够表示的数值范围是：

![https://article-images.zsxq.com/Fi0lx3D7DTuL6VbpSvjuj4KSYb\_q][https_article-images.zsxq.com_Fi0lx3D7DTuL6VbpSvjuj4KSYb_q]

所以，对于有符号整型，输出采用 %d ，如下：

int main() {
    
        printf("%d\n", ~0 );
    
        return 0;
    
    }

结果为：

\-1

##### 2）无符号整型 #####

对于无符号整型 unsigned int 而言，由于不需要符号位，所以总共有32位表示数值，数值范围为：

![https://article-images.zsxq.com/Fvrxl2rj6EjwUVfXT6rgAmcrhLlu][https_article-images.zsxq.com_Fvrxl2rj6EjwUVfXT6rgAmcrhLlu]

对于无符号整型，输出采用 %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;
    
    }

运行结果为：

### 九、左移运算符 ###

#### 1、左移的二进制形态 ####

左移运算符是一个二元的位运算符，也就是有两个操作数，表示为 x << y 。其中 x 和 y 均为整数。

x << y 念作：“将 x 左移 y 位”，这里的位当然就是二进制位了，那么它表示的意思也就是：先将 x 用二进制表示，然后再左移 y 位，并且在尾部添上 y 个零。

举个例子：对于二进制数 (10111) 左移 y 位的结果就是：

![https://article-images.zsxq.com/FvTqe04ZHua0EeVeUMDCtMNXzo7n][https_article-images.zsxq.com_FvTqe04ZHua0EeVeUMDCtMNXzo7n]

#### 2、左移的执行结果 ####

x << y 的执行结果等价于：

![https://article-images.zsxq.com/Fk\_rdCU\_5WjxTh\_orJIHhEnrhKuY][https_article-images.zsxq.com_Fk_rdCU_5WjxTh_orJIHhEnrhKuY]

如下代码：

int main() {
    
        int x = 3;
    
        int y = 5;
    
        printf("%d\n", x << y);
    
        return 0;
    
    }

输出结果为：

正好符合这个左移运算符的实际含义：

![https://article-images.zsxq.com/FhtmddBPBXDrRnnKt9ntJl1rZJmd][https_article-images.zsxq.com_FhtmddBPBXDrRnnKt9ntJl1rZJmd]

最常用的就是当 x = 1 时，1 << y 代表的就是 2^y，即 2 的幂。

#### 3、负数左移的执行结果 ####

所谓负数左移，就是 x << y 中，当 x 为负数的情况，代码如下：

int main() {
    
        printf("%d\n", -1 << 1);
    
        return 0;
    
    }

它的输出如下：

我们发现同样是满足的，这个可以用补码来解释，-1的补码为：

![https://article-images.zsxq.com/FhggBS-a-eEd\_69rLowsn9EhEwrw][https_article-images.zsxq.com_FhggBS-a-eEd_69rLowsn9EhEwrw]

左移一位后，最高位的 1 就没了，低位补上 0，得到：

![https://article-images.zsxq.com/Fs8\_QTeR0VEbB\_61OllhxoRrPCj5][https_article-images.zsxq.com_Fs8_QTeR0VEbB_61OllhxoRrPCj5]

而这，正好是 -2 的补码，同样，继续左移 1 位，得到：

![https://article-images.zsxq.com/FghDxL2eqaV\_gY91WKkqtWjZeWXD][https_article-images.zsxq.com_FghDxL2eqaV_gY91WKkqtWjZeWXD]

这是 -4 的补码，以此类推，所以负整数的左移结果同样也是满足的。

> 可以理解成 - (x << y) 和 (-x) << y 是等价的。

#### 4、左移负数位是什么情况 ####

刚才我们讨论了 x < 0 的情况，那么接下来，我们试下 y < 0 的情况会是如何？

是否同样满足如下等式呢？

![https://article-images.zsxq.com/FpFGvQNEhi\_LQJq9OXWCaJhd4O89][https_article-images.zsxq.com_FpFGvQNEhi_LQJq9OXWCaJhd4O89]

如果还是满足，那么两个整数的左移就有可能产生小数了。

看个例子：

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 。

实际输出的结果，的确是：

但是如果按照之前的规则，答案应该是：

![https://article-images.zsxq.com/FmKoYtppTNqzNexloHYWWhCUIcxn][https_article-images.zsxq.com_FmKoYtppTNqzNexloHYWWhCUIcxn]

这里又回到了补码的问题上，事实上，在计算机中， int 整型其实是一个环，溢出以后又会回来，而环的长度正好是 2^32，所以 -2^32 + 2 = 2，这个就有点像同余的概念，这两个数是模 2^32 同余的。

### 十、左移运算符的应用 ###

#### 1、取模转化成位运算 ####

对于 x 模上一个 2 的次幂的数 y，我们可以转换成位与上 2^y-1。

即在数学上的：

![https://article-images.zsxq.com/FpUvtfkgp\_qUoKYkLHViqWqgeTgD][https_article-images.zsxq.com_FpUvtfkgp_qUoKYkLHViqWqgeTgD]

在计算机中就可以用一行代码表示：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 位的结果就是：

![https://article-images.zsxq.com/FvInA6fe5nYR4n5vi7lWXfKy8S9F][https_article-images.zsxq.com_FvInA6fe5nYR4n5vi7lWXfKy8S9F]

#### 2、右移的执行结果 ####

x >> y 的执行结果等价于：

![https://article-images.zsxq.com/FkeAdR01NS5ApAkj5EjHYz-zUNjc][https_article-images.zsxq.com_FkeAdR01NS5ApAkj5EjHYz-zUNjc]

这个符号代表取下整。如下代码：

int main() {
    
        int x = 0b1010111;
    
        int y = 3;
    
        printf("%d\n", x >> y);
    
        return 0;
    
    }

输出结果为：

正好符合这个右移运算符的实际含义：

![https://article-images.zsxq.com/Funy2VkX9ZHf-H9VFUc3\_NALCVY9][https_article-images.zsxq.com_Funy2VkX9ZHf-H9VFUc3_NALCVY9]

> 由于除法可能造成不能整除，所以才会有 取下整 这一步运算。

#### 3、负数右移的执行结果 ####

所谓负数右移，就是 x >> y 中，当 x 为负数的情况，代码如下：

int main() {
    
        printf("%d\n", -1 >> 1);
    
        return 0;
    
    }

它的输出如下：

我们发现同样是满足如下式子的

![https://article-images.zsxq.com/FhOdztoufxwrir271BznnGYfmtgE][https_article-images.zsxq.com_FhOdztoufxwrir271BznnGYfmtgE]

这个可以用补码来解释，-1 的补码为：

![https://article-images.zsxq.com/Fj-tKcTGYyQW68iOIqXEpvtPyWpe][https_article-images.zsxq.com_Fj-tKcTGYyQW68iOIqXEpvtPyWpe]

右移一位后，由于是负数，高位补上 1，得到：

![https://article-images.zsxq.com/Fj-tKcTGYyQW68iOIqXEpvtPyWpe][https_article-images.zsxq.com_Fj-tKcTGYyQW68iOIqXEpvtPyWpe]

> 可以理解成 - (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 的情况会是如何？是否同样满足如下性质呢？

![https://article-images.zsxq.com/FkIn8OfkxIBaXIrLHlWwvfSXfEcT][https_article-images.zsxq.com_FkIn8OfkxIBaXIrLHlWwvfSXfEcT]

如果还是满足，那么两个整数的左移就有可能产生小数了。

看个例子：

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。如下：

![https://article-images.zsxq.com/Fsl9kFfLcoD6dd\_P2bwxA3RjTP0q][https_article-images.zsxq.com_Fsl9kFfLcoD6dd_P2bwxA3RjTP0q]

然后我们将它加上 1 以后，得到的就是：

![https://article-images.zsxq.com/Fs\_N8KlpKEMMQH1lwFA5g0uVdVuU][https_article-images.zsxq.com_Fs_N8KlpKEMMQH1lwFA5g0uVdVuU]

这时候将这两个数异或结果为：

![https://article-images.zsxq.com/FiBtxZ6AnUcJQFN2r97bOPbR-Wwc][https_article-images.zsxq.com_FiBtxZ6AnUcJQFN2r97bOPbR-Wwc]

这时候，再进行右移一位，就得到了 连续 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)\]

如果还是满足，那么两个整数的左移就有可能产生小数了。

看个例子：

虽然能够正常运行，但是结果好像不是我们期望的，而且会报警告如下：

> \[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。

### 十三 leecode相关题 ###

> [191. 位1的个数][191. _1]

> 解题思路：
> 
> 1.  初始化计数器变量 count 为 0。
> 2.  定义一个循环变量 i，并初始化为 0。
> 3.  进入循环，判断 i 是否小于 32（因为无符号整数有 32 位）。
> 4.  在循环内部，首先使用位运算将数字 n 的第 i 位设置为 1，并将结果与 n 进行比较。如果结果等于 n，则说明第 i 位为 1，将计数器 count 加 1。
> 5.  循环变量 i 增加 1，继续下一次循环。
> 6.  循环结束后，返回最终的计数值 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;
        }
    };

> [201. 数字范围按位与][201.]

> 解题思路：
> 
> 1.  初始化计数器变量 count 为 0。
> 2.  进入循环，判断 left 是否小于 right。
> 3.  在循环内部，将 left 和 right 都右移一位（相当于除以 2），并同时增加计数器 count。
> 4.  循环结束后，返回 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][Offer 56 - II. _ II]

> 解题思路：
> 
> 1.  初始化一个长度为 32 的数组 count，用于统计每一位上的出现次数。
> 2.  初始化结果变量 result 为 0。
> 3.  进入第一个循环，循环变量 i 控制当前统计的是第 i 位。
> 4.  在第一个循环内部，进入第二个循环，循环变量 num 遍历数组 nums 中的每个元素。
> 5.  在第二个循环内部，通过右移 i 位和按位与运算，将 num 的第 i 位取出并累加到 count\[i\] 中，即统计当前位上数字出现的次数。
> 6.  循环结束后，进入第三个循环，循环变量 i 控制当前统计的是第 i 位。
> 7.  在第三个循环内部，通过对 count\[i\] 取余 3，得到只出现一次的数字在当前位上的值，并将其左移 i 位后，通过按位或运算更新结果变量 result。
> 8.  循环结束后，返回最终的结果变量 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;
        }
    };

> [982. 按位与为零的三元组][982.]

> 解题思路：
> 
> 1.  初始化结果变量 ans 为 0。
> 2.  初始化长度为 2^16（即65536）的数组 count，用于统计每个数字的按位与结果出现的次数。
> 3.  进入第一个循环，循环变量 x 遍历数组 nums 中的每个元素。
> 4.  在第一个循环内部，进入第二个循环，循环变量 y 遍历数组 nums 中的每个元素。
> 5.  在第二个循环内部，通过按位与运算符将 x 和 y 按位与的结果作为索引，将 count 对应位置的值增加 1，以统计每个按位与结果出现的次数。
> 6.  第二个循环结束后，进入第三个循环，循环变量 x 遍历数组 nums 中的每个元素。
> 7.  在第三个循环内部，进入第四个循环，循环变量 i 遍历从 0 到 2^16-1 的所有整数。
> 8.  在第四个循环内部，判断是否满足 (x & i) == 0 的条件，如果满足，则将 count\[i\] 的值累加到结果变量 ans 中。
> 9.  第四个循环结束后，返回最终的结果变量 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;
        }
    };

> [1835. 所有数对按位与结果的异或和][1835.]

> 解题思路：
> 
> 1.  我们需要将数组arr1中的所有元素进行异或运算，得到一个变量a作为中间结果。这是因为异或运算满足结合律和交换律，即无论元素的顺序如何，结果都是相同的。
> 2.  我们需要遍历数组arr2中的每个元素，并对其进行按位与运算，将结果保存回数组arr2中。这样做的目的是将arr2中的每个元素与a进行按位与运算，从而获取每个(i, j)数对的按位与结果。
> 3.  我们再次遍历数组arr2，对其中的每个元素进行异或运算，得到最终的异或和ans。
> 4.  我们只需要进行两次循环来完成计算，分别是遍历arr1和遍历arr2的过程，因此时间复杂度为O(N+M)，其中N是arr1的长度，M是arr2的长度。
> 5.  这样写的原因是为了利用异或运算的性质，同时减少了额外空间的使用，直接在原数组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;
        }
    };

### 后记 ###

刷题最重要的是基础！基础！基础！

[https_article-images.zsxq.com_FuK9MkdBw13Y-L9Hmp176jUtqoKi]: https://img-blog.csdnimg.cn/img_convert/f2f9dc5764cebfa76ed4f0335038ceca.png
[https_article-images.zsxq.com_Fr3FEevcsw6AGwMedmlYozR8fBWD]: https://img-blog.csdnimg.cn/img_convert/37cbf51c7ea6dfa3ce317d9f3db04db0.png
[https_article-images.zsxq.com_Fgop5R_LxyZtPF70Vs-VdDN51j_x]: https://img-blog.csdnimg.cn/img_convert/cc50887f991c52d4137e1ff7c315ba7c.png
[https_article-images.zsxq.com_FjNYjX6GoiKRmv13CEGybKCt0Qe5]: https://img-blog.csdnimg.cn/img_convert/88931954c07827345a0b69c060a28c16.png
[https_article-images.zsxq.com_FjFgw6gfXY6yEU2lGniGHpOVdaL4]: https://img-blog.csdnimg.cn/img_convert/1483767202696cdd665d9ae8e887c293.png
[https_article-images.zsxq.com_FivTjeFY443LOb1bqqNav9LkrIpD]: https://img-blog.csdnimg.cn/img_convert/d4b659213ae1becb2494177c8ad26d4c.png
[https_article-images.zsxq.com_FuSMvHw-X3ZrceocHXM8XJQvjkY2]: https://img-blog.csdnimg.cn/img_convert/289af9f0e4316d2ef20e134e77d77682.png
[https_article-images.zsxq.com_Fp4a8QJapXNc0ry4bnQ3yEhYc5fY]: https://img-blog.csdnimg.cn/img_convert/dcb31981032d03a9aacf1ddf4e9f7118.png
[https_article-images.zsxq.com_FvpY3Ck4J9BVcaWPDjwehJJbclwg]: https://img-blog.csdnimg.cn/img_convert/55652ddb605a9bab264077ca7b7afcd6.png
[https_article-images.zsxq.com_FiPsRdLga5cfh8-4OBQc7DIMfrKD]: https://img-blog.csdnimg.cn/img_convert/1966cbbbc57d0aafabad4289227f0972.png
[https_article-images.zsxq.com_Fr1cTE2CXyRhlBgZUPFfJRwwDG56]: https://img-blog.csdnimg.cn/img_convert/4ed0d6334432562defec597c0a66767c.png
[https_article-images.zsxq.com_Fi4GQ3jvcIupCmwF3tDYwl1_fjKC]: https://img-blog.csdnimg.cn/img_convert/bc004f5c9c33add24a7467ba07c8f59f.png
[https_article-images.zsxq.com_FiBrFELi58vEcQmME5_CcnoTv5dW]: https://img-blog.csdnimg.cn/img_convert/7318643fed6b7d1340157f3ef28af0f2.png
[https_article-images.zsxq.com_FqGHMjJbeJzIbbRMwyx6vVUtpGbP]: https://img-blog.csdnimg.cn/img_convert/0bc8e1e0886165f9099d260adfa2921c.png
[https_article-images.zsxq.com_FtYp9xvEhlduj1YtCnEf0vB1UBwf]: https://img-blog.csdnimg.cn/img_convert/f03fc3b4fabc65ac132b3ff5bcea75fa.png
[https_article-images.zsxq.com_Fv6q2Vd9LSbDZwSCdHhlaf6xKqP3]: https://img-blog.csdnimg.cn/img_convert/a00b302ee26ebbf6ed9f95ded8576825.png
[https_article-images.zsxq.com_Fh68gYeZdzO0W4Dmw6pwnO02h09n]: https://img-blog.csdnimg.cn/img_convert/9dae54a25017ef7bb6b2c94779ab666c.png
[https_article-images.zsxq.com_Fi0lx3D7DTuL6VbpSvjuj4KSYb_q]: https://img-blog.csdnimg.cn/img_convert/f468addf1b68a99a3ddb087eb7934384.png
[https_article-images.zsxq.com_Fvrxl2rj6EjwUVfXT6rgAmcrhLlu]: https://img-blog.csdnimg.cn/img_convert/4a3848ac0475dd3292e39268fb129ae3.png
[https_article-images.zsxq.com_FvTqe04ZHua0EeVeUMDCtMNXzo7n]: https://img-blog.csdnimg.cn/img_convert/931cc380ad04bb2b6328b156f8a3029d.png
[https_article-images.zsxq.com_Fk_rdCU_5WjxTh_orJIHhEnrhKuY]: https://img-blog.csdnimg.cn/img_convert/ea6824cb296f822c644421191da167c0.png
[https_article-images.zsxq.com_FhtmddBPBXDrRnnKt9ntJl1rZJmd]: https://img-blog.csdnimg.cn/img_convert/5039ef753fbdaf95b6655ce32e05e43f.png
[https_article-images.zsxq.com_FhggBS-a-eEd_69rLowsn9EhEwrw]: https://img-blog.csdnimg.cn/img_convert/cb4d2fc2c2e6429a18c1c53a4c0e8054.png
[https_article-images.zsxq.com_Fs8_QTeR0VEbB_61OllhxoRrPCj5]: https://img-blog.csdnimg.cn/img_convert/fd43b34959a3df766e23e613ac095934.png
[https_article-images.zsxq.com_FghDxL2eqaV_gY91WKkqtWjZeWXD]: https://img-blog.csdnimg.cn/img_convert/a533953d1eb215ecd3d1b0faadc554c5.png
[https_article-images.zsxq.com_FpFGvQNEhi_LQJq9OXWCaJhd4O89]: https://img-blog.csdnimg.cn/img_convert/eee5da3bbeb6563a1e4ee04747951db4.png
[https_article-images.zsxq.com_FmKoYtppTNqzNexloHYWWhCUIcxn]: https://img-blog.csdnimg.cn/img_convert/7aecc87bfbd15ab685b3a52bbf9b70eb.png
[https_article-images.zsxq.com_FpUvtfkgp_qUoKYkLHViqWqgeTgD]: https://img-blog.csdnimg.cn/img_convert/f23d42caa13b8f0f1160598b797d2367.png
[https_article-images.zsxq.com_FvInA6fe5nYR4n5vi7lWXfKy8S9F]: https://img-blog.csdnimg.cn/img_convert/5bb9133371199e570786119dd7e5b80c.png
[https_article-images.zsxq.com_FkeAdR01NS5ApAkj5EjHYz-zUNjc]: https://img-blog.csdnimg.cn/img_convert/617cc53be1348797cc51c3da2545fe89.png
[https_article-images.zsxq.com_Funy2VkX9ZHf-H9VFUc3_NALCVY9]: https://img-blog.csdnimg.cn/img_convert/0cdacd9f60d66a63534cb11f8c215338.png
[https_article-images.zsxq.com_FhOdztoufxwrir271BznnGYfmtgE]: https://img-blog.csdnimg.cn/img_convert/a921fedcae3c63005ebc7a6756db5939.png
[https_article-images.zsxq.com_Fj-tKcTGYyQW68iOIqXEpvtPyWpe]: https://img-blog.csdnimg.cn/img_convert/3cb9a0e59e1e6732a8068fda7fa64bf1.png
[https_article-images.zsxq.com_FkIn8OfkxIBaXIrLHlWwvfSXfEcT]: https://img-blog.csdnimg.cn/img_convert/9c0fce17944d77022d0e7f1436d24f02.png
[https_article-images.zsxq.com_Fsl9kFfLcoD6dd_P2bwxA3RjTP0q]: https://img-blog.csdnimg.cn/img_convert/acc93bb7890cb9f32ec5785a4ddcee74.png
[https_article-images.zsxq.com_Fs_N8KlpKEMMQH1lwFA5g0uVdVuU]: https://img-blog.csdnimg.cn/img_convert/db47d5969f6314bd12b193ff9af0d8f6.png
[https_article-images.zsxq.com_FiBtxZ6AnUcJQFN2r97bOPbR-Wwc]: https://img-blog.csdnimg.cn/img_convert/6547f09b8a8389d4342357f015b8bfed.png
[191. _1]: https://leetcode.cn/problems/number-of-1-bits/
[201.]: https://leetcode.cn/problems/bitwise-and-of-numbers-range/
[Offer 56 - II. _ II]: https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
[982.]: https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/
[1835.]: https://leetcode.cn/problems/find-xor-sum-of-all-pairs-bitwise-and/