# 位运算以及位图

计算机中的数在内存中都是以二进制形式进行存储的，用位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。

## 位操作符

### 与&

```
1 0 0 1 1 
1 1 0 0 1 
------------------------------
1 0 0 0 1

与运算 两个位都是 1 时，结果才为 1，否则为 0
```

### 或 |

```
1 0 0 1 1 
1 1 0 0 1 
------------------------------
1 1 0 1 1

或运算 两个位都是 0 时，结果才为 0，否则为 1
```

### 异或运算 ^

**即无进位相加**

```
1 0 0 1 1 
1 1 0 0 1 
-----------------------------
0 1 0 1 0

异或运算，两个位相同则为 0，不同则为 1
```

1. `0 ^ N = N`, `N ^ N = 0`
2. 异或运算满足交换律与结合律

> 使用无进位相加理解上述两个性质非常容易

### 取反运算 \~

```
1 0 0 1 1 
-----------------------------
0 1 1 0 0

取反运算，0 则变为 1，1 则变为 0
```

### 左移运算 <<

```
int a = 8;
a << 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0100 0000

左移运算，向左进行移位操作，高位丢弃，低位补 0
```

* 对一个数进行左移一次相当于 `* 2`
* 左移n次，相当于`* (2 ^ n)`

### 右移运算 >>

```
unsigned int a = 8;
a >> 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0000 0001

右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位
```

* 对一个数右移一次相当于 `/ 2`
* 右移n次，相当于 `/ (2 ^ n)`

### 无符号右移运算 >>>

```
unsigned int a = -1;
a >>> 1;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0000 0001

无符号右移运算，向右进行移位操作，高位补 0
```

## 负数的表示

计算机32位int值，如果是无符号整型，可以表示的数字范围位`0 ~ 2^32-1`，如果是有符号整型，可表示的数字范围为`-2^31 ~ 2^31-1`，包含0，他们都共可以表示 `2 ^ 32`个数字。

无符号整型将所有32位都作为值存储，而有符号整型则将最高位作为符号位，当符号位为0代表该数字为非负数（可能为0以及正数），如果符号位数字为1，代表该数字为负数，比如在Java中：

```java
print(Integer.MAX_VALUE); // 01111111111111111111111111111111  int最大值 正值
print(Integer.MIN_VALUE); // 10000000000000000000000000000000  int最小值 负值
print(1);  // 00000000000000000000000000000001
print(-1); // 11111111111111111111111111111111
```

负数二进制表示的计算：

```
假设负数 -1：
最高位也就是符号位为1，也就是 100....00
后面的31位表示数字值，对绝对值使用取反加一计算：
原值 => 100....01 
取反 => 111....10
加一 => 111....11  这个值就是 -1 的二进制表示

----------

假设负数位 Integer最小值也就是 -2^31
最高位也就是符号位为1，也就是 100....00
后面的31位表示数字值，对绝对值使用取反加一计算：
原值 => 1100....000 注意，这里溢出一位
取反 => 1011....111
加一 => 1111....111
结果 => 1111....11 溢出的一位直接去除，这个值就是 -2^31的二进制表示
```

**取反加一就是二进制的补码。**

**为什么负数要使用二进制补码的形式？**

> 参考：<https://blog.csdn.net/leonliu06/article/details/78685197>
>
> 总结：一种巧妙地设计，也是一种规定，为了提高二进制计算的效率

## 常见的位运算问题

### 32位int转换为二进制字符串

```java
/**
 * 打印数字的二进制表现字符串
 */
public static void print(int num) {
  for (int i = 31; i >= 0; i--) {
    System.out.print((num & (1 << i)) == 0 ? "0": "1");
  }
  System.out.println();
}
```

> 说明：便利32位int的每一位，将每位的状态打印。比如，第一位与 `100....00`相与，可得到该数第一位的状态；第二位与`0100...0`相与，可得到第二位的状态，一直到第最后一位，从 31 到 0。

### 交换数字（异或）

```java
a ^= b;
b ^= a;
a ^= b;
```

**原理：**

```java
int a = x;
int b = y;
a ^= b;  // a = x ^ y;
b ^= a;  // b = y ^ x ^ y;   b = x;
a ^= b;  // a = x ^ y ^ x;   a = y;
```

