> > Yes. The thing is that you need to convince yourself that this is still > > uniformly distributed over the wanted numbers. But it's correct. In > > fact, it's enough to flip a fixed bit, so you can get away with one call > > to arc4random(). > > Its not immediately obvious because this is not always true. > Only true if your bad seed was at least surjective onto the desired codomain.
Since we start from a uniform distribution, surjective is not good enough. It needs to be n:1. Flipping the k-th bit swaps the numbers of odd parity (good seeds) with the numbers of even parity (bad seeds). The suggested construction of keeping a good seed and flipping the k-th bit of a bad one yields a 2:1 mapping from all 16-bit numbers onto those with odd parity. We're good. David Higgs's code is also correct. Probably the easiest way to see that is to start from a uniform distribution on [0, 2^16-1] x [0, 15] and map it 32:1 onto the good seeds -- (x, k) maps to x if x is good, and to x with the k-th bit flipped if x is bad.
