The fxt demos: bit wizardry

Directory bits: Bit fiddling routines.
Find a list of all files in this directory here. An index of all topics is here

You may want to look at the outputs first.

all-dbs-out.txt is the output of all-dbs-demo.cc.
Find all De Bruijn sequences (DBS) of given length 2^n (3<=n<=5). Exhaustive search.
The demo uses the functions from bitcombcolex.h (fxt/src/bits/bitcombcolex.h) bitrotate.h (fxt/src/bits/bitrotate.h)

bin-to-sl-gray-out.txt is the output of bin-to-sl-gray-demo.cc.
Converting binary numbers to corresponding words in SL-Gray order. Cf. OEIS sequence A217262.
The demo uses the functions from bin-to-sl-gray.h (fxt/src/bits/bin-to-sl-gray.h)

bin2naf-out.txt is the output of bin2naf-demo.cc.
Sparse signed binary representation (nonadjacent form, NAF).
The demo uses the functions from bin2naf.h (fxt/src/bits/bin2naf.h) print-bin.h (fxt/src/bits/print-bin.h) print-bindiff.cc (fxt/src/bits/print-bindiff.cc)

bin2sbin-out.txt is the output of bin2sbin-demo.cc.
Signed binary representation (not a nonadjacent form in general).
The demo uses the functions from bin2naf.h (fxt/src/bits/bin2naf.h) print-bin.h (fxt/src/bits/print-bin.h) print-bindiff.cc (fxt/src/bits/print-bindiff.cc)

bit-necklace-out.txt is the output of bit-necklace-demo.cc.
Binary necklaces and Lyndon words: CAT generation.
The demo uses the functions from bit-necklace.h (fxt/src/bits/bit-necklace.h)

bit-nextgray-out.txt is the output of bit-nextgray-demo.cc.
Gray increment/counter.
The demo uses the functions from nextgray.h (fxt/src/bits/nextgray.h) graycode.h (fxt/src/bits/graycode.h)

bit-paper-fold-alt-out.txt is the output of bit-paper-fold-alt-demo.cc.
Generate the alternate paper-folding sequence.
The demo uses the functions from bit-paper-fold.h (fxt/src/bits/bit-paper-fold.h)

bit-paper-fold-out.txt is the output of bit-paper-fold-demo.cc.
Generate the paper-folding sequence. Cf. OEIS sequences A014577, A014707, A091072, and A091067.
The demo uses the functions from bit-paper-fold.h (fxt/src/bits/bit-paper-fold.h)

bit-paper-fold-general-out.txt is the output of bit-paper-fold-general-demo.cc.
Generate (a general) paper-folding sequence.
The demo uses the functions from bit-paper-fold.h (fxt/src/bits/bit-paper-fold.h)

bit-rll2-out.txt is the output of bit-rll2-demo.cc.
Run length limited (RLL) words and Fibonacci Gray code.
The demo uses the functions from bit-rll2.h (fxt/src/bits/bit-rll2.h)

bit-sl-gray-out.txt is the output of bit-sl-gray-demo.cc.
Binary words in SL-Gray order, the minimal-change order corresponding to subset-lex order. Cf. OEIS sequence A217262.
The demo uses the functions from bit-sl-gray.h (fxt/src/bits/bit-sl-gray.h)

bit2adic-out.txt is the output of bit2adic-demo.cc.
2-adic inverse and square root.
The demo uses the functions from bit2adic.h (fxt/src/bits/bit2adic.h)

bitcombcolex-out.txt is the output of bitcombcolex-demo.cc.
Generating combinations of bits (as binary words) in co-lexicographic order.
The demo uses the functions from bitcombcolex.h (fxt/src/bits/bitcombcolex.h)

bitcomblex-out.txt is the output of bitcomblex-demo.cc.
Generating combinations of bits (as binary words) in lexicographic order.
The demo uses the functions from bitcombcolex.h (fxt/src/bits/bitcombcolex.h) revbin.h (fxt/src/bits/revbin.h)

bitcombminchange-out.txt is the output of bitcombminchange-demo.cc.
Generating all combinations of bits (as binary words) in minimal-change order.
The demo uses the functions from bitcombminchange.h (fxt/src/bits/bitcombminchange.h)

