Proper way to do bitwise difference? (python 2.7)

Question

I am storing sets of values as python long integers, in the form of distinct 2**i sums, because python allows bitwise operations on it's integers. For many of my programs this is much faster than using data structures.

I often find myself wanting to take the difference of two bitwise values.

Example:

Let's say I have two values, represented by 2 and 4. By union they form a set, the value 6. (110) I then have a second set, decimal value 10(binary 1010), which is 2 and 8.

I want to find the value that is in the first set, and not in the second set. If I was using set structures, I would take set difference. But I am using integers. If I try to do difference, it won't work (it would be -4).

As of now, I find myself doing value1 - (value1&value2). This requires two separate operations to find the difference. Is there a way I can take advantage of what python offers to quickly do this in one operation instead of two?

Answer 1

Set difference B-A is just the intersection of B and the complement of A.

And, while there's no bitwise difference operator, there are bitwise intersection (&) and bitwise complement (~) operators. So:

b_minus_a = b & ~a

Or, using your example:

>>> b, a = 0b110, 0b1010
>>> b & ~a
4
>>> bin(_)
0b100

---

You can of course wrap this up in a function:

def bitsetdiff(b, a):
    return b & ~a

---

But if you're going to be doing a lot of this kind of stuff, and bitwise operations don't come naturally to you, you may want to search PyPI for libraries for bit set and bitset, which will give you an object that acts like a set of boolean values, but is stored as (and can be efficiently converted to and from) an integer.

I chose intbitset because it looks promising:

>>> b = intbitset([2, 4])
>>> a = intbitset([2, 8])
>>> b - a
intbitset([4])

Just like using sets. But I don't see any obvious way to access the value as one big integer. There might be other libraries that fit your needs better; I only picked one after a quick scan.

Answer 2

Not in one operation, but you should stick to bit operations (not + or -). If you want the bits in value1 not in value2, the ordinary way to spell that is

value1 & ~value2

That is, the intersection of value1 with the complement of value2 (note that the unary prefix operator there is ~, not -).