你不知道的位运算

在JavaScript中，位运算是一种直接操作二进制位的强大工具。尽管在日常开发中使用较少，但在某些性能优化或特定场景下，位运算能够提供高效且独特的解决方案。然而，理解位运算的基础并不简单，尤其是当我们处理负数时。因此，在深入探讨“与、或、非、异或”等位运算操作之前，我们需要了解一个重要概念：补码。

补码与位运算

计算机在处理负数时，使用的是一种称为“补码”的表示法，而不是直接操作原码。补码是一种在二进制系统中表示有符号数的方法，它解决了加减运算中对负数的处理问题。

• 正数的补码与其原码相同。
• 负数的补码是将其绝对值的二进制形式按位取反后加1。

例如，8位二进制中：

• 5 的补码表示为 00000101。
• -5 的补码表示为 11111011（取反加一）。

现在我们已经了解了补码，让我们来看具体的位运算操作。

位运算的基本操作

1. 与（AND）

位运算“与”使用符号 &，它将两个数字的二进制位进行按位与操作。只有当对应位都是1时，结果位才为1，否则为0。

let a = 5;  // 二进制：0101
let b = 3;  // 二进制：0011
let result = a & b;  // 结果：0001，即 1
console.log(result); // 输出 1

2. 或（OR）

位运算“或”使用符号 |，它将两个数字的二进制位进行按位或操作。只要有一个对应位为1，结果位就为1。

let a = 5;  // 二进制：0101
let b = 3;  // 二进制：0011
let result = a & b;  // 结果：0111，即 7
console.log(result); // 输出 1

3. 非（NOT）

位运算“非”使用符号 ~，它将数字的每个位进行取反操作。即0变1，1变0。

let a = 5;  // 二进制：0101
let result = ~a;  // 结果：1010，即 -6（补码表示）
console.log(result); // 输出 -6

注意：由于JavaScript使用补码表示负数，因此取反操作后的结果会是补码形式的负数。

4. 异或（XOR）

位运算“异或”使用符号 ^，它将两个数字的二进制位进行按位异或操作。当对应位不同时，结果位为1，否则为0。

let a = 5;  // 二进制：0101
let b = 3;  // 二进制：0011
let result = a ^ b;  // 结果：0110，即 6
console.log(result); // 输出 6

位移操作

位移操作用于将数字的二进制位左移或右移。

1. 左移（<<）

左移操作符 << 会将一个数的二进制位向左移动指定的位数，右侧用0填充。左移操作等价于乘以2的n次方。

let a = 5;  // 二进制：0101
let result = a << 1;  // 结果：1010，即 10
console.log(result); // 输出 10

2. 右移（>>）

右移操作符 >> 会将一个数的二进制位向右移动指定的位数，左侧用符号位填充。右移操作等价于除以2的n次方（向下取整）。

let a = 5;  // 二进制：0101
let result = a >> 1;  // 结果：0010，即 2
console.log(result); // 输出 2

3. 无符号右移（>>>）

无符号右移操作符 >>> 会将一个数的二进制位向右移动指定的位数，左侧用0填充，不考虑符号位。适用于无符号数的右移。

let a = -5;  // 二进制：11111111111111111111111111111011（补码形式）
let result = a >>> 1;  // 结果：01111111111111111111111111111101
console.log(result); // 输出 2147483645

有符号与无符号右移的区别

有符号右移 >> ：保留符号位，适用于处理有符号数的场景，右移后负数依旧为负数。
无符号右移 >>> ：不保留符号位，总是用0填充高位，适用于处理无符号数的场景。即使输入是负数，结果也会是一个正数。

位运算的操作没什么好说的大家都知道，想了解更多的位运算操作请看 表达式和运算符。

补充：js中的位运算只能处理32的整数，超过会截断，这一点和大部分语言保持一致。

位运算操作

位运算的用途

向下取整

我们有一个小数如何保留它的整数部分，大部分人可能会想到Math.floor(n)，这是非常正确的做法，在实际开发中也应该这样用，但是在写一些库的时候我们可以使用 & 运算的特性来完成。

const n = -234.34343;
const mask = 0xFFFFFFFF; // 16进制的F相当于二进制中的1111,所以8个F就是32个1
console.log(n & mask); // 结果为234

原理很简单，当一个数"与"上一个二进制全是1的数，它的所有位状态都会保持不变，而且位运算只操作整数部分，小数部分直接被舍弃掉，所以会得到一个向下取整的结果。