bitcombshifts-out.txt is the output of bitcombshifts-demo.cc.
bit-combinations in shifts order.
The demo uses the functions from bitcombshifts.h (fxt/src/bits/bitcombshifts.h)

bitcount-v-out.txt is the output of bitcount-v-demo.cc.
bit-count many words via vertical addition
The demo uses the functions from bitcount.h (fxt/src/bits/bitcount.h) bitcount-v.cc (fxt/src/bits/bitcount-v.cc)

bitfibgray-out.txt is the output of bitfibgray-demo.cc.
Fibonacci Gray code with binary words.
The demo uses the functions from bitfibgray.h (fxt/src/bits/bitfibgray.h) graycode.h (fxt/src/bits/graycode.h) negbin.h (fxt/src/bits/negbin.h) fibrep.h (fxt/src/bits/fibrep.h)

bithilo-out.txt is the output of bithilo-demo.cc.
Operations on the low and high bits of binary words.
The demo uses the functions from bit2pow.h (fxt/src/bits/bit2pow.h) bitlow.h (fxt/src/bits/bitlow.h) bitlow-edge.h (fxt/src/bits/bitlow-edge.h) bithigh.h (fxt/src/bits/bithigh.h) bithigh-edge.h (fxt/src/bits/bithigh-edge.h)

bitlex-out.txt is the output of bitlex-demo.cc.
Generating binary words in subset-lexrev order.
The demo uses the functions from bitlex.h (fxt/src/bits/bitlex.h)

bitlex-rec-out.txt is the output of bitlex-rec-demo.cc.
Recursive algorithm for the binary words in subset-lex order.

bitmisc-out.txt is the output of bitmisc-demo.cc.
Miscellaneous operations on binary words.
The demo uses the functions from bitswap.h (fxt/src/bits/bitswap.h) zerobyte.h (fxt/src/bits/zerobyte.h) bit-isolate.h (fxt/src/bits/bit-isolate.h) bitcount.h (fxt/src/bits/bitcount.h)

bitmisc2-out.txt is the output of bitmisc2-demo.cc.
Miscellaneous operations on binary words.
The demo uses the functions from revbin.h (fxt/src/bits/revbin.h) bitswap.h (fxt/src/bits/bitswap.h) graycode.h (fxt/src/bits/graycode.h) revgraycode.h (fxt/src/bits/revgraycode.h) bitsequency.h (fxt/src/bits/bitsequency.h) bitrotate.h (fxt/src/bits/bitrotate.h) bitcyclic-minmax.h (fxt/src/bits/bitcyclic-minmax.h)

bitperm1-out.txt is the output of bitperm1-demo.cc.
Certain permutations controlled by a binary word.

bitsequency-out.txt is the output of bitsequency-demo.cc.
Generating bit sets of given sequency.
The demo uses the functions from bitsequency.h (fxt/src/bits/bitsequency.h)

bitsubset-out.txt is the output of bitsubset-demo.cc.
Generating all subsets of a bitset.
The demo uses the functions from bitsubset.h (fxt/src/bits/bitsubset.h)

bitsubset-gray-out.txt is the output of bitsubset-gray-demo.cc.
Generating all subsets of a bitset in Gray code order.
The demo uses the functions from bitsubset-gray.h (fxt/src/bits/bitsubset-gray.h) bitsubset.h (fxt/src/bits/bitsubset.h)

bitsubset-shift-out.txt is the output of bitsubset-shift-demo.cc.
Shifting through a bitset.
The demo uses the functions from bitsubset.h (fxt/src/bits/bitsubset.h)

bittransforms-blue-out.txt is the output of bittransforms-blue-demo.cc.
Transforms of binary words that are involutions: blue code and yellow code.
The demo uses the functions from bittransforms.h (fxt/src/bits/bittransforms.h)

bittransforms-blue-fp-out.txt is the output of bittransforms-blue-fp-demo.cc.
Fixed points of the blue code.
The demo uses the functions from blue-fixed-points.h (fxt/src/bits/blue-fixed-points.h) bittransforms.h (fxt/src/bits/bittransforms.h)

