|Just another Perl shrine|
Boolean math: Fill in the blanks.by BrowserUk (Pope)
|on Oct 10, 2008 at 09:12 UTC||Need Help??|
BrowserUk has asked for the
wisdom of the Perl Monks concerning the following question:
If you pick a bunch of random 32-bit values and and average the number of bits set, if your PRNG is any good, the average will tend toward 16 (50% of 32).
Update: swapped AND & OR in the descriptions of the next two examples as pointed out by GrandFather++
If you pick another set, but this time bit-wise AND each pair of values together, and this time average the number of bits set in the results, the average will tend toward 8 (25%).
Do the same thing once more, this time bit-wise ORing each pair and the average number of bits in the results will tend toward 24 (75%).
By extending the number of values you combine to derive each result, whilst varying the sequence of AND & OR operations you use to combine them, you can derive sequences of values who's average number of bits tends toward each of the ordinal values 1 through 31. For example, using R to represent a random unsigned integer in the range 0 .. 2**32, you can derive an average that tends toward 1 by combining 5 R using AND:
If you alternatively OR 5 R together(substitute pack 'V', R | R | R | R | R; above), the average tends toward 31:
I've found some patterns in this. For example, to obtain the low order odd averages, you take the equation for double the value and apply & R to it's result. eg. to get 14, I have R & R | R & R, so to get 7 I use ( R & R | R & R ) & R. but that runs out for odd values greater than 15.
I've managed to find most of them through a combination of recognising some patterns and trial and error:
Firstly, I wonder if anyone can fill in those blanks?
Secondly, and more intellectually satisfying, is can anyone see an overall pattern that they can describe?
Finally, I do have a real use for this. It is not just intellectual curiosity. Thanks.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.