191.位-1-的个数.md

191.位-1-的个数

/*
 * @lc app=leetcode.cn id=191 lang=typescript
 *
 * [191] 位1的个数
 */

// @lc code=start
function hammingWeight(n: number): number {}
// @lc code=end

解法 1: 使用 API

function hammingWeight(n: number): number {
  return n
    .toString(2)
    .split('')
    .map(Number)
    .reduce((a, b) => a + b)
}

解法 2: 使用位运算

判断最右位是否为 1,如果为 1 则 res + 1,然后向右移一位

在 JavaScript 中,>> 是有符号的右移,这回导致一个比较大的数字右移时失败会变为负数,比如4294967293>>1===-2

是因为使用 >> 计算是,会先对数字进行 ToInt32 操作,而ToInt32(4294967293)的结果是 -3,最终 -3>>1 -> -2

所以必须要使用 >>> 才能正确

function hammingWeight(n: number): number {
  let res = 0
  while (n) {
    res += n & 1
    n >>>= 1
  }
  return res
}

• Right shift (>>)
• 6.1.6.1.10 Number::signedRightShift
• 7.1.6 ToInt32

解法 3: 位运算 2

利用 n&(n-1) 会消除最后一位的原理

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

Case

test.each([
  { input: { n: 11 }, output: 3 },
  { input: { n: 128 }, output: 1 },
  { input: { n: 4294967293 }, output: 31 },
])('input: n = $input.n', ({ input: { n }, output }) => {
  expect(hammingWeight(n)).toBe(output)
})