bitwise not - not what I expected

[Tim Peters]

[Elaine Jackson]
> In case any fellow newbies have been following this thread, here is
> the finished Nim script. It doesn't use bit-manipulation as much as I
> thought it would. (Still, I got the basics straight. Thanks again to
> everyone who helped out!) For a readable account of the optimal
> strategy for Nim, see Hardy & Wright's "Introduction to the Theory of
> Numbers". Peace.
>
> ## NIM
> from random import random
> piles=[0,0,0]
>
> ...
>
> def yourMove():
>     magicNum=piles[0]^piles[1]^piles[2]
>     if magicNum==0:
>         i=indexOfMax()
>         piles[i]=piles[i]-1
>     else:
>         magicIndex=leftmostBitIndex(magicNum)
>         targetIndex=(-1)
>         for i in range(3):
>             if (piles[i]>>magicIndex)%2==1:
>                 targetNum=piles[i]
>                 targetIndex=i
>                 break
>         replacement=0
>         for i in range(magicIndex):
>             magicDigit=(magicNum>>i)%2
>             targetDigit=(piles[targetIndex]>>i)%2
>             if magicDigit==1:
>                 replacementDigit=(magicDigit-targetDigit)
>             else:
>                 replacementDigit=targetDigit
>             replacement=replacement+replacementDigit*pow(2,i)
>         newNum=targetNum-(targetNum%pow(2,magicIndex+1))+replacement
>         piles[targetIndex]=newNum
>         print piles

OK, what you're trying to do is force the xor of the pile counts to 0.
There may be more than one way to do that.  For example, if piles is

    [2, 6, 7]

you can force a win by doing any of these:

    remove 1 from the 2 pile, leaving [1, 6, 7]
    remove 1 from the 6 pile, leaving [2, 5, 7]
    remove 3 from the 7 pile, leaving [2, 6, 4]

because 1^6^7 == 2^5^7 == 2^6^4 == 0.  Now the educational <wink> thing is
that it's possible to find all these solutions easily *without* picking
apart any bits:

def myMove(piles):
    all = 0
    for count in piles:
        all ^= count
    for i, count in enumerate(piles): # enumerate() new in 2.3
        all_without_count = all ^ count
        if all_without_count < count:
            print "leave %d in pile #%d" % (all_without_count, i)

For example,

>>> myMove([2, 6, 7])
leave 1 in pile #0
leave 5 in pile #1
leave 4 in pile #2
>>>

Note that the function works for any number of piles, and doesn't care how
big each pile may be; for example,

>>> myMove([2**50, 3**67, 5**12, 76**30])
leave 92709463147897838211662074651978 in pile #3
>>> 2**50 ^ 3**67 ^ 5**12 ^ 92709463147897838211662074651978
0L
>>>

I think you'll enjoy figuring out why that function works; proving that it
finds all solutions is a bit delicate, but not truly hard.