位运算

coderljw 2024-10-13

位运算
算法

小于 1 分钟

# 1. 打印二进制

const number2binary = (num) => {
  const ary = []
  for (i = 31; i >= 0; i--) {
    ary.push((num & (1 << i)) === 0 ? 0 : 1)
  }

  return ary.join('')
}

number2binary(4396) === (4396).toString(2).padStart(32, 0)

1
2
3
4
5
6
7
8
9
10

# 2. 求中点

mid = L + ((R - L) >> 1)

const L = 2
const R = 8

const mid = L + ((R - L) >> 1)

1
2
3
4

# 3. 异或运算 ^

无进位相加，0 ^ N等于 N，N ^ N等于 0，满足交换律与结合律。

0 ^ 7 // => 7
7 ^ 7 // => 0

// 两数交换
let a = 3
let b = 4

a ^= b
b ^= a
a ^= b

1
2
3
4
5
6
7
8
9
10

数列中只有一个数出现奇数次，其余数出现偶数次，求出现奇数次的数？

const ary = [1, 2, 1, 7, 7, 1, 2, 1, 7]

let num = 0
ary.map((i) => (num ^= i))
console.log(num)

1
2
3
4
5

数列中有两个数出现奇数次，其余数出现偶数次，求出现奇数次的数？

num & (~num + 1) 提取不为零数中最右侧的 1。

const ary = [1, 2, 1, 7, 7, 1, 2, 1, 7, 9]

let num1 = 0, // num1 = a ^ b，因为 a !== b，所以 num1 !== 0，num1 必然有一位为 1
  num2 = 0 // num2 = a or b
ary.map((i) => (num1 ^= i))

let rightOne = num1 & (~num1 + 1) // 取出最右侧的 1
ary.map((i) => i & rightOne && (num2 ^= i)) // 划分 a、b，将 a 或 b 赋值给 num2

console.log(num2, num1 ^ num2) // 两数

1
2
3
4
5
6
7
8
9
10

排序算法