Python equivalent of C code from Bit Twiddling Hacks?

Question

I have a bit counting method that I am trying to make as fast as possible. I want to try the algorithm below from Bit Twiddling Hacks, but I don't know C. What is 'type T' and what is the python equivalent of (T)~(T)0/3?

A generalization of the best bit counting method to integers of bit-widths upto 128 (parameterized by type T) is this:

v = v - ((v >> 1) & (T)~(T)0/3);      // temp 
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
c = (T)(v * ((T)~(T)0/255)) >> (sizeof(v) - 1) * CHAR_BIT; // count

Answer 1

T is a integer type, which I'm assuming is unsigned. Since this is C, it'll be fixed width, probably (but not necessarily) one of 8, 16, 32, 64 or 128. The fragment (T)~(T)0 that appears repeatedly in that code sample just gives the value 2**N-1, where N is the width of the type T. I suspect that the code may require that N be a multiple of 8 for correct operation.

Here's a direct translation of the given code into Python, parameterized in terms of N, the width of T in bits.

def count_set_bits(v, N=128):
    mask = (1 << N) - 1

    v = v - ((v >> 1) & mask//3)
    v = (v & mask//15*3) + ((v >> 2) & mask//15*3)
    v = (v + (v >> 4)) & mask//255*15
    return (mask & v * (mask//255)) >> (N//8 - 1) * 8

Caveats:

(1) the above will only work for numbers up to 2**128. You might be able to generalize it for larger numbers, though.

(2) There are obvious inefficiencies: for example, 'mask//15' is computed twice. This doesn't matter for C, of course, because the compiler will almost certainly do the division at compile time rather than run time, but Python's peephole optimizer may not be so clever.

(3) The fastest C method may well not translate to the fastest Python method. For Python speed, you should probably be looking for an algorithm that minimizes the number of Python bitwise operations. As Alexander Gessler said: profile!

Answer 2

What you copied is a template for generating code. It's not a good idea to transliterate that template into another language and expect it to run fast. Let's expand the template.

(T)~(T)0 means "as many 1-bits as fit in type T". The algorithm needs 4 masks which we will compute for the various T-sizes we might be interested in.

>>> for N in (8, 16, 32, 64, 128):
...     all_ones = (1 << N) - 1
...     constants = ' '.join([hex(x) for x in [
...         all_ones // 3,
...         all_ones // 15 * 3,
...         all_ones // 255 * 15,
...         all_ones // 255,
...         ]])
...     print N, constants
...
8 0x55 0x33 0xf 0x1
16 0x5555 0x3333 0xf0f 0x101
32 0x55555555L 0x33333333L 0xf0f0f0fL 0x1010101L
64 0x5555555555555555L 0x3333333333333333L 0xf0f0f0f0f0f0f0fL 0x101010101010101L
128 0x55555555555555555555555555555555L 0x33333333333333333333333333333333L 0xf0f0f0f0f0f0f0f0f0f0f0f0f0f0f0fL 0x1010101010101010101010101010101L
>>>

You'll notice that the masks generated for the 32-bit case match those in the hardcoded 32-bit C code. Implementation detail: lose the L suffix from the 32-bit masks (Python 2.x) and lose all L suffixes for Python 3.x.

As you can see the whole template and (T)~(T)0 caper is merely obfuscatory sophistry. Put quite simply, for a k-byte type, you need 4 masks:

k bytes each 0x55
k bytes each 0x33
k bytes each 0x0f
k bytes each 0x01

and the final shift is merely N-8 (i.e. 8*(k-1)) bits. Aside: I doubt if the template code would actually work on a machine whose CHAR_BIT was not 8, but there aren't very many of those around these days.

Update: There is another point that affects the correctness and the speed when transliterating such algorithms from C to Python. The C algorithms often assume unsigned integers. In C, operations on unsigned integers work silently modulo 2**N. In other words, only the least significant N bits are retained. No overflow exceptions. Many bit twiddling algorithms rely on this. However (a) Python's int and long are signed (b) old Python 2.X will raise an exception, recent Python 2.Xs will silently promote int to long and Python 3.x int == Python 2.x long.

The correctness problem usually requires register &= all_ones at least once in the Python code. Careful analysis is often required to determine the minimal correct masking.

Working in long instead of int doesn't do much for efficiency. You'll notice that the algorithm for 32 bits will return a long answer even from input of 0, because the 32-bits all_ones is long.