[LeetCode] 每日一题 2595. 奇偶位数

题目链接

https://leetcode.cn/problems/number-of-even-and-odd-bits

题目描述

给你一个 正 整数 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

解题思路

今天的题目比较简单，核心思路是将给定的整数 n 展开成二进制形式，并逐位判断其中奇偶位上值为 1 的个数。题目要求我们分别统计在偶数下标和奇数下标上值为 1 的位数

具体来说，关键点是：我们不需要精确知道每一位的值，只需要判断当前是偶数位还是奇数位，因此我们可以用 异或运算 来交替判断偶数位和奇数位。对于数字的逐位判断，我们通过与运算 (n & 1) 来获取当前位的值，而右移操作 (n >>= 1) 让我们可以快速处理下一位。这种方式不仅简洁，而且提高了运算效率，因为除2操作实际上就是二进制右移一位

代码实现

class Solution {
    public int[] evenOddBit(int n) {
        int[] ans = new int[2];
        for (int i = 0; n > 0; i ^= 1) { // 通过 i 异或操作交替处理奇偶位
            ans[i] += n & 1; // 获取当前位是否为 1
            n >>= 1; // 右移处理下一位
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(log n)，因为我们对 n 进行右移操作，直到它变为 0。每次右移一位，相当于操作了 n 的每一位，因此时间复杂度为 O(log n)，其中 log n 是 n 的二进制位数

• 空间复杂度：O(1)，我们只使用了一个常数空间来存储结果数组 ans

总结

这道题目通过对整数 n 的二进制位进行逐位操作，统计在偶数和奇数下标上值为 1 的位数。尽管题目本身较为简单，但我们在具体实现上做了一些优化。通过使用异或操作 (^) 来交替判断奇偶位，通过与运算 (n & 1) 直接获取当前位的值，并使用右移操作 (n >>= 1)) 提高了运算效率。这些操作使得代码更加简洁和高效。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。