Thanks for all the comments.  Here's an updated patch, with quite a few 
changes:

code:
 - drop lookup tables in favour of "while(x) {x >>= 1; count += 1;}"
 - add example to docstring, and use PyDoc_STRVAR macro for docstrings

docs:
 - add "bin(37)" to whatsnew example
 - move main documentation out of the bit operations table into its own
   subsection, so that it can be indexed properly.
 - expand main documentation with examples, informal definition,
   equivalent Python code
 - I dropped the 1 + math.floor(...) definition from the docs, judging
   that 1 informal, 1 formal and 1 Python definition should be enough.

tests:
 - as proposed by Raymond, directly check equivalence with formal
   definition, equivalent Python code, and two other possible definitions.

(FWIW I prefer 'x>>1' over 'x//2' in the Python code, because it's more 
immediately related to the intended sense:  the operation should be 
thought of as a bit shift rather than a division.)