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.

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.

[Generating sequences with] unequal probabilities Given a sequence a of n equally probable 0's and 1's, the following generates a single 0 or 1 with probabilities approximating {1 - p, p} to n digits: Fold[({BitAnd, BitOr} 〚 1 + First[#2] 〛 [#1, Last[#2]]) &, 0, Reverse[Transpose[{First[RealDigits[p, 2, n, -1]], a}]]] This can be generalized to allow a whole sequence to be generated with as little as an average of two input digits being used for each output digit.

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.)

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).

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] .)

[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.

Applying BitReverseOrder to this matrix yields a matrix which has an essentially nested form, and for size n = 2 s can be obtained from Nest[With[{c = BitReverseOrder[Range[0, Length[#] - 1]/ Length[#]]}, Flatten2D[MapIndexed[#1 {{1, 1}, {1, -1} (-1)^c 〚 Last[#2] 〛 } &, #, {2}]]] &, {{1}}, s] Using this structure, one obtains the so-called fast Fourier transform which operates in n Log[n] steps and is given by With[{n = Length[data]}, Fold[Flatten[Map[With[ {k = Length[#]/2}, {{1, 1}, {1, -1}} . {Take[#, k], Drop[ #, k](-1)^(Range[0, k - 1]/k)}] &, Partition[##]]] &, BitReverseOrder[data], 2^Range[Log[2, n]]]/ √ n ] (See also page 1080 .)

Numbers for example are typically represented in base 2 by sequences of 32 or more bits. Similarly, characters of text are usually represented by sequences of 8 or more bits. … Images are usually represented by bitmaps containing thousands or millions of bits, with each bit specifying for example whether a pixel at a particular location should, say, be black or white.

[Number representations in] practical computing Numbers used for arithmetic in practical computing are usually assumed to have a fixed length of, say, 32 bits, and thus do not need to be self-delimiting.