**注意：**

```java
public static void swap(int[] arr, int i, int j) {
  arr[i] ^= arr[j];
  arr[j] ^= arr[i];
  arr[i] ^= arr[j];
}
swap(arr, 0, 1); // 正确
swap(arr, 0, 0); // 错误，arr[i] 与 arr[j] 会都变为0，这是因为arr[i] 与 arr[j] 共用一块内存，如下
// arr[i] ^= arr[j]; // arr[i] = x ^ x;     arr[i] = 0;
// arr[j] ^= arr[i]; // arr[j] = 0 ^ 0;     arr[j] = 0; 
// arr[i] ^= arr[j]; // arr[i] = 0 ^ 0;     arr[i] = 0;
```

### 判断奇偶数

```c
if(0 == (a & 1)) {
 //偶数
}
```

### 正负切换（补码）

```c
int reversal(int a) {
  return ~a + 1;
}
```

### 绝对值

```c
int abs(int a) {
  int i = a >> 31; // 获取符号位
  return i == 0 ? a : (~a + 1); // 符号位为0=>正数不变返回，符号位为1=>负数取反加一返回
}
```

### 高低位交换

```
34520的二进制表示：
10000110 11011000

将其高8位与低8位进行交换，得到一个新的二进制数：
11011000 10000110
其十进制为55430
```

```c
unsigned short a = 34520;
a = (a >> 8) | (a << 8);
// 1. a >> 8 得到高8位  00000000 10000110
// 2. a << 8 得到低8位  11011000 00000000
// 3. (a >> 8) | (a << 8) 得到 11011000 10000110
```

### 统计二进制中 1 的个数

```java
/**
 * 统计二进制数中1的个数
 */
public static int count(int num) {
  int count = 0;
  for (int i = 31; i >= 0; i--) {
    count += (num & (1 << i)) == 0 ? 0 : 1;
  }
  return count;
}
```

统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 `a &= (a-1)`的结果：

* 第一次：计算前：`1000 0110 1101 1000` 计算后：`1000 0110 1101 0000`
* 第二次：计算前：`1000 0110 1101 0000` 计算后：`1000 0110 1100 0000`
* 第二次：计算前：`1000 0110 1100 0000` 计算后：`1000 0110 1000 0000` 我们发现，没计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：

```c
count = 0  
while(a){  
  a = a & (a - 1);  
  count++;  
}  
```

### 位运算实现加减乘除

计算机底层都是使用位运算实现加减乘除。

#### 加法

```
a = 46; => 0010 1110
b = 20; => 0001 0100

// 使用异或获取无进位相加的结果
a ^ b   => 0011 1010  => 58
// 由上面可知，进位信息位于第三位
// 可以使用先&获取同为1的位置，再左移获取进位信息
a & b   => 0000 0100
a & b << 1 => 0000 1000  => 8
// 加法和就等于 无进位相加和 + 进位
58 + 8 = 66

// 继续使用上述方式计算 58 + 8
a = 58; => 0011 1010
b = 8;  => 0000 1000
a ^ b;  => 0011 0010 => 50
a & b;  => 0000 1000
a & b << 1 => 0001 0000 => 16

// 继续使用上述计算方式计算 50 + 16 
a = 50; => 0011 0010
b = 16; => 0001 0000
a ^ b;  => 0010 0010; => 34
a & b;  => 0001 0000;
a & b << 1; => 0010 0000; => 32

//继续使用上述计算方式计算 34 + 32
a = 34; => 0010 0010;
b = 32; => 0010 0000;
a ^ b;  => 0000 0010;  => 2
a & b;  => 0010 0000; 
a & b << 1; => 0100 0000; =>  64

// 继续使用上述计算方式计算 64 + 2
a = 64; => 0100 0000;
b = 2;  => 0000 0010;
a ^ b;  => 0100 0010; => 66
a & b;  => 0000 0000;
没有进位，那么此时a ^ b 的结果就是该加法的结果。
```

java实现：

```java
public static int add(int a, int b) {
  int sum = a;
  while (b != 0) {
    sum = a ^ b;
    b = (a & b) << 1;
    a = sum;
  }
  return sum;
}
```

#### 减法

