0

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.

Improve this question

2 Answers 2

Reset to default
2

[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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Much appreciated. This is a terrific answer in lay man's terms, which is (obviously) my speed at the moment! Thanks again!
1

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.

Improve this answer

1 Comment

Wow, fantastic! Thank you so very much! A hurdle seems to be using bitwise ops to get things done whereas I would ordinarily try to keep things in decimal for and let the bitwise operations happen under the hood and out of sight. Very illuminating!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.