标签: 位运算
难度: Easy
给你一个 正 整数 n 。
用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。
用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。
返回整数数组 answer ，其中 answer = [even, odd] 。
示例 1：
输入：n = 17 输出：[2,0] 解释：17 的二进制形式是 10001 。 下标 0 和 下标 4 对应的值为 1 。 共有 2 个偶数下标，0 个奇数下标。
示例 2：
输入：n = 2 输出：[0,1] 解释：2 的二进制形式是 10 。 下标 1 对应的值为 1 。 共有 0 个偶数下标，1 个奇数下标。
提示：
1 <= n <= 1000运行时间: 20 ms
内存: 16.1 MB
class Solution:
def evenOddBit(self, n: int) -> List[int]:
even, odd = 0, 0
cnt = 0
while n:
if cnt % 2 == 0 and n & 1:
even += 1
elif cnt % 2 == 1 and n & 1:
odd += 1
n >>= 1
cnt += 1
return [even, odd]
该题解通过遍历整数 n 的二进制位来统计奇数位和偶数位上值为 1 的位的数量。使用一个循环，每次迭代检查 n 的最低位（n & 1），根据当前位的下标是奇数还是偶数（通过计数器 cnt 实现），更新奇数位或偶数位的计数器。每次迭代后，n 右移一位（n >>= 1），即去掉已经检查过的最低位，同时计数器 cnt 自增1，直到 n 为 0。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def evenOddBit(self, n: int) -> List[int]:
even, odd = 0, 0 # 初始化偶数位和奇数位的计数器
cnt = 0 # 位计数器，用来跟踪当前检查的是哪一位
while n: # 当 n 不为 0 时循环
if cnt % 2 == 0 and n & 1: # 如果当前位是偶数位且为 1
even += 1 # 增加偶数位计数器
elif cnt % 2 == 1 and n & 1: # 如果当前位是奇数位且为 1
odd += 1 # 增加奇数位计数器
n >>= 1 # n 右移一位，去掉已经检查的最低位
cnt += 1 # 增加位计数器
return [even, odd] # 返回偶数位和奇数位的计数
位运算（n & 1）用来检查整数 n 的最低位是否为 1 是因为这种操作非常高效和直接。这个运算符会与二进制的 1 进行 AND 操作，这样仅当 n 的最低位是 1 时，结果才为 1（即真），如果是 0 则结果为 0（即假）。这种方法直接对应到二进制位的检查，无需进行其他转换或复杂计算，因此是处理二进制数据的常用技巧。
在这种实现中，每次迭代将 n 右移一位（n >>= 1）不会导致遗漏检查某些位的值。右移操作使得 n 的当前最低位被丢弃，而下一位变为新的最低位。这个过程会持续进行，直到 n 变为 0。每次迭代中，都会检查当时的最低位，然后移除它，因此所有位都会依次被检查一次，不会有遗漏。
变量 cnt 的初始值设为 0 是因为在二进制计数中，最低位（最右边的位）通常被认为是第 0 位。这种从 0 开始的索引方式是在编程中常见的，它使得位的索引与数组和其他数据结构的索引方式保持一致。从 0 开始和从 1 开始的主要区别在于位的编号方式，前者使得偶数位的索引为偶数（例如第 0 位、第 2 位等），而后者则会使得偶数位的索引为奇数（例如第 1 位、第 3 位等），这会影响如何判断当前位是奇数位还是偶数位。
在题解的代码中不需要特别处理 n=0 的情况，因为当 n=0 时，循环条件 `while n:` 不成立，循环体不会被执行。这意味着如果 n 的初始值为 0，函数将直接返回偶数位和奇数位计数器的初始值 [0, 0]。这种处理是适当的，因为如果 n 为 0，则它没有任何为 1 的位，因此偶数位和奇数位的计数都应该是 0。