Home | Projects | Notes > Problem Solving > LC - E - 2595. Number of Even and Odd Bits (bit manipulation)

LC - E - 2595. Number of Even and Odd Bits (bit manipulation)

Solutions in C

Solution 1

This solution uses bitwise operations.

Complexity Analysis:

• $T=O(\log n)$$T = O(\log n)$ where $n$$n$ is the given integer value

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
19
1
/**
2
 * Note: The returned array must be malloced, assume caller calls free().
3
 */
4
int* evenOddBit(int n, int* returnSize){
5
    *returnSize = 2;
6
    int *answer = (int *)calloc(*returnSize, sizeof(int));
7
    int i;
8
    int temp = n;
9
    
10
    // count even
11
    for (i = 0; 2 * i < 32; i++)
12
        answer[0] += (temp >> (2 * i) & 1);
13

14
    // count odd
15
    for (i = 0; 2 * i + 1 < 32; i++)
16
        answer[1] += (n >> (2 * i + 1) & 1);
17

18
    return answer;
19
}

Solution 2

This solution uses bitwise operations. (e.g., Bit masking)

Complexity Analysis:

• $T=O(k)$$T = O(k)$ where $k$$k$ is the number of bits set to 1 in the given integer n (On average more efficient than $O(n)$$O(n)$)

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
29
1
/**
2
 * Note: The returned array must be malloced, assume caller calls free().
3
 */
4
int* evenOddBit(int n, int* returnSize){
5
    unsigned int bitmask_odd = 0xAAAAAAAA;  // 01010101 01010101 01010101 01010101
6
    unsigned int bitmask_even = 0x55555555; // 10101010 10101010 10101010 10101010
7
    int ncopy = n;
8
    *returnSize = 2;
9

10
    int *answer = (int *)calloc(2, sizeof(int));
11

12
    // count 'even'
13
    ncopy &= bitmask_even;
14
    while (ncopy)
15
    {
16
        ncopy &= (ncopy - 1);
17
        answer[0]++;
18
    }
19

20
    // count 'odd'
21
    n &= bitmask_odd;
22
    while (n)
23
    {
24
        n &= (n - 1);   // drop the lowest set bit of 'n'
25
        answer[1]++;
26
    }
27

28
    return answer;
29
}