Beautiful Code [152]
bits bitsum data
0x00000005 0 A[0]
0x00018001 2 A[2]
0x80000000 5 A[32]
A[47]
A[48]
A[95]
Here's the key task: given a "logical" index i into the full array, translate it into the "physical" index sparse_i where the array element is stored, if that element exists, or give some indication if it does not exist. For the array in the previous table, we wish to translate 47 to 3, 48 to 4, and 49 to "does not exist." Given a logical index i, the corresponding index sparse_i into the data array is given by the number of 1-bits in array bits that precede the bit corresponding to i. This may be calculated as follows:
j = i >> 5; // j = i/32.
k = i & 31; // k = rem(i, 32);
mask = 1 << k; // A "1" at position k.
if ((bits[j] & mask) == 0) goto no_such_element;
mask = mask - 1; // 1's to right of k.
sparse_i = bitsum[j] + pop(bits[j] & mask);
The space cost of this representation is two bits per position in the full array.
The population count function can be used to generate binomially distributed random integers. To generate an integer drawn from a population given by Binomial(t, p) where t is the number of trials and p = 1/2, generate t random bits and count the number of 1s in the t bits. This can be generalized to probabilities p other than 1/2.[]
[] See section 3.4.1, problem 27 in Donald E. Knuth, The Art of Computer Programming: Seminumerical Algorithms (Vol. 2, 3rd. ed.). Addison-Wesley, 1998.
According to computer folklore, population count is important to the National Security Agency. No one (outside of NSA) seems to know just what they use it for, but it may be in cryptography work or in searching huge amounts of material.
Secure Communication: The Technology Of Freedom > The Heart of the Start
11. Secure Communication: The Technology Of Freedom
Ashish Gulhati
I speak of none other than the computer that is to come after me. A computer whose merest operational parameters I am not worthy to calculate—and yet I will design it for you. A computer which can calculate the Question to the Ultimate Answer, a computer of such infinite and subtle complexity that organic life itself shall form part of its operational matrix.
Deep Thought, The Hitchhiker's Guide to the Galaxy
In mid-1999 i flew to costa rica to work with laissez faire city, a group that was working to create software systems to help usher in a new era of individual sovereignty.[*]
[*] See The Sovereign Individual: Mastering the Transition to the Information Age, James Dale Davidson and Sir William Rees Mogg, Free Press, 1999.
The group at LFC was working primarily to develop a suite of software designed to protect and enhance individual rights in the digital age, including easy-to-use secure email, online dispute mediation services, an online stock exchange, and a private asset trading and banking system. My interest in many of the same technologies had been piqued long ago by the cypherpunks list and Bruce Schneier's Applied Cryptography (Wiley), and I'd already been working on prototype implementations of some of these systems.
The most fundamental of these were systems to deliver strong and usable communications privacy to just about everybody.
When I stepped into LFC's sprawling "interim consulate" outside San José, Costa Rica, they had a working prototype of a secure webmail system they called MailVault. It ran on Mac OS 9, used FileMaker as its database, and was written in Frontier. Not at all the mix of technologies you'd want to run a mission-critical communications service on, but that's what the programmers had produced.
It was no surprise the system crashed early and often, and was extremely fragile. It could hardly support two concurrent users. LFC was facing a credibility crisis with its investors, as their software releases had been delayed many times, and their