给你一个 正 整数 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 个奇数下标。
提示：
视频讲解
见【周赛 337】 。
方法一：二进制基本操作
不断取最低位，然后右移，直到等于 0 为止，这样可以取到每个比特位。
[sol1-Python3]1
2
3
4
5
6
7
8
9
| 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
|
[sol1-Java]1
2
3
4
5
6
7
8
| class Solution {
public int[] evenOddBit(int n) {
var ans = new int[2];
for (int i = 0; n > 0; i ^= 1, n >>= 1)
ans[i] += n & 1;
return ans;
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
| class Solution {
public:
vector<int> evenOddBit(int n) {
vector<int> ans(2);
for (int i = 0; n; i ^= 1, n >>= 1)
ans[i] += n & 1;
return ans;
}
};
|
[sol1-Go]1
2
3
4
5
6
7
8
| func evenOddBit(n int) []int {
ans := make([]int, 2)
for i := 0; n > 0; i ^= 1 {
ans[i] += n & 1
n >>= 1
}
return ans
}
|
复杂度分析
- 时间复杂度：O(\log n)。
- 空间复杂度：O(1)。仅用到若干额外变量。
方法二：位掩码 + 库函数
利用位掩码 0x55555555（二进制的 010101\cdots），取出偶数下标比特和奇数下标比特，分别用库函数统计 1 的个数。
本题由于 n 范围比较小，取 0x5555 作为位掩码。
[sol2-Python3]1
2
3
4
| class Solution:
def evenOddBit(self, n: int) -> List[int]:
MASK = 0x5555
return [(n & MASK).bit_count(), (n & (MASK >> 1)).bit_count()]
|
[sol2-Java]1
2
3
4
5
6
| class Solution {
public int[] evenOddBit(int n) {
final int MASK = 0x5555;
return new int[]{Integer.bitCount(n & MASK), Integer.bitCount(n & (MASK >> 1))};
}
}
|
[sol2-C++]1
2
3
4
5
6
7
| class Solution {
public:
vector<int> evenOddBit(int n) {
const int MASK = 0x5555;
return {__builtin_popcount(n & MASK), __builtin_popcount(n & (MASK >> 1))};
}
};
|
[sol2-Go]1
2
3
4
| func evenOddBit(n int) []int {
const mask = 0x5555
return []int{bits.OnesCount16(uint16(n & mask)), bits.OnesCount16(uint16(n & (mask >> 1)))}
}
|
复杂度分析
- 时间复杂度：O(1)。
- 空间复杂度：O(1)。仅用到若干额外变量。