```java
// 减法就是 a + (-b)， 一个数的相反数可以用 ~b + 1来表示
public static int minus(int a, int b) {
  return add(a, add(~b, 1));
}
```

#### 乘法

乘法的实现方式是乘法的竖式表达程序化：

```
  23
x 12
----
  46
 23
----
 276
 
二进制表现相同：
    10111
x    1100
-----------
    00000
   00000
  10111
 10111
-----------
100010100   =>  276
```

程序化：

```java
// 乘法
public static int multi(int a, int b) {
  int bi;
  int result = 0;
  int count = 0;
  while (count < 32) {
    bi = b & (1 << count);
    if (bi != 0) {
      result = add(result, a << count);
    }
    count++;
  }
  return result;
}

// 乘法更简单的实现
// b每次向右侧移动一位，即可取到某位的状态
public static int multi2(int a, int b) {
  int res = 0;
  while (b != 0) {
    if ((b & 1) != 0) {
      res = add(res, a);
    }
    a <<= 1;
    b >>>= 1;
  }
  return res;
}
```

#### 除法

```
举例说明
41 / 3
3 * 2 ^ 0 = 3 < 41
3 * 2 ^ 1 = 6 < 41
3 * 2 ^ 2 = 12 < 41
3 * 2 ^ 3 = 24 < 41
3 * 2 ^ 4 = 48 > 41 

商=2^3
对余数继续除：
41 - 24 = 17
17 / 3 
3 * 2 ^ 0 = 3  < 17 
3* 2 ^ 1 = 6 < 17
3 * 2 ^ 2 = 12 < 17 
3 * 2 ^ 3 = 24 > 17 

商 =  2^3 + 2^2
对余数继续除
17 - 12 = 5 
3 * 2 ^ 0 = 3 < 5
3 * 2 ^ 1 = 6 > 5

商 = 2^3 + 2^2 + 2^0 
5 - 3 = 2
2 < 3 不继续除

所以，41 / 3 = 2^3 + 2^2 + 2^0 = 13
```

使用除2的方式是因为2可以使用位运算替代。这种方式实际就是不断的减去被除数，并计算被减的次数。

Java代码实现如下：

```java
```

### 控制某一位

假设有二进制数`1011 0110`：

1. 控制这个二进制数的最高位变为0：

   ```
    1011 0110
   &0111 1111
    0011 0110
   ```
2. 控制这个二进制数的最低位变为1：

   ```
    1011 0110
   |0000 0001
    1011 0111
   ```

java实现：

```java
/**
 * 设置二进制数的某一位
 * @param num 二进制数
 * @param pos 位置
 * @param flag true => 1， false => 0
 */
public static int set(int num, int pos, boolean flag) throws IllegalArgumentException{
    if (pos < 0 || pos > 31) {
        throw new IllegalArgumentException();
    }
    if (flag) {
        num |= (1 << pos);
        return num;
    }
    
    num &= ~ (1 << pos);
    return num;
}
```

### 位图的实现

Java:

```java
static class BitMap {
  // 1个long类型可以存储64位
  // 使用一个long类型数组存储bit位图
  private final long[] bits;

  // 根据max确定数组的长度
  // 如果 max 属于 0 ~ 63 则数组长度为1
  // 如果 max 属于 0 ~ 127 则数组长度为2
  public BitMap(int max) {
    if (max < 0) throw new IllegalArgumentException();
    bits = new long[(max + 64) >> 6]; // 等同于 (size + 64) / 64
  }

  // 将某个位置置为1，位置索引从0开始
  public void add(int num) {
    // 1. 确定num位置属于数组的第几个整数元素： 0/64=0, 64/64=1, 127/64=1, 128/64=2
    //    故元素位置= num / 64 也就是  num >> 6
    // 2. 确定num位于已确定的整型元素的第几位： 0%64=0, 1%64=1, 127%64=63, 128%64=0
    //    故num位置位于整型元素的第  num%64位。num%64 等同于 num&63：
    //    num%64等同于只保留二进制的最后6位，前面的位数全部去除，所以 num & 63 = num % 64
    // 3. 将指定位置1，使用 |，比如将第2位置1 
    //    0000 | 0100 = 0100
    //    0100 => 1 << (num & 63)
    // 故结果如下：
    bits[num >> 6] |= (1L << (num & 63));
  }

  public void delete(int num) {
    // 1. 确定num位置属于数组的第几个整数元素: num >> 6
    // 2. 确定num位于已确定的整型元素的第几位: num % 64 => num & 63
    // 3. 将指定位置0，使用&，比如将第二位置0
    //    1111 & 1011 = 1011
    //    1011 => ~0100
    // 故结果如下
    bits[num >> 6] &= ~(1L << (num & 63));
  }

  public boolean contains(int num) {
    // 1010 & 0100 => 0000 说明第二位是0，否则第二位是1
    return (bits[num >> 6] & (1L << (num & 63))) != 0;
  }
}
```

