二进制位运算

判断奇偶性

奇数的二进制, 末位一定为1 ``` bool isOdd(int n) { return (i & 1) == 1; }

## 乘除运算
- 乘法通项: a * b = a << (b >> 1) + a << (b % 2);
- 除法通项: a / b = a >> (b >> 1) + a >> (b % 2); 有误差
## 判断一个数是否为2的正整数幂

bool isPowerOfTwo(int n) { return (n & (n - 1)) == 0; }

## 对2^n取模
- 对 n 取模 结果永远不会大于 n - 1, 对 n - 1进行按位与运算, 结果最大就是 n - 1

int modPowerOfTwo(int i, int n) { return i & ((1 << n) - 1); }

## 快速幂取模
- 定理: (a * b) mod c = ( (a mod c) * (b mod c) ) mod c

long long (long long a, long long b, long long mod) { long long ret = 1; while (b) { if (b & 1) { ret = (ret a) % mod; } a = (a a) % mod; b >>= 1; } return ret % mod; }

## 提取某段二进制

int x = 0x7f; //0111 1111 int ret = x & ( (1 << 6) - 1 ); //提取后 6 位数据 int ret = x & ( (1 << n) - 1 ); //提取后 n 位数据

## 计算二进制数1的个数

int count_one(int n) { int cnt = 0; while (x) { x &= x - 1; cnt++; } return cnt; }

## 求某范围内唯一重复的一个数

int a[11]; for (int i = 0; i < 10; i++) { a[i] = i + 1; } a[10] = rand() % 11; for (int i = 0; i < 11; i++) { cout << a[i] << ‘ ‘; } int k = a[0]; for (int i = 1; i < 11; i++) { k ^= a[i]; } for (int i = 1; i <= 10; i++) { k ^= i; } cout << endl << k;

测试结果: 1 2 3 4 5 6 7 8 9 10 8 8

```

二进制 位运算

二进制 位运算

二进制 位运算

判断奇偶性

二进制位运算

二进制位运算

二进制位运算