Source code for low level binary functions

some bit wizardry from FXT

Note that there is a bit wizardry chapter in the fxtbook

Everything here is taken from the FXT library (see the fxtpage). You'll find the files in the directory src/bits/.

Define BITS_PER_LONG:

Many of the files #include
bitsperlong.h which #defines BITS_PER_LONG according to sizeof(long).
The type 'unsigned long' is abbreviated 'ulong' throughout, this is done in fxttypes.h via
typedef unsigned long ulong;

Inline assembler (for i386 and AMD64):


bitasm.h: conditionally include inline asm versions of various functions.
bitasm-i386.h: i386 inline asm.
bitasm-amd64.h: AMD64 inline asm.

Combinatorial routines:


bitsubset.h: generate all bit-subsets of a word.
bitsubset-gray.h: all bit-subsets of a word, Gray code order.
bitlex.h: generate all bit sets in (subset-)lex order.
bit-sl-gray.h: Gray code corresponding to subset-lex order (SL-Gray order).
bin-to-sl-gray.h: conversion from binary to SL-Gray order.
bitcombcolex.h: generate all bit-combinations in colex order.
bitcombcolex.h: generate all bit-combinations in colex order.
bitcombminchange.h: generate all bit-combinations in minimal-change order (Gray code).
fibrep-subset-lexrev.h: Fibonacci representations in subset-lex order.
bitfibgray: Gray code for the Fibonacci words.
bit-rll2.h: run length limited (RLL) words and Gray code for the Fibonacci words.
parenwords.h: determine whether binary word corresponds to a well-formed parenthesizing.
bit-necklace.h: generate all binary necklaces.
bitcombshifts.h: generate all combinations in shifts order.
thue-morse.h: Thue-Morse sequence.
grsnegative.h: whether Golay-Rudin-Shapiro sequence negative at an index.

Arithmetic and representation in non-standard bases:


average.h: average of two integers avoiding overflow.
evenodd.h: next_even(), next_odd() etc.
negbin.h: conversion from and to radix -2.
radix-m4.h: conversion from and to radix -4.
radix-2i.h: conversion from and to the complex radix (2*i).
radix-m1pi.h: conversion from and to the complex radix (-1+i).
bin2naf.h: non-adjacent form: sparse signed binary representation.
fibrep.h: Fibonacci representations.
bitsequency.h: generate all words with given number of edges.
bit2adic.h: 2-adic inverse and square root.

Space-filling curves:


hilbert.h: 1dim coord. to 2dim Hilbert coord.
zorder.h: 1dim coord. to 2dim/3dim space filling curve, Z-order.
bit-paper-fold.h: paper-folding sequence, also turns of the dragon curve.
bit-dragon3.h: turns of the terdragon curve.
bit-dragon-r4.h: turns of the R4-dragon curve.
bit-dragon-r5.h: turns of the R5-dragon curve.
bit-dragon-r7.h: turns of the R7-dragon curve.
bit-dragon-r9.h: turns of the R9-dragon curve.
bit-dragon-r13.h: turns of the R13-dragon curve.

Functions about cyclic rotations, necklaces, and Lyndon words:


bitrotate.h: rotating words.
bit-necklace.h: generate all binary necklaces.
bitcyclic-minmax.h: min and max among bitwise rotations.
bitcyclic-period.h: periodicity of bitwise rotations.
bitcyclic-dist.h: distance among bitwise rotations.
bitcyclic-match.h: matching bitwise rotations.
bitcyclic-xor.h: rotate-xor operation and its inverse.
bitperiodic.h: creating a periodic word.

Gray code, parity, and invertible transformations:


graycode.h: graycode and its inverse.
parity.h: parity.
revgraycode.h: reversed Gray code and its inverse.
graypower.h: Gray code powered.
bittransforms.h: invertible transforms of binary words: blue-, yellow-, cyan-, and red code.
blue-fixed-points.h: fixed points fo the blue code.
bitxtransforms.h: invertible transforms Kronecker-powered.

Cyclic Redundancy Check (CRC):


crc64.h: 64 bit CRC .
crc32.h: 32 bit CRC.
tcrc64.h: CRC with lookup table, 64 bit.
pcrc64.h: parallel CRC, 64 bit.

Mixing colors (8-bit RGB channels):


colormix.h: functions that add/average/multiply/mix color channels.
colormixp.h: versions of some of the above funcs that are correct to the last bit.
colormix-fl.h: color manipulation with floating point scaling.

Permutations of bits:


bitzip.h: even/odd bits to/from low/high bits.
bitzip-pairs.h: even/odd bits to/from low/high bits.
bitbutterfly.h: auxiliary routine for bit-zip.
bitswap.h: swapping groups of bits.
revbin.h: reversing the order of bits in a word.
revbin-upd.h: counting in bit-reversed order.
bitgather.h: bit gather/scatter.
bitseparate.h: separate bits according to a mask.

Oldenburger-Kolakoski sequence:


kolakoski-seq.h

Isolation of low or high bits and blocks:


bitlow.h: functions that isolate/find the lowest set bit.
bitlow-edge.h: create 10 or 01 edge at the lowest set bit.
bithigh.h: functions that isolate/find the highest set bit.
bithigh-edge.h: create 10 or 01 edge at the highest set bit.
bit-isolate.h: isolation of bits/blocks at low and high end, and at 0/1 and 1/0 transitions.
bit2pow.h: functions like floor(log2()).
bitldeq.h: comparing base-2 logarithms of two words.

All the rest (low level functions):


bitcount.h: population count: counting the bits in a word.
bitblock.h: generating a bit block.
bitsubsetq.h: return whether a word is a bit-subset of another word.
ith-one-idx.h: index of the i-th set bit in a word.
bittest.h: testing and changing bits of a word.
bitcopy.h: copying bits of a word.
branchless.h: code that avoids branches.
zerobyte.h: finding zero bytes in a word.
tinyfactors.h: determining whether d divides x for d,x<BITS_PER_LONG.
cswap.h: conditional swap.


A generated index of all headers.

Your feedback is appreciated.
jj (Jörg Arndt)

Last modified 2018-May-31 (17:57)
Goto jj's ugly Homepage