位运算技巧

目录

定义：六种常见的位运算（来自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 的模运算，性能会更好一些。

利用 n & (n-1) 的应用

n & (n-1) 这个操作是算法中常见的，作用是 消除 n 数字的二进制表示 中的最后一个 1 ，见下图：

image.png|504

第 191 题「位 1 的个数」：计算汉明权重（Hamming Weight）

image.png|584

// 用一个循环不停地消除 1 同时计数，直到 n 变成 0 为止
var hammingWeight = function(n) {
    var res = 0;
    while (n != 0) { 
        n = n & (n - 1); 
        res++;
    }
    return res;
};

第 231 题「2 的幂」：判断一个数是不是 2 的指数

一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1

2^0 = 1 = 0b0001
2^1 = 2 = 0b0010
2^2 = 4 = 0b0100

一个数如果是 `2 的指数`，那么它的二进制表示一定`只含有一个 1`
var isPowerOfTwo = function(n) {
    if (n <= 0) return false; // 注意是小于等于
    return (n & (n - 1)) === 0; // 注意运算符优先级，括号不可以省略
};

a ^ a = 0 ; a ^ 0 = a 的运用

异或运算的性质是需要我们牢记的：

  • 一个数和它本身做异或运算结果为 0，即 a ^ a = 0；
  • 一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a

第 136 题「只出现一次的数字」：查找只出现一次的元素

image.png|544

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let res = 0;
    nums.forEach((num)=>{
        console.log(res,num);
        res = res ^ num; 
    
    })
    return res;
};


singleNumber([4,1,2,2,1,4,5])
0 4
4 1
5 2
7 2
5 1
4 4
0 5

第 268 题「丢失的数字」：：寻找缺失的元素

image.png|560

常规解法

  • 排序 + 遍历：很容易找到缺失的元素
  • hashSet + 遍历 ：用一个 HashSet 把数组里出现的数字都储存下来，再遍历[0,n]之间的数字，去 HashSet 中查询是否存在

利用数学公式

image.png|560

位运算：使用异或运算

或运算满足交换律和结合律
2 ^ 3 ^ 2 = 3 ^ (2 ^ 2) = 3 ^ 0 = 3

以 nums = [0,3,1,4] 为例：

image.png|536

如何找这个落单的数字呢，只要把所有的元素和索引做异或运算，成对儿的数字都会消为 0，只有这个落单的元素会剩下，也就达到了我们的目的

由于异或运算满足交换律和结合律，所以总是能把成对儿的数字消去，留下缺失的那个元素。

var missingNumber = function(nums) {
    const n = nums.length;
    let res = 0;
    // 先和新补的索引异或一下
    res ^= n;
    // 和其他的元素、索引做异或
    for (let i = 0; i < n; i++)
        res ^= i ^ nums[i];
    return res;
}