【算法】【位运算】一文带你搞懂位运算

ゝ一世哀愁。 2024-04-06 14:10 168阅读 0赞

## 二进制与十进制的转换 ##

### 十进制->二进制 ###

#### 正整数 ####

除二取余，逆序排列，高位补0  
![在这里插入图片描述][8d9b6ae7b0f7443798ea2e6aef43aa58.png]

#### 负整数 ####

先是将对应的正整数转换成二进制后，对二进制取反，然后对结果再加一  
![在这里插入图片描述][e4c5d1b89675468ab71e2cc5e8be5c8e.png]

#### 小数 ####

对小数点以后的数乘以2，然后取其结果的整数部分（不是1就是0），然后再用小数部分再乘以2，再取结果的整数部分……以此类推，直到小数部分为0或者位数已经够了就OK了。然后把取的整数部分按先后次序排列，就构成了二进制小数部分的序列

![在这里插入图片描述][402499e5def14dbbbbf2c737daf10f26.png]

> 当小数除不尽的时候，一般取八位（或按要求）

#### 混合数 ####

![在这里插入图片描述][2bd21f3110b746ec921cf5c13bb7e37c.png]

### 二进制->十进制 ###

#### 正整数 ####

从二进制的右边第一个数开始，每一个乘以2的n次方，n从0开始，每次递增1。然后得出来的每个数相加即是十进制数。

例如：

二进制的数110化为十进制：
    
          0*2^0+1*2^1+1^2^2=6

#### 负整数 ####

如果补齐之后，最高位是1,则说明是负数

*  方法一：先减一，再取反，再加上负号
 *  方法二：先取反，再加一，再加上负号

#### 小数 ####

![在这里插入图片描述][437bbf9f5aa44fb6848208946bdbfddf.png]

![在这里插入图片描述][868b884c7c914740aa8e6eadbabffd8b.jpeg]

## 原码、反码、补码的转换 ##

### (1) 正数的原码、反码、补码相同 ###

![e1e492d084c662099930b5524cb5d527.png][]

### (2) 负数的原码、反码、补码转换如下图所示 ###

![2931ed241095b767fb57f3ed8f2b5ca4.png][]

**需要说明的是，在计算机中，数字是以补码的形式存在的，计算也是用补码来进行计算，计算后的结果也是补码**

## 位运算 ##

下表列出了位运算符的基本运算，假设整数变量 A 的值为 60 和变量 B 的值为 13：  
![在这里插入图片描述][71607622792e4301a6589f5168316077.png]

### (1) & : 按位与 ###

5 & 9 = 1

![07a2a58f55e7eaf5cf8be865bbe4ecb0.png][]

### (2) | : 按位或 ###

5 | 9 = 13

![3d963bde3b73aef3bfc7fdb342741526.png][]

### (3) ^ : 按位异或 ###

5 ^ 9 = 12

![590fe95de47742845a5eb929322690c6.png][]

### (4) ~ : 按位非 ###

~5 = -6

![b6b40fdfb3ef2fcdf1a4debcd66b61ed.png][]

### (5) << : 左移 ###

5 << 2 = 20

![d54ce3f5efd1d940f4d6c86ba57691f4.png][]

\-5 << 2 = -20

![6f2125b7caa6246d3989f8c6fc869921.png][]

### (6) >> : 右移 ###

\-5 >> 2 = -2

![4f4e537eb32de20ab2179a2fc02151f5.png][]

### (7) >>> : 无符号右移 ###

\-5 >>> 2 = 1073741822

![649675ffa12dfcd1255073a9ad26cf4a.png][]

## 应用 ##

### 左移 ###

左移常常被用来 \*（2^n)的运算  
8<< 1 -> 8 \* 2=16  
8<< 2 -> 8 \* (2^2)=32  
8<< n -> 8 \* (2^n)

### 右移 ###

右移常被用来做 / (2 ^ n)的运算，  
12 >> 1 = 6  
12 >> 2 = 3  
12 >> n = 12 /(2^n)

### 位与 ###

*  二进制位与运算相当于对应位相加之后的进位 ,例如：

