How to access list elements with a binary-patern (bitwise) counting in python

Question

I am having a difficulty in finding a way to access some list elements that are represented on a binary access pattern. What I mean is:

Suppose that we have a binary number Bin of 4 digits: Bin = 0b0000 We also have a list (or set or tuple, does not matter) of same length as Bin, lets say: list = [A, B, C, D]

Now, I want to combinatory access the elements that are represented by 1 in Bin meaning that as the counter increments +1 on each loop if we are at Bin = 0b0101 (which means Bin = 10) then I want to access the corresponding indices, hence B and D elements in the list.

Same goes until the loop ends when Bin = 0b1111 or Bin = 15 where I finally access all elements of list A, B, C, D.

Thanks in advance.

@PadraicCunningham Yes since binary is 2^n where n is the length but how am I supposed to check the 1 in the number? Use an operator maybe? — BugShotGG
– BugShotGG, Commented Jul 6, 2014 at 21:47

Padraic Cunningham · Accepted Answer · 2014-07-06 22:01:41Z

1

This is a powerset generator used on the M.I.T 6.00x course.

def powerSet(items):
    n = len(items)
    for i in xrange(2**n):
        combo = []
        for j in xrange(n):  
            #print i,j,(i >> j) % 2 == 1 # uncomment to see the values through the loop
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo
print list(powerSet([1,2,3,4]))
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

if (i >> j) % 2 == 1 can also be written as if (i >> j) & 1

It uses the >> Bitwise Operator.

*x >> y Returns x with the bits shifted to the right by y places. This is the same as //'ing x by 2**y.*

edited Jul 6, 2014 at 22:01

answered Jul 6, 2014 at 21:51

Padraic Cunningham

181k30 gold badges264 silver badges327 bronze badges

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

2 Comments

jonrsharpe Over a year ago

There's a much neater implementation in the itertools recipes.

Padraic Cunningham Over a year ago

@jonrsharpe, it helped me learn about powersets and the how the >> operator worked, I know there are better implementations but this helped me a lot.

Daniel · Accepted Answer · 2014-07-06 22:28:33Z

0

If you don't need the full power-set:

def bin_access(iterable, index):
    return [b for a,b in zip(reversed(bin(index)[2:]), iterable) if a=='1']

answered Jul 6, 2014 at 22:28

Daniel

42.9k4 gold badges57 silver badges82 bronze badges

1 Comment

BugShotGG Over a year ago

Could you add some explanation or comments? Thanks

Collectives™ on Stack Overflow

How to access list elements with a binary-patern (bitwise) counting in python

2 Answers 2

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related