判断奇偶性

在开发中会经常遇到判断奇偶性的情况，正常情况我们判断奇偶的条件是这个数除2之后的余数是否等于0，如果等于0那么它就是偶数，反之就是奇数，比如 n%2 === 0。但是只要我们仔细观察就会发现，所有偶数的二进制表示中最低位为0，所有奇数的二进制表示中最低位为1，所以我们只需判断最低位是否为0，就可以判断一个数的奇偶性。

const even = 234;
const odd = 233;

/**
 * 判断一个数是否是偶数
 * @param {number} n - 要判断奇偶的数字
 * @returns bolean
 */
function isEven(n) {
  if (n & 1) return false;
  return true;
}

console.log(isEven(even)); // true
console.log(isEven(odd)); // false

乘或除2的幂次方

const n = 9;

console.log(n >> 1); // 4
console.log(n >> 2); // 2
console.log(n << 1); // 18
console.log(n << 2); // 36

如果知道二进制是如何转换成10进制的，那么这个操作的原理就很明确了，假设我们有一个数111，这个数的10进制结果是7，从低位往高位的1依次表示12^0、12^1、1*2^2,所有结果相加为7，当右移动一位时，最低位的1就被丢弃了，表现的结果就像所有位置都降了一次幂，这个操作和10进制中的/2是等效的，所以每向右移动一位相当于除2，向左移动一位相当于乘2,用来操作数组下标非常好用。

交换两个变量

假设我们有两个变量 a 和 b，其值分别为 a 和 b。我们要交换它们的值，步骤如下：

1. a = a ^ b
2. b = a ^ b
3. a = a ^ b

步骤解释

第一步：a = a ^ b

这一步后，a 变成了 a 和 b 的异或结果。
现在 a = a ^ b。

第二步：b = a ^ b

这一步等效于 b = (a ^ b) ^ b。
根据异或的性质，(a ^ b) ^ b 可以简化为 a，因为 b ^ b 等于 0，而任何数与 0 异或结果是它本身。
现在 b = a。

第三步：a = a ^ b

这一步等效于 a = (a ^ b) ^ a。
根据异或的性质，(a ^ b) ^ a 可以简化为 b，因为 a ^ a 等于 0，而任何数与 0 异或结果是它本身。
现在 a = b。

示例

假设初始值 a = 5 和 b = 9，其二进制表示分别为 0101 和 1001。

1. 第一步：a = a ^ b，即 a = 0101 ^ 1001 = 1100（十进制为12）。
2. 第二步：b = a ^ b，即 b = 1100 ^ 1001 = 0101（十进制为5）。
3. 第三步：a = a ^ b，即 a = 1100 ^ 0101 = 1001（十进制为9）。

此时，a 的值为9，b 的值为5，交换成功。

let a = 5;  // 二进制: 0101
let b = 9;  // 二进制: 1001

// 第一步
a = a ^ b;  // a = 0101 ^ 1001 = 1100 (12)

// 第二步
b = a ^ b;  // b = 1100 ^ 1001 = 0101 (5)

// 第三步
a = a ^ b;  // a = 1100 ^ 0101 = 1001 (9)

console.log(a);  // 输出: 9
console.log(b);  // 输出: 5

计算两个数的最大公约数

计算两个数的最大公约数有一个流传甚久的算法，GCD(阿基米德算法)

function gcd(a, b) {
  if (b === 0) return a;
  return gcd(b, a % b);
}

这个算法的原理是，两个数的最大公约数，等于两个数除以较小那个数的余数的最大公约数。这个算法非常的简洁，如果两个数都比较大，但是最大公因数又比较小的情况下运算效率肯会比较低下。

现在来看看位运算优化的版本。

function gcd(a, b) {
    if (a === b) {
        return a;
    }
    if (a === 0) {
        return b;
    }
    if (b === 0) {
        return a;
    }

    // a 和 b 都是偶数
    if ((a & 1) === 0 && (b & 1) === 0) {
        return gcd(a >> 1, b >> 1) << 1;
    }

    // a 是偶数，b 是奇数
    if ((a & 1) === 0) {
        return gcd(a >> 1, b);
    }

    // a 是奇数，b 是偶数
    if ((b & 1) === 0) {
        return gcd(a, b >> 1);
    }

    // a 和 b 都是奇数，且 a > b
    if (a > b) {
        return gcd((a - b) >> 1, b);
    }

    // a 和 b 都是奇数，且 a <= b
    return gcd((b - a) >> 1, a);
}

