bit operations and testing for exponent of two

[dancks]

I'm writing a basic sudoku solver. I have a simple method that looks for squareas with only 1 possible number and fills them in before trying to solve the puzzle.

the method look like this:

def fillinones(sq):
    table = {1:1,2:2,4:3,8:4,16:5,32:6,64:7,128:8,256:9}
    for i in range(0,80):
        p=checkpossible(sq,i)
        print "p: ",p
        if p & ~(p & (p - 1)):
            sq[i] = table[p]

checkpossible returns a number that has uses bits to represent the possible numbers that can go in a blank square. so 1:1,2:2,4:3,etc up to nine, which is what the table does.

so if only one number can fit into the square, p must be an exponent of 2. p & ~(p & (p - 1)) fails to differentiate non 2-exponent numbers. logically it seems to make since since base 2 32: 100000 and 31: 011111 so 100000 & 011111 : 0. and the table is supposed to match the exponent with the power. I'm guessing that how it works I couldn't find an example that didn't use strings for keys.

[TrustyTony]

Python has sets use those or there is module https://pypi.python.org/pypi/bitarray/

I will look your code later in home, if somebody does not review it before that.

[dancks]

I tried this test code but I can't get it to work:

    def getnumber(str):
        num=0
        for i in str:
            zz = ord(i)-48
            if zz<0 or zz>9:
                num=-1
                break
            else:
                num=(num*10)+zz
        return num

    def testexp2(p):
        table = {1:1,2:2,4:3,8:4,16:5,32:6,64:7,128:8,256:9}
        if p & ~(p & (p - 1)):
            print "yes"
        else:
            print "no"


    in = 1
    while in is not -1:
        in = raw_input("> ")
        in = getnumber(in)
        if in>-1:
            testexp2(in)
        else:
            print "\nDone\n\n"

the problem is in line 20.

[TrustyTony]

in is python command checking if value is in some sequence. You are trying to use it as variable.

OK, try to do bit more effort next time, here is some code:

def testexp2(p):
    return not (p & (p - 1))

b = 1
while b is not -1:
    b = int(raw_input("> "))
    if b <= -1: break
    print b, testexp2(b)

print """
Done

"""