位运算技巧

#算法/位运算

`定义：`六种常见的`位运算`（来自GPT）

位运算是对整数在二进制形式下的每一位(bit)进行的运算。这些运算通常比标准的算术或逻辑运算要快，因为它们直接在CPU中进行。以下是几种常见的位运算类型及其说明：

按位与（AND）：
- 符号：&
- 规则：两个位都为1时，结果为1；否则为0。
- 例子：1010 & 1100 = 1000
按位或（OR）：
- 符号：|
- 规则：两个位中只要有一个为1，结果就为1；如果都不为1，结果就为0。
- 例子：1010 | 1100 = 1110
按位异或（XOR）：可理解为相减的绝对值
- 符号：^
- 规则：两个位不相同时，结果为1；相同时为0。
- 例子：1010 ^ 1100 = 0110
按位取反（NOT）：
- 符号：~
- 规则：将位中的0变成1，1变成0。
- 例子：~1010 = 0101（假设是4位二进制数）
左移（Left Shift）：
- 符号：<<
- 规则：将二进制全部位向左移动指定的位数，右边空出的位用0填充。
- 例子：1010 << 2 = 101000
右移（Right Shift）：
- 符号：>>
- 规则：有两种右移，逻辑右移和算术右移。逻辑右移将二进制全部位向右移动指定的位数，左边空出的位用0填充；算术右移在许多系统中会保留符号位（即最左边的位），所以如果是正数左边填充0，负数左边填充1。
- 例子（逻辑右移）：1010 >> 2 = 0010
- 例子（算术右移）：如果是负数，例如 -1010 >> 2 在32位系统中可能会得到 11111111111111111111111111111010

这些位运算在低级编程、硬件设计、加密算法等领域中非常有用，因为它们可以高效地直接操作数据的二进制表示。

几个有趣的位操作

转成大写，转成小写或者大小写互换

记忆技巧：

大写：AND，转大写，条件严格些
小写：OR，转小写，条件宽松些
异或：XOR，大小写 VR 换


利用或操作 | 和空格将英文字符转换为小写

('a' | ' ') = 'a'
('A' | ' ') = 'a'

利用与操作 & 和下划线将英文字符转换为大写

('b' & '_') = 'B'
('B' & '_') = 'B'

利用异或操作 ^ 和空格进行英文字符大小写互换

('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'

大小写转化比如('b' & '_') = 'B' 或其他的，本质是因为ASCII 字符其实就是数字，做运算刚好转了，具体的不用记住

不用`临时变量`就能交换两个值，使用`位运算`

image.png|396

判断两个数是否异号，用`^` 来判断是否大于 0

image.png|282

原理：
- 利用的是补码编码的符号位。整数编码最高位是符号位，负数的符号位是 1，非负数的符号位是 0，
- 再借助异或的特性，可以判断出两个数字是否异号
其他方法
- 乘积来判断两个数是否异号，但是这种处理方式容易造成整型溢出从而出现错误。
- 逻辑运算： a>0 & b<0 || a<0 & b>0

使用`～` 来 `加一` 或者`减一`

加一
int n = 1;
n = -~n;
// 现在 n = 2

减一
int n = 2;
n = ~-n;
// 现在 n = 1

环形数组：`index & (arr.length - 1)` 的运用

如何实现让数组看起来头尾相接形成一个环形 ？

1,2,3,4 , 1,2,3,4, 1,2,3,4...

方法一：使用 `%` 求模

var arr = [1, 2, 3, 4];
var index = 0;
while (true) {
    // 在环形数组中转圈
    console.log(arr[index % arr.length]);
    index++;
}
// 输出：1,2,3,4,1,2,3,4,1,2,3,4...

方法二：使用 `index & (arr.length - 1)`

var arr = [1,2,3,4];
var index = 0;
while (true) {
    // 在环形数组中转圈
    console.log(arr[index & (arr.length - 1)]);
    index++;
}
// 输出：1,2,3,4,1,2,3,4,1,2,3,4...

两点说明

注意这个技巧只适用于数组长度是 2 的幂次方的情况，

简单说，& (arr.length - 1) 这个位运算能够替代 % arr.length 的模运算，性能会更好一些。

liguwe's site