> 1 & 1 = 1 (当前位的值进一位)  
> 1 & 0 = 0(当前位的值不进位）  
> 0 & 0 = 0 (当前位的值不进位）

#### 计算二进制中有多少个 1（32位） ####

由 `x & (x-1)`消去x最后一位知。循环使用`x & (x-1)`消去最后一位1，计算总共消去了多少次即可。  
[Loading Question… - 力扣（LeetCode）][Loading Question_ - _LeetCode]

public class Solution {
          
        // you need to treat n as an unsigned value  
        public int hammingWeight(int n) {
          
            int count = 0;  
            for (int i = 0; i < 32; ++i) {
          
                count += n & 1;  
                n >>>= 1;  
            }  
            return count;  
      
        }  
      
        public int hammingWeight2(int n) {
          
            int res = 0;  
            while (n != 0) {
          
                res += 1;  
                n &= n - 1;//可以把n的最后一个1变成0  
            }  
            return res;  
        }  
      
    }

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

(在不产生溢出的情况下)

*  `a % (2^n)`等价于`a & (2^n - 1)`
 *  `a % 2`等价于`a & 1`

#### 判断奇偶数 ####

利用 &位运算符的特性，判断二进制数第一位是0还是1。  
用`if ((a & 1) == 0)` 代替`if (a % 2 == 0)`来判断a是不是偶数。

### 异或 ###

*  二进制位的异或运算相当于位相加，例如：

> 1 ^ 1 = 0 (当前位值为 0 进一位)  
> 1 ^ 0 = 1 (当前位值为 1)  
> 0 ^ 0 = 0 (当前位值为 0)

#### 交换两个数 ####

使用 ^位运算符的特性，不使用临时变量实现两个数的交换。

a ^= b;
    b ^= a;
    a ^= b;

a=10,b=1  
a=11  
b=10  
a=1

eg a=10,b=10,c=a^b=0,可以实现相加的效果，但是没有进位的效果

因此 ^ & <<可以一起实现+的效果  
题目链接

*  [剑指 Offer 65. 不用加减乘除做加法 - 力扣（LeetCode）][Offer 65. _ - _LeetCode]

public int add(int a, int b) {
          
        while(b != 0){
          
            int temp = a ^ b;//计算出相对应的位置相加后的结果,非进位和  
            b = (a & b) << 1;//计算出想对应的位置的进位，然后左移一位  
            a = temp;  
        }  
        return a;  
    }

### LeetCode ###

*  [位运算知识点题库 - 力扣（LeetCode）][- _LeetCode]
 *  [两数相除 - 两数相除 - 力扣（LeetCode）][- _ - _LeetCode]

[8d9b6ae7b0f7443798ea2e6aef43aa58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a7179b27996c49c2b1b6c2b51ced6b89.png
[e4c5d1b89675468ab71e2cc5e8be5c8e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/cd3327464823474682017c72b600f983.png
[402499e5def14dbbbbf2c737daf10f26.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a99b8c91fa4e44fc98cd09a7530de882.png
[2bd21f3110b746ec921cf5c13bb7e37c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/26479e727a1447a1b6c167c16dcef906.png
[437bbf9f5aa44fb6848208946bdbfddf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/72032929387448269d9fc0cd7387aa10.png
[868b884c7c914740aa8e6eadbabffd8b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8655bf7480b54d8b8537a238809d3099.jpeg
[e1e492d084c662099930b5524cb5d527.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f6a5e39205ae4a61b98ae3611ae80f8f.png
[2931ed241095b767fb57f3ed8f2b5ca4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/285b110b330e4e8d8b9eceea99ae68d7.png
[71607622792e4301a6589f5168316077.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/b52a764ba15b434fbe2211c432b43187.png
[07a2a58f55e7eaf5cf8be865bbe4ecb0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/0c59554c3bd847bd9a38db5356e56d6e.png
[3d963bde3b73aef3bfc7fdb342741526.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/6b36815a82064033b832fe2a3a136076.png
[590fe95de47742845a5eb929322690c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/54353c6d1da343c5898b2c576bbc9c53.png
[b6b40fdfb3ef2fcdf1a4debcd66b61ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f6b332faabc34e51bbe0a85ebc594572.png
[d54ce3f5efd1d940f4d6c86ba57691f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/4daf90bbab794a93bb3451651db1dae1.png
[6f2125b7caa6246d3989f8c6fc869921.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/11982507bc514b38b0680729295ed48e.png
[4f4e537eb32de20ab2179a2fc02151f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f041593ac7534a09957dc3d54e00cf77.png
[649675ffa12dfcd1255073a9ad26cf4a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/502fcb2bc61c4cc7bbcd85598847cca0.png
[Loading Question_ - _LeetCode]: https://leetcode.cn/problems/number-of-1-bits/
[Offer 65. _ - _LeetCode]: https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/
[- _LeetCode]: https://leetcode.cn/tag/bit-manipulation/problemset/
[- _ - _LeetCode]: https://leetcode.cn/problems/divide-two-integers/solution/liang-shu-xiang-chu-by-leetcode-solution-5hic/