# Number of Even and Odd Bits
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-even-and-odd-bits)
Canonical: https://scaleengineer.com/dsa/problems/number-of-even-and-odd-bits
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
You are given a **positive** integer `n`.

Let `even` denote the number of even indices in the binary representation of `n` with value 1.

Let `odd` denote the number of odd indices in the binary representation of `n` with value 1.

Note that bits are indexed from **right to left** in the binary representation of a number.

Return the array `[even, odd]`.

**Example 1:**

**Input:** n = 50

**Output:** \[1,2\]

**Explanation:**

The binary representation of 50 is `110010`.

It contains 1 on indices 1, 4, and 5.

**Example 2:**

**Input:** n = 2

**Output:** \[0,1\]

**Explanation:**

The binary representation of 2 is `10`.

It contains 1 only on index 1.

**Constraints:**

* `1 <= n <= 1000`

# Approaches
## Convert to String and Iterate
This approach converts the integer `n` into its binary string representation. It then iterates through this string from right to left, keeping track of the current bit's index (0-based). If a '1' is found, it checks if the index is even or odd and increments the corresponding counter.
**Time:** O(log n), where n is the input integer. This is because converting n to a binary string takes O(log n) time, and iterating through the string of length log n also takes O(log n) time. · **Space:** O(log n) to store the binary string representation of n.
**Pros:** Simple to understand and implement.; Leverages standard library functions for string conversion.
**Cons:** Less efficient due to the overhead of string creation and manipulation.; Requires extra space proportional to the number of bits in n.
### Explanation
This approach converts the integer to a string and iterates over it. The main steps are:\n- Convert `n` to its binary string representation.\n- Iterate through the string from right to left, which corresponds to indices 0, 1, 2, ...\n- For each '1' encountered, check the parity of its index and update the respective counter.\n\n```java\nclass Solution {\n    public int[] evenOddBit(int n) {\n        String binaryString = Integer.toBinaryString(n);\n        int even = 0;\n        int odd = 0;\n        int len = binaryString.length();\n        // Iterate from right to left of the string\n        // The index from the right is `i`\n        for (int i = 0; i < len; i++) {\n            // Character at index `len - 1 - i` corresponds to bit position `i`\n            if (binaryString.charAt(len - 1 - i) == '1') {\n                if (i % 2 == 0) { // Even index\n                    even++;\n                } else { // Odd index\n                    odd++;\n                }\n            }\n        }\n        return new int[]{even, odd};\n    }\n}\n```
### Algorithm
1. Convert the input integer `n` to its binary string representation using `Integer.toBinaryString(n)`.\n2. Initialize two counters, `even` and `odd`, to zero.\n3. Iterate from `i = 0` up to the length of the binary string. This `i` will represent the bit index from the right.\n4. In each iteration, access the character corresponding to the `i`-th bit from the right.\n5. If the character is '1':\n    - If `i` is even, increment `even`.\n    - If `i` is odd, increment `odd`.\n6. After the loop, return the result as an array `[even, odd]`.

## Iterative Bitwise Operations
This method avoids string conversion by using bitwise operations. It repeatedly checks the least significant bit (LSB) of the number `n`. If the LSB is 1, it increments the appropriate counter (`even` or `odd`) based on the current bit position. The number is then right-shifted to process the next bit, and the process continues until the number becomes zero.
**Time:** O(log n), as the loop runs once for each bit in the number `n`. The number of bits is proportional to log n. · **Space:** O(1), as it only uses a few variables to store the counts and the index, regardless of the size of n.
**Pros:** More efficient than the string approach in both time and space.; Works directly with the integer's binary representation.; Constant space complexity.
**Cons:** May be slightly less intuitive for developers not comfortable with bitwise operations.
### Explanation
This method uses bitwise operations to check each bit of the integer without converting it to a string. This is generally more efficient.\n\nThe algorithm proceeds as follows:\n- We loop as long as `n` is not zero.\n- In each iteration, we check the last bit of `n` using `n & 1`.\n- If it's 1, we check the current bit index's parity and update `even` or `odd`.\n- We then right-shift `n` by one (`n >>= 1`) to discard the last bit and move to the next one.\n- We increment the bit index.\n\n```java\nclass Solution {\n    public int[] evenOddBit(int n) {\n        int even = 0;\n        int odd = 0;\n        int index = 0;\n        while (n > 0) {\n            if ((n & 1) == 1) { // Check if the last bit is 1\n                if (index % 2 == 0) {\n                    even++;\n                } else {\n                    odd++;\n                }\n            }\n            n >>= 1; // Right shift to process the next bit\n            index++;\n        }\n        return new int[]{even, odd};\n    }\n}\n```
### Algorithm
1. Initialize `even = 0`, `odd = 0`, and a bit index counter `index = 0`.\n2. Start a loop that continues as long as `n > 0`.\n3. Inside the loop, check if the least significant bit is 1 using the bitwise AND operation: `(n & 1) == 1`.\n4. If the LSB is 1:\n    - If the current `index` is even, increment `even`.\n    - Otherwise, increment `odd`.\n5. Right-shift `n` by one position (`n >>= 1`) to process the next bit.\n6. Increment the `index` counter.\n7. After the loop terminates, return the array `[even, odd]`.