bittransforms-red-out.txt is the output of bittransforms-red-demo.cc.
Transforms of binary words that are involutions: red code and green code.
The demo uses the functions from bittransforms.h (fxt/src/bits/bittransforms.h)

bitxtransforms-out.txt is the output of bitxtransforms-demo.cc.
Matrices corresponding to symbolic powers of the 'color' transforms.

crc64-out.txt is the output of crc64-demo.cc.
Cyclic Redundancy Check (CRC) with 64 bits.
The demo uses the functions from crc64.h (fxt/src/bits/crc64.h) crc64.cc (fxt/src/bits/crc64.cc) poly-tab.h (fxt/src/bpol/poly-tab.h)

debruijn-lookup-out.txt is the output of debruijn-lookup-demo.cc.
Determination of the lowest bit in a word via De Bruijn sequences.

dragon-curve-moves-out.txt is the output of dragon-curve-moves-demo.cc.
Moves of the dragon curve: +==right, -==left, ^==up, v==down
The demo uses the functions from bit-paper-fold.h (fxt/src/bits/bit-paper-fold.h)

fibrep-out.txt is the output of fibrep-demo.cc.
Fibonacci representations: successive generation in lexicographic order. Cf. OEIS sequence A003714.
The demo uses the functions from fibrep.h (fxt/src/bits/fibrep.h)

fibrep-subset-lexrev-out.txt is the output of fibrep-subset-lexrev-demo.cc.
Generating Fibonacci words in subset-lexrev order.
The demo uses the functions from fibrep-subset-lexrev.h (fxt/src/bits/fibrep-subset-lexrev.h)

gotcha-out.txt is the output of gotcha-demo.cc.
A pitfall with two's complement: one nonzero value equals its own negative.

gray-out.txt is the output of gray-demo.cc.
Binary Gray code.
The demo uses the functions from graycode.h (fxt/src/bits/graycode.h) parity.h (fxt/src/bits/parity.h) print-bin.h (fxt/src/bits/print-bin.h)

gray-rec-out.txt is the output of gray-rec-demo.cc.
Recursive algorithm for the binary Gray code.

graycode-out.txt is the output of graycode-demo.cc.
Demo of the binary Gray code.
The demo uses the functions from graycode.h (fxt/src/bits/graycode.h) parity.h (fxt/src/bits/parity.h)

grs-out.txt is the output of grs-demo.cc.
The Golay-Rudin-Shapiro (GRS) sequence.
The demo uses the functions from grsnegative.h (fxt/src/bits/grsnegative.h) parity.h (fxt/src/bits/parity.h)

grs-next-out.txt is the output of grs-next-demo.cc.
Generate the Golay-Rudin-Shapiro (GRS) sequence.
The demo uses the functions from grsnegative.h (fxt/src/bits/grsnegative.h) bitlow.h (fxt/src/bits/bitlow.h)

hanoi-out.txt is the output of hanoi-demo.cc.
Towers of Hanoi and the period-doubling sequence.

hilbert-out.txt is the output of hilbert-demo.cc.
Hilbert curve and Gray code.
The demo uses the functions from hilbert.h (fxt/src/bits/hilbert.h) lin2hilbert.cc (fxt/src/bits/lin2hilbert.cc) graycode.h (fxt/src/bits/graycode.h) bitzip.h (fxt/src/bits/bitzip.h)

hilbert-gray-out.txt is the output of hilbert-gray-demo.cc.
Gray code from Hilbert curve
The demo uses the functions from hilbert.h (fxt/src/bits/hilbert.h) lin2hilbert.cc (fxt/src/bits/lin2hilbert.cc)

hilbert-moves-out.txt is the output of hilbert-moves-demo.cc.
Moves and turns of the Hilbert curve.
The demo uses the functions from hilbert.h (fxt/src/bits/hilbert.h)

