CODEWITHSUNDEEP
pythonbit-manipulation
Padraic Cunningham
Padraic Cunningham

Reputation: 180391

struggling to understand bitwise operators in python

I am struggling to understandwhat the "if (i >> j) % 2 ==1 " does in the following function or any function for that matter?

def powerSet(items):

    N = len(items)
    for i in xrange(2**N): 
               combo = []
        for j in xrange(N):
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

Upvotes: 2

Views: 1897

Answers (3)

Fred Foo
Fred Foo

Reputation: 363537

It checks whether the j'th bit of the binary number i, counting from the end, is set. i >> j right-shift, so the final j bits are gone. n % 2 == 1 is the familiar check for odd numbers, which in binary have their last bit set.

EDIT: this is generating a power set as follows. The outer loop walks through all 2**N subsets of items, each represented as a binary integer. The inner loop then constructs the actual subset by checking which of the N final bits of these integers are set, using the bits as indicators of subset membership.

E.g., suppose that N=5. Then at some point, i will be 0b10011. From that, the set [items[0], items[1], items[4]] can be constructed. First reverse the bits, because they're numbered right-to-left by j:

1          1         0          0          1
items[0]   items[1]  (nothing)  (nothing)  items[4]

(Try printing i and combo inside the inner loop.)

Upvotes: 6

Sason Torosean
Sason Torosean

Reputation: 572

As an alternate flavour to larsmans already complete solution, here is how I understood it.

i >> j simply means i/pow(2,j), which mathematically means i/2^j [obviously we are in integer space]. lets set n=i/2^j. When you have n % 2 == 1 you ask if n mod 2 is 1? if it is then n must be odd, else n must be even.

Source: http://docs.python.org/2/reference/expressions.html

Upvotes: 0

tdelaney
tdelaney

Reputation: 77337

You can print the numbers in binary as the operation progresses to see how it works. Here's an example with i=1234 and j=4.

1234 in binary

>>> '{:b}'.format(1234)
'10011010010'

shifting right 4 places causes the rightmost bits (0010) to fall away

>>> '{:b}'.format(1234>>4)
'1001101'

the modulo operation divides by 2 and gives you the remainder

>>> '{:b}'.format((1234>>4)%2)
'1'

its also common to do this with the & operation

>>> '{:b}'.format((1234>>4)&1)
'1'

if you have a number where the 4th bit (from zero) is zero, you get a zero

>>> '{:b}'.format((1234+0b10000>>4)&1)
'0'

Upvotes: 3

Related Questions