Number of Even and Odd Bits

Number of Even and Odd Bits

What is this problem about?

The Number of Even and Odd Bits problem asks you to count how many bits at even positions are set to 1 and how many bits at odd positions are set to 1 in the binary representation of a given integer. Positions are 0-indexed from the least significant bit. This Number of Even and Odd Bits coding problem tests bit iteration with position tracking.

Why is this asked in interviews?

Meta and Amazon ask this easy problem to verify bit manipulation fundamentals — specifically iterating through bits while tracking position parity. The bit manipulation interview pattern is directly tested at a basic level.

Algorithmic pattern used

Bit iteration with position tracking. Iterate from position 0 upward. At each step: check if the current LSB is 1 (n & 1). If position is even, increment even_count; if odd, increment odd_count. Right-shift n by 1. Stop when n == 0.

Alternative: use bitmask 0x55555555 (alternating bits for even positions) and 0xAAAAAAAA (for odd positions). Count set bits in n & mask for each.

Example explanation

n=17 (binary: 10001).

• Position 0: bit=1 (even position). even_count=1.
• Position 1: bit=0 (odd). odd_count=0.
• Position 2: bit=0 (even). even_count=1.
• Position 3: bit=0 (odd). odd_count=0.
• Position 4: bit=1 (even). even_count=2. Result: [even=2, odd=0].

Common mistakes candidates make

• Counting positions from 1 instead of 0 (problem specifies 0-indexed).
• Confusing "bit value" (0 or 1) with "bit position" (index).
• Not stopping when n becomes 0 (continuing with 0 bits adds nothing but wastes iterations).
• Off-by-one in the even/odd alternation.

Interview preparation tip

Position-based bit problems use a counter alongside the standard n & 1 / n >>= 1 loop. Incrementing a position counter alongside the shift is the clean approach. The bitmask alternative (n & 0xAAAAAAAA for odd positions) is elegant and O(1) once you memorize the masks. Practice both approaches — the loop for clarity, the bitmask for speed. These patterns appear in broader bit manipulation problems involving alternating bit patterns.