better alternative to brute force xand binary operator

[cwarn23]

Hi everybody. I have a question about the best way to retrieve a list of possible source values from the & operator without checking every combination between the range required. The basic problem I face is I have (a&b)=c I know the values of b and c but need to find all possible values of a. Also note the minimum value of a is equal to c and the maximum value of a is ~(b^c) as demonstrated below. So I have already got in two variables the minimum and maximum possible values of a. Now I need to find the possible values between that range (a 64 bit range or unsigned long int). Can anybody tell me a more cpu efficient way of doing the below get_array() function as it hogs too much cpu especially after I put that function in a long loop. Like is there any way I can just get the binary value of the number and mathematically generate possible numbers based on where 1's and 0's pair with the maximum possible number and the variable b used on the first couple of lines?

import os
import operator       
a = 20 #answer to fetch
b = 11247
c = (a & b)
num = (b ^ c)

def xnot_inversebin(n):
    count=32
    #"""returns the binary of integer n, using count number of digits"""
    n = "".join([str((n >> y) & 1) for y in range(count-1, -1, -1)])
    bin = ''
    for i in range(0,32):
        if n[i] == '0':
            bin+='1'
        else:
            bin+='0'

    return int(bin,2)
    
def get_array(b,min,max):
    array=[0]
    count=32
    #a = "".join([str((max >> y) & 1) for y in range(count-1, -1, -1)])
    #bstr = "".join([str((c >> y) & 1) for y in range(count-1, -1, -1)])
    j=1
    i=min
    #for i in lrange(0,(max-min)):
    while i <= max:
        v=b&i
        if v==min:
            array.append(i)
            array[0]+=1;
            j=j+1
        i+=1
    return array

#now to use the functions
print xnot_inversebin(num) #maximum possible answer for a
print c #minimum possible answer for a
dat = get_array(b,c,xnot_inversebin(num))
print dat[0] #number of entries in the array of possible answers
os.system('pause')

Thanks.
cwarn23

[TrustyTony]

Your formula in text gives me strange maximum: negative value.

Brute force is very fast, I do not know why you need to optimize. If I only know that the number is maximum same bit length as maximum of b and c, which is known.

from __future__ import print_function
import os
import time
a = 20 #answer to fetch
b = 11247
c = (a & b)
print('b = %i, c = %i' % (b,c))
num = (b ^ c)
max_answer = 2**len(bin(max(b,c)))-1
print('Max answer: %i' % max_answer)
t0= time.time()
answers = list(a for a in range(c,max_answer) if c ==  a & b and num == b ^ c)
print ('Took %s ms' %(1000*(time.time()-t0)))
print ('Answers:', answers)
os.system('pause')

Running time for your number is about 32 ms in my computer.