数学解题技巧

加减乘除求余
边界问题
位运算
数学方法
整型方法
正负判断
进制
幂运算

位运算

基本的位运算知识：

// 与运算（&）
0 & 0 = 0;
1 & 1 = 1;
1 & 0 = 0;

// 或运算（|）
0 | 0 = 0;
1 | 0 = 1;
1 | 1 = 1;

// 异或运算（^）
1 ^ 1 = 0;
1 ^ 0 = 1;
0 ^ 0 = 0;

常用技巧：

n & (n - 1) 能够消灭 n 中最右侧一个 1
右移：除以 2；左移：乘以 2
异或性质：交换律，0 ^ n = n，n ^ n = 0
我们可以将常用字符、数字等均转为按位运算，可以节约空间

位运算常用技巧

操作说明	变化	操作
去掉最后一位	`101101` -> `10110`	`n >> 1`
在最后加一个 0	`101101` -> `1011010`	`n << 1`
在最后加一个 1	`101101` -> `1011011`	`(n << 1) + 1`
把最后一位变成 1	`101100` -> `101101`	`n \| 1`
把最后一位变成 0	`101101` -> `101100`	`(n \| 1) - 1`
最后一位取反	`101101` -> `101100`	`n ^ 1`
把右数第 K 位变成 1	`101001` -> `101101`（`k=3`）	`n \| (1 << (k-1))`
把右数第 K 位变成 0	`101101` -> `101101`（`k=3`）	`n & ~(1 << (k-1))`
右数第 k 位取反	`101001` -> `101101`（`k=3`）	`n ^ (1 << (k-1))`
取末三位	`1101101` -> `101`	`n & 7`
取末 k 位	`1101101` -> `1101`（`k=5`）	`n & (1 << k-1)`
取右数第 k 位	`1101101` -> `1`（`k=4`）	`n >> (k-1) & 1`
把末 k 位变成 1	`101001` -> `101111`（`k=4`）	`n \| (1 << k-1)`
末 k 位取反	`101001` -> `100110`（`k=4`）	`n ^ (1 << k-1)`
把右边连续的 1 变成 0	`100101111` -> `100100000`	`n & (n + 1)`
把右起第一个 0 变成 1	`100101111` -> `100111111`	`n \| (n + 1)`
把右边连续的 0 变成 1	`11011000` -> `11011111`	`n \| (n - 1)`
取右边连续的 1	`100101111` -> `1111`	`(n ^ (n + 1)) >> 1`
去掉右起第一个 1 的左边	`100101000` -> `1000`	`n & (n ^ (n - 1))`

左移运算

a << b 的值实际上就是 a 乘以 2 的 b 次方，a << b 表示把 a 转为二进制后左移 b 位（在后面添加 b 个 0）。

右移运算

a >> b 表示二进制右移 b 位（去掉末 b 位），相当于 a 除以 2 的 b 次方（取整）。

进位

const v1 = 9,
  v2 = 9,
  carry = 0,
  remainder = 0;

// 总数
const total = v1 + v2 + carry;
// 进位
carry = Math.floor(total / 10);
// 当前位数值
remainder = total % 10;

Data Structure and Algorithms Guidebook

数学解题技巧

位运算

位运算常用技巧

相关题目

进位