Skip to content

Latest commit

 

History

History
141 lines (113 loc) · 4.01 KB

bit-manipulation.md

File metadata and controls

141 lines (113 loc) · 4.01 KB

位运算相关知识，能让你更容易理解lanes的相关代码

⚠️ 注意，在这里已经假设你知道位运算符的作用了，如果还不知道可以看MDN的解释

问题1 .实现gitBit(num: number, i: number):boolean 函数

该函数会会根据数字num，第i个bit的值返回一个布尔值，如果第i个bit为1则返回true否则返回false(i从零开始)

示例1

输入: num = 0b1110 , i = 0 返回: false 解释: 0b1110的第零位为0

示例2

输入: num = 0b1110 , i = 1 返回: true 解释: 0b1110的第一位为1

示例3

输入: num = 0b1110 , i = 2 返回: true 解释: 0b1110的第二位为1

参考答案

const getBit = (num: number, i: number): boolean => {
  return (num & (1 << i)) !== 0
}

解释

要取num的第i位bit，只需让num和除了第i位为1其他位全为0的数按位与，然后在判断他是否为零即可，如果为零表示该bit为0，如果不为零则表示为1 这种数可以通过<<轻松获得 1 << 0 等价于 0b0000000000000000000000000000001 1 << 1 等价于 0b0000000000000000000000000000010 1 << 2 等价于 0b0000000000000000000000000000100 1 << 3 等价于 0b0000000000000000000000000001000

问题2. 实现setBit(num: number, i: number): number函数

该函数会将数字num，第i位bit置为1并返回

示例1

输入: num = 0b00000 , i = 0 返回: 0b00001

示例2

输入: num = 0b00000 , i = 1 返回: 0b00010

示例3

输入: num = 0b01010 , i = 2 返回: 0b01110

参考答案

const setBit = (num: number, i: number): number => {
  return (1 << i) | num
}

解释

要想将num的第i位bit设为1，只需让num和除了第i位为1其他位全为0的数按位或即可 这种数可以通过<<轻松获得 1 << 0 等价于 0b0000000000000000000000000000001 1 << 1 等价于 0b0000000000000000000000000000010 1 << 2 等价于 0b0000000000000000000000000000100 1 << 3 等价于 0b0000000000000000000000000001000

问题3. 实现clearBit(num: number, i: number): number函数

该函数会将数字num，第i位bit置为0并返回

示例1

输入: num = 0b00000 , i = 0 返回: 0b00000

示例2

输入: num = 0b00010 , i = 1 返回: 0b00000

示例3

输入: num = 0b01110 , i = 2 返回: 0b01010

参考答案

const clearBit = (num: number, i: number): number => {
  const mask = ~(1 << i)
  return num & mask
}

解释

要想将num的第i位bit设为0，只需让num和除了第i位为0其他位全为1的数按位与即可 这种数可以通过两个步骤获得，先通过<<获得除了第i位为1其他全为零的数再通过~将他反转即可 第一步 1 << 3 等价于 0b0000000000000000000000000001000 第二步 ~(1<<3)等价于0b1111111111111111111111111110111

问题4. 二进制数组转整数

给你一个数组。数组中的值不是 0 就是 1。已知此数组是一个整数数字的二进制表示形式。 请你返回该数组所表示数字的 十进制值 。

示例1

输入: [1,0,1] 返回: 5

示例2

输入: [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] 返回: 18880

示例3

输入: [0,0] 返回: 0

参考答案

const getDecimalValue = (head: number[]): number => {
  let ans = 0

  for (let i = 0; i < head.length; ++i) {
    ans = (ans << 1) | head[i]
  }

  return ans
}

解释

通过位移和或操作注意将二进制位设置到ans上即可 考虑如下例子，当输入为[1,1]时 第一轮循环先将0位设置1 此时的 ans = 0b1 第二轮先将ans左移一位此时ans = 0b10,再将ans的第零位设为1此时ans = 0b11

相关引用