Easy

题目描述

给你一个正整数 n。

用 even 表示在 n 的二进制表示（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制表示（下标从 0 开始）中值为 1 的奇数下标的个数。

注意：二进制表示中的位是从右到左进行下标标记的。

返回数组 [even, odd]。

示例 1：

输入：n = 50
输出：[1,2]
解释：50 的二进制表示是 110010。
包含下标 1、4 和 5 上的 1。

示例 2：

输入：n = 2
输出：[0,1]
解释：2 的二进制表示是 10。
仅在下标 1 上包含 1。

约束条件：

  • 1 <= n <= 1000

提示：

  • 维护两个整数变量 even 和 odd，用于计算整数 n 的二进制表示中偶数和奇数下标的个数。
  • 当 n 为正数时，将 n 除以 2，如果 n 模 2 为 1，则将 1 添加到对应的变量中。

解题思路

这是一道位操作的基础题目，需要统计二进制表示中偶数位和奇数位上 1 的个数。

核心思路：

  1. 从右到左遍历二进制位，下标从 0 开始
  2. 偶数下标（0, 2, 4, …）和奇数下标（1, 3, 5, …）交替出现
  3. 使用位操作检查每一位是否为 1

解法一：模拟法

  • 使用一个标志位记录当前是偶数位还是奇数位
  • 通过 n & 1 检查最低位是否为 1
  • 每次右移一位 n >>= 1，标志位取反

解法二：位掩码法（推荐）

  • 偶数位掩码：0x55555555（二进制：01010101…）
  • 奇数位掩码：0xAAAAAAAA（二进制：10101010…）
  • 分别与 n 进行按位与操作，然后统计 1 的个数

由于数据范围较小（n <= 1000），两种解法性能差异不大，模拟法更易理解。

代码实现

class Solution {
public:
    vector<int> evenOddBit(int n) {
        int even = 0, odd = 0;
        int index = 0;
        
        while (n > 0) {
            if (n & 1) {
                if (index % 2 == 0) {
                    even++;
                } else {
                    odd++;
                }
            }
            n >>= 1;
            index++;
        }
        
        return {even, odd};
    }
};

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        even = odd = 0
        index = 0
        
        while n > 0:
            if n & 1:
                if index % 2 == 0:
                    even += 1
                else:
                    odd += 1
            n >>= 1
            index += 1
        
        return [even, odd]

public class Solution {
    public int[] EvenOddBit(int n) {
        int even = 0, odd = 0;
        int index = 0;
        
        while (n > 0) {
            if ((n & 1) == 1) {
                if (index % 2 == 0) {
                    even++;
                } else {
                    odd++;
                }
            }
            n >>= 1;
            index++;
        }
        
        return new int[] {even, odd};
    }
}

var evenOddBit = function(n) {
    let even = 0, odd = 0, index = 0;
    while (n > 0) {
        if (n & 1) {
            if (index % 2 === 0) even++;
            else odd++;
        }
        n >>= 1;
        index++;
    }
    return [even, odd];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(log n)
空间复杂度O(1)

说明：

  • 时间复杂度：需要遍历 n 的所有二进制位，位数为 log₂(n)
  • 空间复杂度：只使用常数个额外变量

相关题目