LeetCode 冥想——章节位操作

目录

• 简介
• 按位运算符
  • 和 (&)
  • 或 (|)
  • 异或 (^)
  • 不是(~)
  • 左移（零填充）(
  • 右移（符号保留）(>>)
  • 右移（无符号）(>>>)
• 有点
• 设置一点
• 资源

我们已经进入了本系列的最后一章，终于是时候简要介绍一下位操作了。

根据维基百科的定义，按位运算在位串、位数组或二进制数字（被视为位串）的各个位级别上进行运算。

我们首先用二进制（基数 2）表示一个数字。我们可以对数字使用 tostring 方法，并指定 基数:

const n = 17;

console.log(n.tostring(2)); // 10001

我们还可以解析一个整数，给它一个基数：

console.log(parseint(10001, 2)); // 17

请注意，我们还可以表示带有前缀 0b 的二进制数：

console.log(0b10001); // 17
console.log(0b101); // 5

例如，这些是相同的数字：

0b1 === 0b00000001 // true

javascript 中所有按位运算都是对 32 位二进制数执行的。
也就是说，在执行按位运算之前，javascript 将数字转换为 32 位 **有符号* 整数。*

例如，17 不会只是 10001，而是 00000000 00000000 00000000 00010001。

执行按位运算后，结果将转换回 64 位 javascript 数字。

按位运算符

和 （＆）

如果两位都是 1，则结果为 1，否则为 0。

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 & x2; // 1 (0b1)

或 (|)

如果任意一位为 1，则结果为 1，否则为 0。

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 | x2; // 21 (0b10101)

异或 (^)

如果各位不同（一位为1，一位为0），则结果为1，否则为0。

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 ^ x2; // 20 (0b10100)

不是（~）

翻转位（1 变为 0，0 变为 1）。

Cutout.Pro抠图

AI批量抠图去背景

下载

const n = 17;

const result = ~n; // -18

如果我们使用辅助函数来查看二进制表示，它正如我们所期望的：

console.log(createbinarystring(n));
// -> 00000000 00000000 00000000 00010001

console.log(createbinarystring(result));
// -> 11111111 11111111 11111111 11101110

最左边的位表示信号 - 数字是负数还是正数。

请记住，我们说过 javascript 使用 32 位带符号整数进行按位运算。
最左边的位为 1 表示负数，0 表示正数。
此外，运算符对操作数的二进制补码位表示进行运算。 对每一位应用运算符，并按位构造结果。

请注意，二进制补码允许我们获得带有反信号的数字。
一种方法是反转正数表示中数字的位并加 1：

function twoscomplement(n) {
  return ~n + 0b1;
}

左移（零填充）（

将给定数量的位数向左移动，添加从右侧移入的零位。

const n = 17;
const result = n << 1; // 34


console.log(createbinarystring(17));
// -> 00000000 00000000 00000000 00010001

console.log(createbinarystring(34));
// -> 00000000 00000000 00000000 00100010

请注意，第 32 位（最左边的一位）被丢弃。

右移（符号保留）(>>)

将给定位数向右移动，在从左侧添加位时保留符号。

const n = 17;
const result = n >> 1; // 8


console.log(createbinarystring(17));
// -> 00000000 00000000 00000000 00010001

console.log(createbinarystring(8));
// -> 00000000 00000000 00000000 00001000

const n = -17;
const result = n >> 1; // -9

console.log(createbinarystring(-17));
// -> 11111111 11111111 11111111 11101111

console.log(createbinarystring(-9));
// -> 11111111 11111111 11111111 11110111

右移（无符号）(>>>)

将给定位数向右移动，从左侧添加位时添加 0，无论符号是什么。

const n = 17;
const result = n >>> 1; // 8


console.log(createbinarystring(17));
// -> 00000000 00000000 00000000 00010001

console.log(createbinarystring(8));
// -> 00000000 00000000 00000000 00001000

const n = -17;
const result = n >>> 1; // 2147483639

console.log(createbinarystring(-17));
// -> 11111111 11111111 11111111 11101111

console.log(createbinarystring(2147483639));
// -> 01111111 11111111 11111111 11110111

得到一点

要获取特定位，我们首先需要创建一个位掩码.
我们可以通过将 1 向左移动我们想要获取的位的索引来实现这一点。
结果是二进制数和位掩码的 和 。

但是，使用javascript，我们还可以通过索引进行无符号右移，将位放在第一位（这样我们就无法得到该位置的实际值，但它是否是1或 0):

function getbit(number, idx) {
  const bitmask = 1 << idx;
  const result = number & bitmask;

  return result >>> idx;
}

例如，我们尝试 13，二进制为 1101：

const binarynumber = 0b1101;

console.log('bit at position 0:', getbit(binarynumber, 0));
console.log('bit at position 1:', getbit(binarynumber, 1));
console.log('bit at position 2:', getbit(binarynumber, 2));
console.log('bit at position 3:', getbit(binarynumber, 3));

/*
output:

bit at position 0: 1
bit at position 1: 0
bit at position 2: 1
bit at position 3: 1
*/

设置一点

如果我们想将一位变为 1（换句话说，“设置一点”），我们可以做类似的事情。

首先，我们可以通过将 1 向左移动我们想要设置为 1 的位的索引来再次创建位掩码。
结果是数字和位掩码的 或 ：

function setbit(number, idx) {
  const bitmask = 1 << idx;
  return number | bitmask;    
}

请记住，在我们的示例中，13 在二进制中是 1101，假设我们要在索引 1 处设置 0：

const binaryNumber = 0b1101;
const newBinaryNumber = setBit(binaryNumber, 1);

console.log(createBinaryString(newBinaryNumber));
// -> 00000000 00000000 00000000 00001111

console.log('Bit at position 1:', getBit(newBinaryNumber, 1));
// -> Bit at position 1: 1

我们简要地了解了按位运算，以及获取/设置位。在最后一章中，我们将从 1 位数开始讨论五个问题。在那之前，祝您编码愉快。

资源

• “javascript 位操作的绝对要点”- lucas f. costa
• js 位运算符
• 号码（mdn）
• 按位与 (mdn)
• 按位非 (mdn)
• 按位或 (mdn)
• 按位异或 (mdn)
• 左移（mdn）
• 右移（mdn）
• 无符号右移 (mdn)