CodePlexProject Hosting for Open Source Software

C# implementation of most of the bit operations from Volume 4A of "The Art of Computer Programming" by Donald Knuth.

I've implemented most of the bitwise operations from Knuth's "Art of Computer Programming: Combinatorial Algorithms - Volume 4A". Algorithms included are:

All the simple manipulations on p. 140

Counting trailing zeros using the cute de Bruign trick (Knuth's ruler/rho function)

Leftmost one index (i.e., floor(lg(n)) ) using binary reduction

Bit swapping

Reversal

Bit counting or, as Knuth calls it, sideways addition

Fast general bit extraction attributed to Guy Steele on p. 148 (I called it scrunching)

General bit permuter (network solution as given on pp. 145-147)

Fragmented field operations mentioned on p. 150

Subcube vertex ops mentioned on the same page

Bytewise operations in a long as discussed on pp. 151-153

About the only thing left out is the short section on BroadWords because I don't really think they apply even to BigIntegers. The applications are interesting but not generally useful and omitted.

There are full tests for everything and those and the comments will have to serve as documentation for the moment (along with Knuth's book - probably the most important source of info).

Most are implemented for ulongs, ints, shorts and bytes and, where reasonable, for BigIntegers.

Last edited Sep 28, 2012 at 9:28 AM by darrellp, version 3