What is the best way to count even and odd bits in the binary representation of a number?

The best way is to use bitwise operations with two counters—one for even indices and one for odd indices—while iterating through the bits of the number.

How can I avoid mistakes when counting bits at even and odd positions?

Be sure to clearly separate the handling of even and odd indices, and double-check your bitwise operations, especially with shifts and masks.

Can I solve the "Number of Even and Odd Bits" problem without bit manipulation?

While it's possible, bit manipulation offers a more efficient solution with less overhead and faster execution, especially for larger integers.

What is the time complexity of solving the "Number of Even and Odd Bits" problem?

The time complexity is O(log n), as the algorithm processes each bit of n individually.

How does GhostInterview help with the "Number of Even and Odd Bits" problem?

GhostInterview provides insights on how to leverage bit manipulation, focusing on optimizing the solution with efficient operations and counters.

#2595

Easy

auto_awesome位运算·操作·driven·solution·strategy

LeetCode 题解工作台

奇偶位数

给你一个正整数 n 。用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。请注意，在数字的二进制表示中，位下标的顺序从右到左。返回整数数组 answer ，其中 …

位运算

题目描述

给你一个正整数 n 。

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

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

请注意，在数字的二进制表示中，位下标的顺序 从右到左。

返回整数数组 answer ，其中 answer = [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

lightbulb

解题思路

方法一：枚举

我们根据题意，枚举 $n$ 的二进制表示中从低位到高位的每一位，如果该位为 $1$ ，则根据该位的下标是奇数还是偶数，将对应的计数器加 $1$ 即可。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为给定的整数。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        ans = [0, 0]
        i = 0
        while n:
            ans[i] += n & 1
            i ^= 1
            n >>= 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of bit manipulation techniques.
question_mark
Expect the candidate to optimize the solution with efficient operations like bit shifting.
question_mark
Pay attention to the candidate’s ability to maintain multiple counters for specific conditions.

warning

常见陷阱

外企场景

error
Candidates may attempt a less efficient solution using string conversion or array manipulation.
error
Confusing even and odd indices, leading to incorrect counting.
error
Overcomplicating the solution with unnecessary loops or data structures.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count bits at even and odd indices for larger integers.
arrow_right_alt
Consider extending the problem to work with negative integers, adjusting for the sign bit.
arrow_right_alt
Handle cases where the binary representation has fewer bits than the typical word length.

help

常见问题

外企场景

继续练习

#2588 统计美丽子数组数目 #2572 无平方子集计数 #2571 将整数减少到零需要的最少操作数