// 示例
console.log(gcd(48, 18));  // 输出: 6

1. a === b：
   如果 a 和 b 相等，则它们的 GCD 就是 a 或 b 本身。

2. a === 0 或 b === 0：
   如果其中一个为零，则 GCD 是另一个数。

3. a 和 b 都是偶数：
   同时右移一位，相当于同时除以2，并且在最后结果上乘以2。

4. a 是偶数，b 是奇数：
   右移 a，相当于除以2。

5. a 是奇数，b 是偶数：
   右移 b，相当于除以2。

6. a 和 b 都是奇数：
   用较大数减去较小数，并右移结果，相当于除以2。

这个实现有一个专门的名字叫Stein，这个算法了解即可，重点还是位运算。

求平均数

求平均数这么简单的操作为什么还需要位运算啊！有这种疑问也很正常，毕竟js中的位运算只能操作32位的整数，但是js安全的数值是2^53-1,所以这个对js来说并没有太大作用，我们来考虑一下其它语言的情况，在其它语言中定义了一个int类型的数值，它最大能接收4294967295这个数，现在我想求4294967295和4294967293的平均数，按照平常的做法把它们先相加，之后再除以2，结果为4294967294，但是问题恰恰出在了第一步，这两个数相加的结果会超出int的范围，会得到一个错误的结果，我们再把错误的结果除2，显然是错误的，为了解决这个问题我们可以这么做。

function average(a, b) {
    return (a & b) + ((a ^ b) >> 1);
}

// 示例
let a = 6;
let b = 10;
console.log(average(a, b));  // 输出: 8

• 无需进位的部分：a & b。
• 需要进位的部分：(a ^ b) >> 1，相当于除以2。
  将这两部分相加，就得到 a 和 b 的平均值。这种方法避免了直接相加可能导致的溢出问题，同时高效地利用了位运算的特性。

操作位的一些方法

找出二进制中1的个数

要计算一个整数的二进制表示中1的个数，可以使用按位操作与循环。

function countOnes(n) {
    let count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// 示例
console.log(countOnes(15));  // 输出: 4 (1111)

检查某位是否为1

要检查某个位是否为1，可以使用按位与操作符 &。

function isBitSet(n, k) {
    return (n & (1 << k)) !== 0;
}

// 示例
console.log(isBitSet(5, 0));  // 输出: true (5的二进制为101, 第0位为1)
console.log(isBitSet(5, 1));  // 输出: false (5的二进制为101, 第1位为0)

设置某位为1

要设置某个位为1，可以使用按位或操作符 |。

function setBit(n, k) {
    return n | (1 << k);
}

// 示例
console.log(setBit(5, 1));  // 输出: 7 (5的二进制为101, 设置第1位为1后为111, 即7)

清除某位（设置某位为0）

要清除某个位为0，可以使用按位与操作符 & 和按位非操作符 ~。

function clearBit(n, k) {
    return n & ~(1 << k);
}

// 示例
console.log(clearBit(5, 0));  // 输出: 4 (5的二进制为101, 清除第0位后为100, 即4)

反转某一位

要反转某个位，可以使用按位异或操作符 ^。

function toggleBit(n, k) {
    return n ^ (1 << k);
}

// 示例
console.log(toggleBit(5, 0));  // 输出: 4 (5的二进制为101, 反转第0位后为100, 即4)
console.log(toggleBit(5, 1));  // 输出: 7 (5的二进制为101, 反转第1位后为111, 即7)

反转二进制

要反转整个二进制数，可以使用循环和按位操作。

function reverseBits(n) {
    let reversed = 0;
    while (n > 0) {
        reversed = (reversed << 1) | (n & 1);
        n >>= 1;
    }
    return reversed;
}

// 示例
console.log(reverseBits(13));  // 输出: 11 (13的二进制为1101, 反转后为1011, 即11)

总结

首先我们了解了位运算的基本运算规则，之后学习了一些常用的技巧比如使用位运算实现判断奇偶性，乘或除2的幂次方等操作，这些操作在日常开发中是非常实用的，最后我们学习了一些操作位的方法，这些方法之后我们都会用到，比如在位图中我们需要对某一位操作，这个时候就派上用场了。