File Bitwise.h

↰ Parent directory (ADS/combinatorial)

The broadword tricks of Knuth (7.1.3), beyond the book: operations on the 64 bits of a word as on a vector of bits, with a few instructions and no loop over the bits.

Definition (ADS/combinatorial/Bitwise.h)

Detailed Description

  • sidewaysSum() counts the 1 bits by adding them in parallel in fields of 2, 4 and 8 bits and then the bytes by one multiplication;

  • ruler() ( :math:` rho , the trailing zeros) as the sideways sum of :math: x oplus ( x - 1 ) ` minus 1, lambda() ( :math:` lambda , the place of the leading 1) by halving the width, and rightmostOne() and smearRight() by the identities :math: x & -x ` and :math:` x | ( x - 1 ) `;

  • reverseBits() swaps halves, then quarters, and so on;

  • gray() and grayInverse() convert between binary and Gray code;

  • nextSameWeight() gives the next larger word with as many 1 bits (the trick of Gosper), which enumerates the k-subsets of 64 items;

  • interleave() and deinterleave() give the Morton code of two 32-bit coordinates by the perfect shuffle of their bits, whose order keeps nearby points of the plane nearby;

  • hasZeroByte() tells in O( 1 ) whether one of the 8 bytes of a word is 0, the test that makes strlen() fast.

The contracts [see File Contract.h]: ruler() and lambda() need x != 0, and nextSameWeight() a word whose next one does not overflow. The functions are defined in Bitwise.tpp.

    1. Knuth, The Art of Computer Programming, vol. 4A, Addison-Wesley, 2011, section 7.1.3

    1. Warren, Hacker’s Delight, 2nd ed., Addison-Wesley, 2012

  1. Beeler, R. W. Gosper, R. Schroeppel, HAKMEM, MIT AI Memo 239, 1972, item 175 (the next word with as many 1 bits)

  1. Gray, Pulse code communication, U.S. Patent 2,632,058, 1953

    1. Morton, A computer oriented geodetic data base and a new technique in file sequencing, IBM report, Ottawa, 1966

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/combinatorial/impl/Bitwise.tpp

  • cstdint

  • utility

Included By

Namespaces

Functions

Typedefs