There are some good answers here already, but I'm going to take a crack at it too =) Say you have a random hash function that produces (unsigned) int values.

There are some good answers here already, but I'm going to take a crack at it too =) Say you have a random hash function that produces (unsigned) int values. So, for all inputs, hash(x) will be in the range [0, 2^32). - How many different inputs would you need to feed it before you would expect to see hash(x) == 0? ... uh, like, billions? - How many different inputs would you need to feed it before you would expect to see hash(x) < 2? ... well, still in the billions, but maybe half as many as finding hash(x) == 0.. - How many different inputs would you need to feed it before you would expect to see hash(x) < 4? .. 8? .. 16? .. 32? ... all the way up to < 2^31 (typically you'll see this within two tries) and 2^32 (all of them). ... and so on and so forth; math does the rest. The "count the leading zeroes" check is the same as "the hashcode is less than 2^X". To prevent a single "lucky" hash from throwing off your estimate, you process your inputs in batches and average their estimates.