next up previous

4.2.2 Reproduction     continued...

This operation is actually quite simple if we have a random number generator that creates a random sequence of 1's and 0's. As a first approximation, we can just use the standard C library procedure, which returns a random integer (see the exercise at the end of this section). Let r be the result of one call to random(). Where there is a 1 bit in r we will take a bit from the top strand, and where there is a 0 bit in r we will take a bit from the bottom strand. In C, the definition of the new strand s from parent strands y and z is straightforward:

  s = (x & r) | (y & ~r);
This expression takes the bitwise AND of a parent strand and r, which will be 1 only where r is 1 and the parent is 1, and ``ors'' it with the bitwise AND of the negation of r, which will be 1 where r is 0 and the parent is 1. Thus the 1s in the parents are copied to the child under control of the random number r.