## Bitmasking and Population Count
This is the most efficient approach, leveraging bitmasking to isolate all even-indexed and odd-indexed bits at once. It uses a mask `0x55555555` (binary `0101...`) to get the set bits at even positions and a mask `0xAAAAAAAA` (binary `1010...`) for odd positions. After applying the masks, the number of set bits (population count) in each result is calculated using a highly optimized built-in function like `Integer.bitCount()`.
**Time:** O(1). The bitwise AND operations are single-cycle instructions. The `Integer.bitCount()` method is often implemented using a dedicated hardware instruction (`POPCNT`) or a fast bit-twiddling algorithm, making it effectively constant time for a fixed-size integer (e.g., 32-bit). · **Space:** O(1). This approach uses only a fixed number of variables, resulting in constant space usage.
**Pros:** Extremely fast and efficient, with constant time complexity.; Elegant and concise for those familiar with bit manipulation.
**Cons:** The 'magic numbers' (masks) can be obscure without explanation.; Relies on a specific built-in function (`Integer.bitCount()`) which, while standard, abstracts away the counting logic.
### Explanation
This highly efficient approach uses bitmasks to isolate all even-indexed and odd-indexed bits simultaneously. Then, it uses a built-in function to count the set bits in the masked results.\n\n- The mask `0x55555555` in binary is `01010101...`. When ANDed with `n`, it keeps only the bits at even positions (0, 2, 4, ...).\n- The mask `0xAAAAAAAA` in binary is `10101010...`. When ANDed with `n`, it keeps only the bits at odd positions (1, 3, 5, ...).\n- `Integer.bitCount()` is a hardware-accelerated instruction on many platforms that counts the number of 1s in an integer's binary representation very quickly.\n\n```java\nclass Solution {\n    public int[] evenOddBit(int n) {\n        // Mask for even indices: 01010101...\n        int evenMask = 0x55555555; \n        // Mask for odd indices: 10101010...\n        int oddMask = 0xAAAAAAAA;\n        \n        int evenCount = Integer.bitCount(n & evenMask);\n        int oddCount = Integer.bitCount(n & oddMask);\n        \n        return new int[]{evenCount, oddCount};\n    }\n}\n```
### Algorithm
1. Define a mask for even positions: `evenMask = 0x55555555`.\n2. Define a mask for odd positions: `oddMask = 0xAAAAAAAA`.\n3. Calculate the bits at even positions by `n & evenMask`.\n4. Count the number of set bits in the result using `Integer.bitCount()` to get the `even` count.\n5. Calculate the bits at odd positions by `n & oddMask`.\n6. Count the number of set bits in this result using `Integer.bitCount()` to get the `odd` count.\n7. Return the counts as `[even, odd]`.

# Solutions
### Java

```java
class Solution {
public
  int[] evenOddBit(int n) {
    int[] ans = new int[2];
    for (int i = 0; n > 0; n >>= 1, i ^= 1) {
      ans[i] += n & 1;
    }
    return ans;
  }
}

```

### Python

```python
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

```

### CPP

```cpp
class Solution {
public:
  vector<int> evenOddBit(int n) {
    vector<int> ans(2);
    for (int i = 0; n > 0; n >>= 1, i ^= 1) {
      ans[i] += n & 1;
    }
    return ans;
  }
};

```