kolakoski-seq-out.txt is the output of kolakoski-seq-demo.cc.
Oldenburger-Kolakoski sequence. See OEIS sequence A000002. Cf. https://en.wikipedia.org/wiki/Kolakoski_sequence Algorithm by David Eppstein, see https://11011110.github.io/blog/2016/10/14/kolakoski-sequence-via.html
The demo uses the functions from kolakoski-seq.h (fxt/src/bits/kolakoski-seq.h)

modular-lookup-out.txt is the output of modular-lookup-demo.cc.
Determination of the lowest bit in a word via modular arithmetic.

negbin-out.txt is the output of negbin-demo.cc.
Representation in radix(-2).
The demo uses the functions from negbin.h (fxt/src/bits/negbin.h) graycode.h (fxt/src/bits/graycode.h)

negbin2-out.txt is the output of negbin2-demo.cc.
radix(-2) representations: successive generation.
The demo uses the functions from negbin.h (fxt/src/bits/negbin.h)

parenword-colex-out.txt is the output of parenword-colex-demo.cc.
Binary 'parentheses words' in colex order.
The demo uses the functions from parenwords.h (fxt/src/bits/parenwords.h) print-bin.h (fxt/src/bits/print-bin.h)

parenword-out.txt is the output of parenword-demo.cc.
Binary words that are "parentheses words". Cf. OEIS sequence A036991.
The demo uses the functions from parenwords.h (fxt/src/bits/parenwords.h)

pcrc64-out.txt is the output of pcrc64-demo.cc.
Parallel Cyclic Redundancy Check (CRC)
The demo uses the functions from pcrc64.h (fxt/src/bits/pcrc64.h)

radix-2i-out.txt is the output of radix-2i-demo.cc.
Representation of purely real and imaginary numbers in radix(2*i). The radix(2*i) representation for complex integers needs one digit (i.e., two bits) after the point.
The demo uses the functions from radix-2i.h (fxt/src/bits/radix-2i.h) radix-m4.h (fxt/src/bits/radix-m4.h) bitzip-pairs.h (fxt/src/bits/bitzip-pairs.h)

radix-2i-to-z-out.txt is the output of radix-2i-to-z-demo.cc.
Convert radix (2*i) numbers to complex numbers. The radix(2*i) representation for complex integers needs one digit (i.e., two bits) after the point.
The demo uses the functions from radix-2i.h (fxt/src/bits/radix-2i.h) radix-m4.h (fxt/src/bits/radix-m4.h) bitzip-pairs.h (fxt/src/bits/bitzip-pairs.h)

radix-m1pi-out.txt is the output of radix-m1pi-demo.cc.
Representation of purely real and imaginary numbers in radix(-1+i).
The demo uses the functions from radix-m1pi.h (fxt/src/bits/radix-m1pi.h) radix-m4.h (fxt/src/bits/radix-m4.h) bitzip.h (fxt/src/bits/bitzip.h)

radix-m1pi-to-z-out.txt is the output of radix-m1pi-to-z-demo.cc.
Convert radix (-1+i) numbers to complex numbers and give radix (-1+i) expansion of real and imaginary part.
The demo uses the functions from radix-m1pi.h (fxt/src/bits/radix-m1pi.h) radix-m4.h (fxt/src/bits/radix-m4.h) bitzip.h (fxt/src/bits/bitzip.h)

radix-m4-out.txt is the output of radix-m4-demo.cc.
Representation in radix(-4).
The demo uses the functions from radix-m4.h (fxt/src/bits/radix-m4.h)

revbin-rec-out.txt is the output of revbin-rec-demo.cc.
Recursive algorithm for the bit-reversed binary words in order.

revbin-steps-out.txt is the output of revbin-steps-demo.cc.
Show steps of the revbin algorithm

revbin-tab-out.txt is the output of revbin-tab-demo.cc.
Table lookup routine for reversing the bits of a word.
The demo uses the functions from revbin.h (fxt/src/bits/revbin.h)

revbin-update-out.txt is the output of revbin-update-demo.cc.
Revbin-update routines.
The demo uses the functions from revbin-upd.h (fxt/src/bits/revbin-upd.h)

thue-morse-out.txt is the output of thue-morse-demo.cc.
Generate the Thue-Morse sequence
The demo uses the functions from thue-morse.h (fxt/src/bits/thue-morse.h)