5-2 Parity

The "parity" of a string refers to whether it contains an odd or an even number of 1-bits. The string has "odd parity" if it contains an odd number of 1-bits; otherwise, it has "even parity."

Computing the Parity of a Word

Here we mean to produce a 1 if a word x has odd parity, and a 0 if it has even parity. This is the sum, modulo 2, of the bits of x梩hat is, the exclusive or of all the bits of x.

One way to compute this is to compute pop(x); the parity is the rightmost bit of the result. This is fine if you have the population count instruction, but if not, there are better ways than using the code for pop(x).

A rather direct method is to compute

graphics/05icon13.gif

 

where n is the word size, and then the parity of x is given by the rightmost bit of y. (Here denotes exclusive or, but for this formula, ordinary addition could be used.)

The parity may be computed much more quickly, for moderately large n, as follows (illustrated for n = 32; the shifts can be signed or unsigned):

Equation 3

graphics/05icon14.gif

 

This executes in ten instructions, as compared to 62 for the first method, even if the implied loop is completely unrolled. Again, the parity bit is the rightmost bit of y. In fact, with either of these, if the shifts are unsigned, then bit i of y gives the parity of the bits of x at and to the left of i. Furthermore, because exclusive or is its own inverse, xi xj is the parity of bits i - 1 through j, for i j.

This is an example of the "parallel prefix," or "scan" operation, which has applications in parallel computing [KRS; HS]. Given a sufficient number of processors, it can convert certain seemingly serial processes from O(n) to O(log2 n) time. For example, if you have an array of words and you wish to compute the exclusive or scan operation on the entire array of bits, you can first use (3) on each word of the array, and then use essentially the same technique on the array, doing exclusive or's on the words of the array. This takes more elementary (word length) exclusive or operations than a simple left-to-right process, and hence it is not a good idea for a uniprocessor. But on a parallel computer with a sufficient number of processors, it can do the job in O(log2 n) rather than O(n) time (where n is the number of words in the array).

A direct application of (3) is the conversion of an integer to Gray code (see page 236).

If the code (3) is changed to use left shifts, the parity of the whole word x winds up in the leftmost bit position, and bit i of y gives the parity of the bits of x at and to the right of position i.

If rotate shift's are used, the result is a word of all 1's if the parity of x is odd, and of all 0's if even.

The following method executes in nine instructions and computes the parity of x as the integer 0 or 1 (the shifts are unsigned).

x = x ^ (x >> 1); 
x = (x ^ (x >> 2)) & 0x11111111; 
x = x*0x11111111; 
p = (x >> 28) & 1; 

After the second statement above, each hex digit of x is 0 or 1, according to the parity of the bits in that hex digit. The multiply adds these digits, putting the sum in the high-order hex digit. There can be no carry out of any hex column during the add part of the multiply, because the maximum sum of a column is 8.

The multiply and shift could be replaced by an instruction to compute the remainder after dividing x by 15, giving a (slow) solution in eight instructions, if the machine has remainder immediate.

Adding a Parity Bit to a 7-Bit Quantity

Item 167 in [HAK] contains a novel expression for putting even parity on a 7-bit quantity that is right-adjusted and isolated in a register. By this we mean to set the bit to the left of the seven bits, to make an 8-bit quantity with even parity. Their code is for a 36-bit machine, but it works on a 32-bit machine as well.

graphics/05icon15.gif

 

Here, modu(a, b) denotes the remainder of a upon division by b, with the arguments and result interpreted as unsigned integers, "*" denotes multiplication modulo and the constant 1920 is 15 ?7. Actually, this computes the sum of the bits of x, and places the sum just to the left of the seven bits comprising x. For example, the expression maps 0x0000007F to 0x000003FF, and 0x00000055 to 0x00000255.

Another ingenious formula from [HAK] is the following, which puts odd parity on a 7-bit integer:

graphics/05icon16.gif

 

where 1152 = 9 ?27. To understand this, it helps to know that the powers of 8 are ?1 modulo 9. If the 0x3DB6DB00 is changed to 0xBDB6DB00, this formula applies even parity.

These methods are not practical on today's machines, because memory is cheap but division is still slow. Most programmers would compute these functions with a simple table lookup.

Application

The parity operation is useful in multiplying bit matrices in GF(2) (in which the add operation is exclusive or).