Note that BitOr[x, y] + BitAnd[x, y]  x + y and BitOr[x, y] - BitAnd[x, y]  BitXor[x, y] . The patterns below show where BitXor[x, y]  t for successive t and correspond to steps in the "munching squares" program studied on the PDP-1 computer in 1962.

The number which appears at position i is given by BitXor[i, Floor[i/2]] . (Iterating the related function BitXor[i, 2i] yields numbers whose digit sequences correspond to the rule 60 cellular automaton).

[Iterated maps from] bitwise operations Cellular automata can be thought of as analogs of iterated maps in which bitwise operations such as BitXor are used instead of ordinary arithmetic ones.

Given an integer a for which IntegerDigits[a, 2] gives the cell values for a cellular automaton, a single step of evolution according say to rule 30 is given by BitXor[a, 2 BitOr[a, 2a]] where (see page 871 ) BitXor[x, y]  BitOr[x, y] - BitAnd[x, y] and a is assumed to be padded with 0's at each end. The corresponding form for rule 110 is BitXor[BitAnd[a, 2a, 4a], BitOr[2a, 4a]] The final equation is then obtained from {1 + x 4 + x 12  2 (1 + x 3 ) (x 1 + 2 x 3 ) , x 2 + x 13  2 x 1 , 1 + x 5 + x 14  2 x 1 , 2 x 3 x 5 + 2 x 1 + 2 x 3 x 6 + 2 x 1 + x 3 x 15 + x 16  x 4 , 1 + x 15 + x 17  2 x 3 , 1 + x 16 + x 18  2 x 3 , 2 1 + x 3 (1 + x 1 + 2 x 3 ) (-1 + x 2 ) - x 10 + x 11  2 x 4 , x 7  BitAnd[x 6 , 2 x 6 ] ∧ x 8  BitOr[x 6 , 2 x 6 ], x 9  BitAnd[x 6 , 2 x 7 ] ∧ x 19  BitOr[x 6 , 2 x 7 ], x 10  BitAnd[x 9 , 2 x 8 ] ∧ x 11  BitOr[x 9 , 2 x 8 ]} where x 1 through x 4 have the meanings indicated in the main text, and satisfy x i ≥ 0 . Non-overlapping subsidiary variables are introduced for BitOr and BitAnd , yielding a total of 79 variables.

Particularly dramatic are the concatenation systems discussed on page 913 , as well as successive rows in nested patterns such as Flatten[IntegerDigits[NestList[BitXor[#, 2 #] &, 1, 500], 2]] and sequences based on numbers such as Flatten[Table[If[GCD[i, j]  0, 1, 0], {i, 1000}, {j, i}]] (see page 613 ).

But since every value must be either 0 or 1, it can in fact be encoded by just a single bit. … The main point of this is that typical machine instructions operate in parallel on all the bits in such a variable. … (It is much easier to implement in Mathematica—as discussed above—since there functions like BitXor can operate on integers of any length.)

It also turns out that BitXor[2a, b] + 1 works, though in this case even for 2 the smallest representation is (1 ∘ 1) ∘ (1 ∘ ((1 ∘ 1) ∘ 1)) . (For BitOr[2a, b] - 1 the number of applications needed is With[{i = IntegerDigits[m, 2]}, Tr[i + 1] + i 〚 2 〛 (1 + i 〚 3 〛 ) - 1] .)

The first n elements can be found efficiently using Module[{a = 1}, Table[First[IntegerDigits[ a, a = BitXor[a, BitOr[2a, 4a]]; 2, i]], {i, n}]] The sequence does not repeat in at least its first million steps, and I would amazed if it ever repeats, but as of now I know of no rigorous proof of this. ( Erica Jen showed in 1986 that no pair of columns can ever repeat, and the arguments on page 1087 suggest that neither can the center column together with occasional neighboring cells.)

With more than two piles it was discovered in 1901 that one player can in general force the other to lose by arranging that after each of their moves Apply[BitXor, h]  0 , where h is the list of heights.

Sierpiński pattern Other ways to generate step n of the pattern shown here in various orientations include: • Mod[Array[Binomial, {2, 2} n , 0], 2] (see pages 611 and 870 ) • 1 - Sign[Array[BitAnd, {2, 2} n , 0]] (see pages 608 and 871 ) • NestList[Mod[RotateLeft[#] + #, 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • NestList[Mod[ListConvolve[{1, 1}, #, -1], 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • IntegerDigits[NestList[BitXor[2#, #] &, 1, 2 n - 1], 2, 2 n ] (see page 906 ) • NestList[Mod[Rest[FoldList[Plus, 0, #]], 2] &, Table[1, {2 n }], 2 n - 1] (see page 1034 ) • Table[PadRight[ Mod[CoefficientList[(1 + x) t - 1 , x], 2], 2 n - 1], {t, 2 n }] (see pages 870 and 951 ) • Reverse[Mod[CoefficientList[Series[1/(1 - (1 + x)y), {x, 0, 2 n - 1}, {y, 0, 2 n - 1}], {x, y}], 2]] (see page 1091 ) • Nest[Apply[Join, MapThread[ Join, {{#, #}, {0 #, #}}, 2]] &, {{1}}, n] (compare page 1073 ) The positions of black squares can be found from: • Nest[Flatten[2# /.