# 位运算


## ***前言***

*本文分三个部分*

1. *有趣的位运算* 

2. *算法比较常用的 n & (n - 1)*

3. *算法例题*

## ***位运算符***

```c
左移                <<        0011 -> 0110

右移                >>        0110 -> 0011

按位或      |      0011
                                       -----> 1011
                                1011

按位与      &     0011
                                      -----> 0011
                               1011

按位取反   ~      0011 -> 1100

按位异或   ^      0011
                                      -----> 1000
                 1011
```

## ***XOR 异或***

```go
异或: 相同为0 不同为1 也可用 "不进位加法" 来理解
  异或操作的一些特点:    
  x ^ 0 = x
  x ^ 1s = ~x  // 注意 1s = ~0
  x ^ (~x) = 1s   x ^ x = 0
  c = a ^ b  => a ^ c = b, b ^ c = a  // 交换两个数
  a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c  // associative
```

## ***有趣的位运算***

### ***将x最右边的n位清零***

```json
x & (~0 << n)
```

### ***获取x的第n位值 (0 或者 1)***

```json
(x >> n) & 1
```

### ***获取x的第n位的幂值***

```json
 x & (1 << (n - 1))
```

### ***仅将第n位置为1***

```json
x | (1 << n)
```

### ***仅见第n位置为0***

```json
x & (~(1 << n))
```

### ***将x最高位至第n位 (含)清零***

```json
x & ((1 << n) -1)
```

### ***将第n位至第0位***

```json
 x & (~((1 << (n-1))-1))
```

### ***判断奇偶***

```go
x % 2 == 1 ---> (x & 1) == 1
x % 2 == 0 ---> (x & 1) == 0
```

### ***x >> 1 ---> x / 2***

```json
即 x = x/2; ---> x = x >> 1;
```

### ***得到最低位的1***

```json
X & -X
```

### ***X & ~X -> 0***

```json
 X & ~X -> 0
```

### ***将英文字符串转为大小写***

```go
大写变小写、小写变大写 : 字符 ^= 32;

大写变小写、小写变小写 : 字符 |= 32;

小写变大写、大写变大写 : 字符 &= -33;

/*
  以上操作能够产生奇特效果的原因在于 ASCII 编码
  字符其实就是数字，恰巧这些字符对应的数字通过位运算就能得到正确的结果，有兴趣的读者可以查 ASCII 码表自己算算，本文就不展开讲了
*/
```

### ***判断两个数是否异号***

```c
int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true

int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false
```

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

```c
int a = 1, b = 2;a ^= b;b ^= a;a ^= b;
```

### ***加1***

```c
int n = 1;n = -~n;
```

### ***减1***

```c
int n = 2;n = ~-n;
// 现在 n = 1
```

## ***算法常用操 n&(n-1)***

```c
这个操作是算法中常见的，作用是消除数字 n 的二进制表示中的最后一个 1
```

### ***例题1 - 二进制中的1的个数***

[LCR 133. 位 1 的个数 - 力扣（LeetCode）](https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/)

```go
思路详解：
    `就是让你返回 n 的二进制表示中有几个 1
        因为 n & (n - 1) 可以消除最后一个 1，所以可以用一个循环不停地消除 1 同时计数，直到 n 变成 0 为止
```

```c
int hammingWeight(uint32_t n) {
    int res = 0;
    while (n != 0) {
        n = n & (n - 1);
        res++;
    }
    return res;
}
```

## ***题目推荐***

### ***例题1 - 插入***

1. ***题目url***
   
   - *[面试题 05.01. 插入 - 力扣（LeetCode）](https://leetcode.cn/problems/insert-into-bits-lcci/)*

2. ***解题思路***
   
   - *先将N的第i ~ j位全部置零；*
   - *在将M左移i位，使之对其上一步中N置零的位，直接相加即可。*

3. ***示例代码***
   
   - ```c
     class Solution {
     public:
         int insertBits(int N, int M, int i, int j) {
             for (int k = i; k <= j; ++ k)
             {   //举例说明： (1 << 3) 表示 00001000，取反后得 11110111
                 // N &= (11110111) 表示将 N 的第3位置零了
                 N &= ~(1 << k);
             }
     
             return N + (M << i);
         }
     };
     ```

### ***例题2 - 翻转数位***

1. ***题目url***
   
   - *[面试题 05.03. 翻转数位 - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-bits-lcci/)*

2. ***方法1 - 位运算***
   
   - ```c
     /*
       在遍历num每一位时，追踪当前1序列的长度和上一段1序列的长度；
     
       当遇到比特位为0时，分两种情况讨论：
       1、若下一个比特位为1，那么preLen = curLen；
       2、若下一个比特位为0，那么preLen = 0，我们不能合并这两个1序列
     */
     class Solution {
     public:
         int reverseBits(int num) {
             if (~num == 0) return 32;                       //全是1的情况，若不特判会输出33
             int curLen = 0, preLen = 0；
             int maxLen = 1;                                 //最少也能翻转1位
             for (int i = 0; i < 32; ++ i) {
                 if ((num & 1) == 1) {
                     curLen ++ ;
                 }
                 else {
                     preLen = ((num & 2) == 0) ? 0 : curLen; //判断下一比特位是否为0
                     curLen = 0;
                 }
     
                 maxLen = max(maxLen, preLen + curLen + 1);
                 num >>= 1;
             }
             return maxLen;
         }
     };
     ```