Clever large integers

Where bitmap is a Python long, consider the innocent looking Python expression:

bitmap = bitmap & ~(1L << bit)

This is the perfectly normal way of clearing a bit in a bitmap, so it looks like there's nothing peculiar going on here.

Except that Python longs are of indefinite (and theoretically infinite) length, and what makes this expression work in normal integers is that the two pieces have the same (finite) size. So Python is clearly not just doing straight binary operations here; the implementation of ~ and & for longs has to be more complicated than just manipulating bit representations.

All of this goes to illustrate that sometimes features aren't as simple as they look.

As it turns out, this cleverness has a cost, at least in Python. If you already know that the bit is set, clearing it with bitmap - (1L << bit) starts out being about twice as fast as the AND approach (when operating on bit 0) and gets better from there. I'm ambivalent about whether or not you want to check the bit's status ahead of setting or clearing it; while it may avoid extra object allocations and deallocations, it's relatively expensive and I haven't completely convinced myself that it actually avoids all that much object churn.

(Checking plus subtraction is usually slower than the AND approach alone; it gets slightly faster when we start operating around bit 2048 and up. Of course, large bits is exactly where you probably want a faster representation of your bitmaps than a large integer, which should speed everything up.)