[jwilk]

That can't be right:

  // Returns k with probability 2^(k-1).

Did you mean 2^(-k-1)?

[orlp]

Yes, woops, fixed.