Home | Projects | Notes > Problem Solving > EPI - 5.1. Computing the Parity of a Word (bit manipulation)

EPI - 5.1. Computing the Parity of a Word (bit manipulation)

Solutions in C++

Solution 1

This solution uses brute-force approach that iteratively tests the value of each bit while tracking the number of 1s seen so far.

Complexity Analysis:

• $T=O(n)$$T = O(n)$, where $n$$n$ is the word size

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

Solution:

​x
1
short Parity(unsigned long x)
2
{
3
    short result = 0;
4

5
    while (x)
6
    {
7
        result += (x & 1);
8
        x >>= 1;
9
    }
10

11
    return result % 2;                                                        
12
}

This can be re-written as follows:

xxxxxxxxxx
12
1
short Parity(unsigned long x)
2
{
3
    short result = 0;
4

5
    while (x)
6
    {
7
        result ^= (x & 1);
8
        x >>= 1;
9
    }
10

11
    return result;
12
}

Solution 2

This solution improves the Solution 1 by using the technique "Erase the lowest set bit in a word in a single operation" (x = x & (x - 1).

Complexity Analysis:

• $T=O(k)$$T = O(k)$, where $k$$k$ is the number of bits set to 1 (e.g., $k$$k$ = 3 for 10001010₍₂₎)

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

Solution:

xxxxxxxxxx
12
1
short Parity(unsigned long x)
2
{
3
    short result = 0;
4
    
5
    while (x)
6
    {
7
        result ^= 1;
8
        x = x & (x - 1);    // Drop the lowest set bit of x
9
    }
10
    
11
    return result;
12
}