Interesting puzzle II

First, consider a function P(x) where:

  P(x) returns:
   true if the number of 1 bits set in the
     binary representation of x is prime,

   false otherwise.

For example, P(239) returns true, while P(51) returns false.

Next, consider the following function prime_bits:

  uint64_t prime_bits(uint64_t a, uint64_t b);

A call to prime_bits(a, b) returns the number of values between a and b inclusive for which P(x) is true. For example, prime_bits(4, 10) returns 5, while prime_bits(137, 31415926535897) returns 7753256197126. Your job is to implement the prime_bits function.

Your implementation should be efficient, and it should be wrapped up nicely such that one can specify a and b on the commandline when running your program. You may expect the range of a and b to be limited to non-negative 64-bit integers, though it would certainly be uncouth for your algorithm to break down for larger values.

Your implementation should have a running time faster than O(n), where n is b - a.