Python bitwise And multiple numbers faster than an iterative bitwise operator?

Question

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

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

Currently, my code uses & operator in a loop that always calculates the bit of the result (even though we know that if we have 0 , then the next and all subsequent bits of the result will always be 0 ). One of my ideas is to calculate the bits in the columns, and for this column, stop calculating when there is 0 , because the result bit will be 0 .

Example (included in the 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 nice if this solution were expanded to, for example, the XOR operator.

I ask for some ideas on how to start implementing this in Python and maximize performance.

Thanks!

Answer 1

I would like Python to worry about optimization, it could be written trivially for the 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 , it took 0.758 seconds to complete 1,000,000 times 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
Intel Core i7-3740QM CPU @ 2.70 GHz
Memory 16.0 GB
OS 64-bit version of 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