Python bitwise AND on multiple numbers, faster way than iterative bitwise operator?

Question

I'm looking for a fastest way (O(n^2) is not acceptable) to apply an AND operator over more than 2 numbers in Python.

There are two scenarios:
a) on input we have numbers in a range between M and N
b) there can be a set of any natural numbers

Currently my code uses an & operator in a loop, which always compute a result bit (despite the fact that we know, that if we have 0, than the next and all next result bits will always be 0). One of my ideas is to compute bits per columns, and for a given column, stop computing when there is 0, because the result bit will be 0.

Example (included in test code below)

Existing (iterative), rather slow (O(n^2)) code:

def solution(M, N):
    result = M
    for x in xrange(M, N):
        result &= x
    return result


def solution_sets(N):
    result = N[0]
    for x in N:
        result &= x
    return result


print solution(5, 7)  # 4
print solution(64, 128)  # 64
print solution(44, 55)  # 32
print solution_sets([60, 13, 12, 21])

It would be good if this solution was expandable to for example XOR operator.

I'm asking for some ideas on how to start implementing this in the Python language and maximize performance.

Thanks!

Answer 1

I would let Python worry about the optimization, this could be written trivially for a sequence using functools.reduce and operator.and_

>>> functools.reduce(operator.and_, [60, 13, 12, 21])
4

Wrapping this in a function

def solution_sets(l):
    return functools.reduce(operator.and_, l)

---

Using timeit, to do this 1000000 times took 0.758 seconds in the following environment:

Python IDLE 3.4.1 (v3.4.1:c0e311e010fc, May 18 2014, 10:38:22) [MSC v.1600 32 bit (Intel)] on win32
Processor Intel Core i7-3740QM CPU @ 2.70 GHz
Memory 16.0 GB
OS 64-bit Windows 7

setup = '''
import functools
import operator

def solution_sets(l):
    return functools.reduce(operator.and_, l)'''

>>> timeit.timeit('solution_sets([60, 13, 12, 21])', setup)
0.7582756285383709