当前位置：首页 > news >正文

LeetCode 2595.奇偶位数：位运算

news 2025/8/9 0:34:15

【LetMeFly】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$ 的最低位？

n & 1即可
如何移除 $n$ 的最低为？

直接右移n >>= 1即可
如何变换奇偶下标？

布尔类型index = !index或整型index ^= 1都可

时间复杂度 $O(\log(n))$ 。 $\log 1024=10$ ，运算次数很低。
空间复杂度 $O (1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-02-20 11:04:55* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-20 11:06:12*/
class Solution {
public:vector<int> evenOddBit(int n) {vector<int> ans(2);bool index = false;while (n) {ans[index] += n & 1;index = !index;n >>= 1;}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-02-20 11:06:38
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-20 11:08:51
'''
from typing import Listclass Solution:def evenOddBit(self, n: int) -> List[int]:ans = [0, 0]index = Falsewhile n:ans[index] += n & 1index = not indexn >>= 1return ans

Java

/** @Author: LetMeFly* @Date: 2025-02-20 11:06:42* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-20 11:10:57*/
class Solution {public int[] evenOddBit(int n) {int[] ans = new int[2];int index = 0;while (n > 0) {ans[index] += n & 1;index ^= 1;n >>= 1;}return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-02-20 11:06:49* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-20 11:18:27*/
package mainfunc evenOddBit(n int) []int {ans := make([]int, 2)for index := 0; n > 0; n >>= 1 {ans[index] += n & 1index ^= 1}return ans
}