SorryToPerson logo
返回
算法2026-04-15·6 分钟

算法知识库：位运算算法实现

JavaScript/TypeScript 实现位运算相关算法，如位计数、位操作技巧等。

位运算算法实现

1. 位计数

ts
function countBits(n: number): number {
  let count = 0;
  while (n) {
    count += n & 1;
    n >>= 1;
  }
  return count;
}

function hammingWeight(n: number): number {
  let count = 0;
  while (n) {
    n &= n - 1;
    count += 1;
  }
  return count;
}

2. 交换两个数

ts
function swap(a: number, b: number): [number, number] {
  a ^= b;
  b ^= a;
  a ^= b;
  return [a, b];
}

3. 判断是否为 2 的幂

ts
function isPowerOfTwo(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0;
}

4. 找到唯一出现的数

ts
function singleNumber(nums: number[]): number {
  let result = 0;
  for (const num of nums) {
    result ^= num;
  }
  return result;
}

5. 位掩码子集枚举

ts
function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  const n = nums.length;
  for (let mask = 0; mask < 1 << n; mask += 1) {
    const subset: number[] = [];
    for (let i = 0; i < n; i += 1) {
      if (mask & (1 << i)) {
        subset.push(nums[i]);
      }
    }
    result.push(subset);
  }
  return result;
}

6. 实现要点

  • 位运算直接操作二进制位。
  • 常数时间复杂度操作。
  • 适合状态压缩和优化问题。
算法位运算JavaScript