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)

Bitwise puzzle explained on an example

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!

You are unlikely to improve upon the performance of bitwise operations on integers, particularly if you write it in Python. — jonrsharpe
– jonrsharpe, Commented Jun 30, 2015 at 17:08
Even if there is a function that lets you AND multiple numbers, your CPU can likely only AND 2 numbers at a time, making your "efficient" function still O(n^2) at the CPU instruction level. — Adam Evans
– Adam Evans, Commented Jun 30, 2015 at 17:08
What makes you think your algorithm is O(n^2)? It's actually O(n). You can eliminate 1 iteration by using "xrange(M+1,N)" to avoid performing "result = M & M" on the first iteration. You can also stop early if result equals zero. It would still be O(n), though. It seems like you are working on a homework problem that you might be approaching in other than the prescribed way. — Heath Hunnicutt
– Heath Hunnicutt, Commented Jun 30, 2015 at 17:12
Thinking about it, you could possibly solve the M, N case analytically, and therefore write a function to calculate the answer in O(1). — jonrsharpe
– jonrsharpe, Commented Jun 30, 2015 at 17:13
I'm also baffled by your (apparent) claim that your current solution is O(n^2). It's O(n), unless the number of bits in each number can grow with n. — j_random_hacker
– j_random_hacker, Commented Jun 30, 2015 at 21:23

Cory Kramer · Accepted Answer · 2015-06-30 17:37:39Z

10

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

edited Jun 30, 2015 at 17:37

answered Jun 30, 2015 at 17:07

Cory Kramer

119k19 gold badges176 silver badges233 bronze badges

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

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related