1. Parity of a Word

Question : Compute the parity of a 64-bit word.
Parity of a number refers to whether it contains an odd or an even number of 1’s in its binary representation. The parity of a number is 1 if it contains odd number of 1’s, else 0.

Method-1 : Brute Force
We can iteratively test the value of each bit while tracking the number of 1’s seen so far.

int Parity (long x){
	int result=0;
	while(x){
		result+=(x&1);
		x>>1;
	}
	return result%2;
}

 

The Time Complexity : O(n), where n is the number of bits in the word.
The Space Complexity : O(1), only a constant amount of extra space required.

Method-2 : A better Approach
We can apply the method that is used to compute the number of 1’s in the bit representation of a number.

int Parity (int x){
	int result=0;
	while(x){
		x=x&(x-1); // removes the lowest set bit.
		result^=1;
	}
	return result;
}

x-1 contains last set bit of x as unset, hence there AND unsets that bit.
The Time Complexity : O(k), where k is the number of SET bits.
The Space Complexity : O(1), only a constant amount of extra space is required.

Method-3: CACHE!
The original question asks us the compute the parity of a 64 bit number, previous methods are sufficiently fast to compute parity for such numbers, though if the computation has to take place for many numbers it is a better idea to cache our solutions and use them when required. Caching 2^64(9223372036854775808) numbers? Ah! does not look like a good idea. Better we can cache answers to first 2^16 numbers and then compute solution for larger numbers by combining the solutions of smaller segments. For a 64 bit number we’ll break the number into 4 segments of 16 bits. We’ll use the table to compute parities of all the 4 segments and then XOR the values to compute the final answer.

void precompute (void){
	for (int i=0;i<=int(pow(2,(sizeOfInt/4))-1);i++){
		Table[i]=parity(i);
		//cout<<i<<' '<<Table[i]<<endl; Uncomment this to check for yourself
	}
	return ;
}

 

int parityAns( int ParityOf, int BitMask, int wordSize){
	return ( Table [ParityOf>>( 3 * wordSize)]
	^ Table[( ParityOf >>  ( 2 * wordSize ) ) & BitMask]
	^ Table[( ParityOf >> ( wordSize ) ) & BitMask]
	^ Table[ ParityOf & BitMask] );
}


The Time Complexity : O(n/L + 2^L)
, where n is the number of bits in the word and L is the width of the word for which we cache the results. 2^L time will be taken to prepare the table, if L is known beforehand we can remove it from the notation, as we only talk about the growth of function in Big-Oh Notation.
The Space Complexity : O(2^L), only a constant amount of extra space required.

Method-4 The Final Blow
We can use the property of XOR to compute the parity.
say X consists of 4 bits(a,b,c,d), we ran the following steps on it.

X =        a     b     c     d
X=X^X>>1 = a    a^b   b^c   c^d
X=X^X>>2 = a    a^b  a^b^c a^b^c^d

The last bit contains the parity which we can extract by ANDing X with 1.

int parity(int ParityOf){
	int factorOfShift = sizeOfInt/2;
	while(factorOfShift){
		ParityOf^=(ParityOf>>factorOfShift);
		factorOfShift=factorOfShift/2;
	}
	return ParityOf & 0x1;
}

The Time Complexity : O(log n), where n is the number of bits in the word.
The Space Complexity : O(1), only a constant amount of extra space required.

Also we can combine the last 2 methods, the full working code to which is available at Github, you can star the repository to get updates. You can also follow this blog for more such posts. Comment in your queries, report bugs, discuss! 🙂

Advertisements

4 thoughts on “1. Parity of a Word

  1. Nice post!
    It’s incredibly nice to understand the basics behind the working of this, but just for the sake of speed and for contest purposes it’s probably better to use built in functions too.

    #include
    using namespace std;
    int sizeOfInt=sizeof(int)*8;
    int parity(int ParityOf){
    int factorOfShift = sizeOfInt/2;
    while(factorOfShift){
    ParityOf^=(ParityOf>>factorOfShift);
    factorOfShift=factorOfShift/2;
    }
    return ParityOf & 0x1;
    }

    main()
    {
    for(int i = 1; i < 1000000; i++)
    {
    if((__builtin_popcount(i)%2) != parity(i))cout << "Results not matching\n";
    }
    clock_t begin_time = clock();
    begin_time = clock();
    for(int i = 1; i < 100000; i++)parity(i);
    cout << float( clock () – begin_time ) / CLOCKS_PER_SEC << "\n\n";

    begin_time = clock();
    for(int i = 1; i < 100000; i++)__builtin_popcount(i)%2;
    cout << float( clock () – begin_time ) / CLOCKS_PER_SEC << "\n\n";
    }

    Run the program above to see a few benchmarks and you would find a speed improvement of at least 5-10 times.

  2. Yes, you are spot on! But this post focuses a programming interview scenerio, from a CP perspective sure, I would do a post on the builtin functions. It is always better to use them if they exist to solve the purpose.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s