SRFI 151: Bitwise Operations

by John Cowan

status: final (2017-07-10)

keywords: Data Structure, R7RS Large, R7RS Large: Tangerine Edition, Numbers

See also SRFI 142: Bitwise Operations.

library name: bitwise-operations


This SRFI proposes a coherent and comprehensive set of procedures for performing bitwise logical operations on integers; it is accompanied by a reference implementation of the spec in terms of a set of seven core operators. The sample implementation is portable, as efficient as practical with pure Scheme arithmetic (it is much more efficient to replace the core operators with C or assembly language if possible), and open source.

The precise semantics of these operators is almost never an issue. A consistent, portable set of names and parameter conventions, however, is. Hence this SRFI, which is based mainly on SRFI 33, with some changes and additions from Olin's late revisions to SRFI 33 (which were never consummated). SRFI 60 (based on SLIB) is smaller but has a few procedures of its own; some of its procedures have both native (often Common Lisp) and SRFI 33 names. They have been incorporated into this SRFI. R6RS is a subset of SRFI 60, except that all procedure names begin with a bitwise- prefix. A few procedures have been added from the general vector SRFI 133.

Among the applications of bitwise operations are: hashing, Galois-field calculations of error-detecting and error-correcting codes, cryptography and ciphers, pseudo-random number generation, register-transfer-level modeling of digital logic designs, Fast-Fourier transforms, packing and unpacking numbers in persistent data structures, space-filling curves with applications to dimension reduction and sparse multi-dimensional database indexes, and generating approximate seed values for root-finders and transcendental function algorithms.

This SRFI differs from SRFI 142 in only two ways:

  1. The bitwise-if function has the argument ordering of SLIB, SRFI 60, and R6RS rather than the ordering of SRFI 33.

  2. The order in which bits are processed by the procedures listed in the "Bits conversion" section has been clarified and some of the procedures' names have been changed. See "Bit processing order" for details.