2595. Number of Even and Odd Bits

algo

链接：2595. 奇偶位数 - 力扣（LeetCode）

做法：Bitwise Operations

既然是二进制，直觉告诉我应该和Bitwise Operations有关。

测试了一下，所谓 0-indexed 指的是最末尾位第 0 位，往左越来越大。

题目给的例子是 n = 17，其二进制是 10001，所以返回 [2, 0]，因为位置 0 和 4 是 1，其余位是 0。

如果是 4，二进制是 100，所以返回 [1, 0]。

看了一下Bitwise Operations的笔记，有两个东西可以用，一个是 n ^ (n - 1) 去除末位 1，一个是 log2(n & -n) 得到末位的 1 在哪个位置。

不过看了下 hint，这个实在是绕了远路，其实只要一直整除 2，其余数即体现了是不是某位置上是 1 还是 0。首先，一个数字的二进制是 1 则为奇数，则 n % 2 = 1，如果是 0 则为偶数，则 n % 2 = 0。整除 2 则相当于右移，就可以判断下一位了。所以右移的效率可能比整除高一些？同时还要用一个 flag 记住当前是偶数还是奇数位。

class Solution:
  def evenOddBit(self, n: int) -> List[int]:
    ans = [0, 0]
    i = 0
    while n:
      ans[i] += n & 1
      n >>= 1
      i ^= 1
    return ans

另一种办法是使用 01 的掩码：

class Solution:
  def evenOddBit(self, n: int) -> List[int]:
    # check with mask binary 0101010101...
    # 1 <= n <= 1000
    # 1000 binary = 1,111,101,000
    # 10 digits
    even_mask = 0b0101010101
    odd_mask = 0b1010101010
    return [(n & even_mask).bit_count(), (n & odd_mask).bit_count()]
Last update : May 23, 2023
Created : May 23, 2023