CODEWITHSUNDEEP
python-3.xbitwise-operatorsbit-shift
Ryan
Ryan

Reputation: 1432

Bitwise operations Python

This is a first run-in with not only bitwise ops in python, but also strange (to me) syntax.

for i in range(2**len(set_)//2):
        parts = [set(), set()]
        for item in set_:
            parts[i&1].add(item)
            i >>= 1

For context, set_ is just a list of 4 letters.

There's a bit to unpack here. First, I've never seen [set(), set()]. I must be using the wrong keywords, as I couldn't find it in the docs. It looks like it creates a matrix in pythontutor, but I cannot say for certain. Second, while parts[i&1] is a slicing operation, I'm not entirely sure why a bitwise operation is required. For example, 0&1 should be 1 and 1&1 should be 0 (carry the one), so binary 10 (or 2 in decimal)? Finally, the last bitwise operation is completely bewildering. I believe a right shift is the same as dividing by two (I hope), but why i>>=1? I don't know how to interpret that. Any guidance would be sincerely appreciated.

Upvotes: 0

Views: 954

Answers (2)

jasonharper
jasonharper

Reputation: 9622

[set(), set()] creates a list consisting of two empty sets.

0&1 is 0, 1&1 is 1. There is no carry in bitwise operations. parts[i&1] therefore refers to the first set when i is even, the second when i is odd.

i >>= 1 shifts right by one bit (which is indeed the same as dividing by two), then assigns the result back to i. It's the same basic concept as using i += 1 to increment a variable.

The effect of the inner loop is to partition the elements of _set into two subsets, based on the bits of i. If the limit in the outer loop had been simply 2 ** len(_set), the code would generate every possible such partitioning. But since that limit was divided by two, only half of the possible partitions get generated - I couldn't guess what the point of that might be, without more context.

Upvotes: 2

user555045
user555045

Reputation: 64913

I've never seen [set(), set()]

This isn't anything interesting, just a list with two new sets in it. So you have seen it, because it's not new syntax. Just a list and constructors.

parts[i&1]

This tests the least significant bit of i and selects either parts[0] (if the lsb was 0) or parts[1] (if the lsb was 1). Nothing fancy like slicing, just plain old indexing into a list. The thing you get out is a set, .add(item) does the obvious thing: adds something to whichever set was selected.

but why i>>=1? I don't know how to interpret that

Take the bits in i and move them one position to the right, dropping the old lsb, and keeping the sign. Sort of like this

arithmetic shift

Except of course that in Python you have arbitrary-precision integers, so it's however long it needs to be instead of 8 bits.

For positive numbers, the part about copying the sign is irrelevant.

You can think of right shift by 1 as a flooring division by 2 (this is different from truncation, negative numbers are rounded towards negative infinity, eg -1 >> 1 = -1), but that interpretation is usually more complicated to reason about.

Anyway, the way it is used here is just a way to loop through the bits of i, testing them one by one from low to high, but instead of changing which bit it tests it moves the bit it wants to test into the same position every time.

Upvotes: 1

Related Questions