Problem Statement

Given an unsigned integer (non-negative), the task is to compute the parity of the binary representation of that number. The goal is to determine if the number of set bits is even or odd.

Problem Understanding

Let's take the number 9 as an example. The binary representation of 9 is 1001. The number of set bits is 2, which is even. Therefore, the parity of 9 is even.

Possible Solutions

Brute Force Counting:

• Iterate through each bit in the binary representation of the number.
• Count the number of set bits.
• Check if the count is even or odd.

int computeParityBruteForce(int num) {
    int count = 0;
    while (num) {
        count += num & 1;
        num >>= 1;
    }
    return count % 2 == 0 ? 0 : 1; // 0 for even parity, 1 for odd parity
}

XOR-based Parity Checking:

• XOR (^) all the bits in the binary representation.
• The result will be 1 if the number of set bits is odd; otherwise, it will be odd.

int computeParityXOR(int num) {
    int result = 0;
    while (num) {
        result ^= num & 1;
        num >>= 1;
    }
    return result;
}

Brian Kernighan's Algorithm:

• Utilize the fact that n & (n-1) turns off the rightmost set bit.
• Continue this operation until n becomes 0.
• Count the number of iterations, and the parity will be based on whether the count is even or odd.

int computeParityBrianKernighan(int num) {
    int count = 0;
    while (num) {
        num = num & (num - 1);
        count++;
    }
    return count % 2;
}