## 面试题

### 异或

**一个数组中有一个数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这个数字？**

```java
// 给定数组 [4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 2, 1, 4]
// 其中 1共有4个，2共有3个，3共有4个，4共有2个
// 找到个数为奇数的数字，也就是2
// 使用异或
public static void main(String[] args) {
  int[] arr = {4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 2, 1, 4};
  int t = 0;
  for (int i = 0; i < arr.length; i++) {
    t ^= arr[i];
  }
  System.out.println(t); // 2
}
```

原理：

1. 满足交换律，所以 `4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 2, 1, 4`即为：`1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4`
2. 相同的数字异或为0， 所以上述数字偶数个的都会被异或为0，奇数个的最中会剩余一个数字

***

**怎么将一个int类型的数，提取出他二进制最右侧的1来？**

```java
public static void main(String[] args) {
  int N = 200;
  System.out.println(Integer.toBinaryString(N)); // 11001000

  // 提取最右侧的1，使用公式：N & ((~N) + 1)
  int result = N & ((~N) + 1);
  System.out.println(Integer.toBinaryString(result)); // 1000
}
```

推算过程：

```
原数 .... 0000 0000 1100 1000
取反 .... 1111 1111 0011 0111
加一 .... 1111 1111 0011 1000
相与 .... 0000 0000 0000 1000
```

***

**一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数？**

```java
// 假设两个奇数为 a 和 b
// eor = 将数组中所有元素相互异或
// eor = a ^ b != 0
// 因为eor != 0，故eor 在至少有一个位置上一定有1，所以 a 和 b 在这些位置上的 0 与 1 的状态一定不一致
// 取eor出最右侧的1，与数组的所有元素相与，可以得出该位置为1的所有元素，其中一定含有 a 或者 b
// 将这些元素再次相互异或，可以得到 a 或者 b， 根据 eor = a ^ b; a = eor ^ b; 故而得到 a 和 b
// 代码如下：
// 假设两个奇数为 a 和 b
// eor = 将数组中所有元素相互异或
// eor = a ^ b != 0
// 因为eor != 0，故eor 在至少有一个位置上一定有1，所以 a 和 b 在这些位置上的 0 与 1 的状态一定不一致
// 取eor出最右侧的1，与数组的所有元素相与，可以得出该位置为1的所有元素，其中一定含有 a 或者 b
// 将这些元素再次相互异或，可以得到 a 或者 b， 根据 eor = a ^ b; a = eor ^ b; 故而得到 a 和 b
// 代码如下：
public static void printOddNum2(int[] arr) {
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    int rightOne = eor & (~eor + 1);
    int aOrB = 0;
    for (int i = 0; i < arr.length; i++) {
        if ((arr[i] ^ rightOne) == 0) {
            aOrB ^= arr[i];
        }
    }
    System.out.println(aOrB + "  " + (eor ^ aOrB));
}
```

***

**找到数字N的二进制的含有1的数量？**

```java
// 以rightOne作为判断条件
public static int bit1Count(int n) {
   int count = 0;
   int rightOne;
   while (true) {
     // 找到最右侧的1
     rightOne = n & (~n + 1);
     if (rightOne == 0) {
       return count;
     }
     count ++;
     // 抹掉最右侧的1
     n ^= rightOne;
   }
 }

// 以n数字作为判断条件
public static int bit1Count2(int n) {
  int count = 0;
  int rightOne;
  while (n != 0) {
    // 找到最右侧的1
    rightOne = n & (~n + 1);
    count ++;
    n ^= rightOne;
  }
  return count;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa/wei-yun-suan-yi-ji-wei-tu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.