This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home. For a version of this page that may be more recent, see BitwiseCowan in WG2's repo for R7RS-large.

Bitwise­Cowan

cowan
2016-09-14 19:57:14
15history
source

Bitwise arithmetic procedures

Abstract

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 worthwhile replacing the core ops 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 33 was never finalized, but is a reasonably comprehensive proposal. A few procedures have been added from SRFI 60 and the general vector SRFI 133. SRFI 60 (based on SLIB) is smaller but has a few procedures of its own; some of its procedures have both native (often CL) and SRFI 33 names. R6RS is a subset of SRFI 60, except that all procedure names begin with a bitwise- prefix.

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 persistant 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.

Procedure index

bitwise-not bitwise-and bitwise-ior bitwise-xor bitwise-eqv bitwise-nand bitwise-nor bitwise-andc1 bitwise-andc2 bitwise-orc1 bitwise-orc2 arithmetic-shift bit-count integer-length bitwise-if bit-set? copy-bit bit-swap any-bit-set? every-bit-set? first-set-bit bit-field bit-field-any? bit-field-every? bit-field-clear bit-field-set bit-field-replace bit-field-replace-same bit-field-rotate bit-field-reverse bit-field-append integer->list list->integer bits bitwise-fold bitwise-for-each bitwise-unfold

Rationale

General design principles

Common Lisp

The core of this design design mirrors the structure of Common Lisp's pretty closely. Here are some differences:

SRFI 33

This SRFI contains all the procedures of SRFI 33, and retains their original names with these exceptions:

SRFI 60

SRFI 60 includes six procedures that do not have SRFI 33 equivalents. They are incorporated into this SRFI as follows:

Other sources

bitwise-fold, bitwise-for-each, bitwise-unfold.

Argument ordering and semantics

Specification

In the following procedure specifications all parameters and return values are exact integers unless otherwise indicated (except that procedures with names ending in ? are predicates, as usual). It is an error to pass values of other types as arguments to these functions.

Bitstrings are represented by exact integers, using a two's-complement encoding of the bitstring. Thus every integer represents a semi-infinite bitstring, having either a finite number of zeros (negative integers) or a finite number of ones (non-negative integers). The bits of a bitstring are numbered from the rightmost/least-significant bit: bit !#0 is the rightmost or 20 bit, bit !#1 is the next or 21 bit, and so forth.

Basic operations

(bitwise-not i)

Returns the bitwise complement of i; that is, all 1 bits are changed to 0 bits and all 0 bits to 1 bits.

(bitwise-not 10) => -11 (bitwise-not -37) => 36

The following ten procedures correspond to the useful set of non-trivial two-argument boolean functions. For each such function, the corresponding bitwise operator maps that function across a pair of bitstrings in a bit-wise fashion. The core idea of this group of functions is this bitwise "lifting" of the set of dyadic boolean functions to bitstring parameters.

(bitwise-and i ...)
(bitwise-ior i ...)
(bitwise-xor i ...)
(bitwise-eqv i ...)

These operations are associative. When passed no arguments, the procedures return the identity values -1, 0, 0, and -1 respectively.

The bitwise-eqv procedure produces the complement of the bitwise-xor procedure. When applied to three arguments, it does not produce a 1 bit everywhere that a, b and c all agree. That is, it does not produce

(bitwise-ior (bitwise-and a b c) (bitwise-and (bitwise-not a) (bitwise-not b) (bitwise-not c)))

Rather, it produces (bitwise-eqv a (bitwise-eqv b c)) or the equivalent (bitwise-eqv (bitwise-eqv a b) c).

(bitwise-ior 3 10) => 11 (bitwise-and 11 26) => 10 (bitwise-xor 3 10) => 9 (bitwise-eqv 37 12) => -42 (bitwise-and 37 12) => 4

(bitwise-nand i j)
(bitwise-nor i j)
(bitwise-andc1 i j)
(bitwise-andc2 i j)
(bitwise-orc1 i j)
(bitwise-orc2 i j)

These operations are not associative.

(bitwise-nand 11 26) => -11 (bitwise-nor 11 26) => -28 (bitwise-andc1 11 26) => 16 (bitwise-andc2 11 26) => 1 (bitwise-orc1 11 26) => -2 (bitwise-orc2 11 26) => -17

Integer operations

(arithmetic-shift i count)

Returns the arithmetic left shift when count>0; right shift when count<0.

(arithmetic-shift 8 2) => 32 (arithmetic-shift 4 0) => 4 (arithmetic-shift 8 -1) => 4 (arithmetic-shift -100000000000000000000000000000000 -100) => -79

(bit-count i)

Returns the population count of 1's (i >= 0) or 0's (i < 0). The result is always non-negative.

(bit-count 0) => 0 (bit-count -1) => 0 (bit-count 7) => 3 (bit-count 13) => 3 ;Two's-complement binary: ...0001101 (bit-count -13) => 2 ;Two's-complement binary: ...1110011 (bit-count 30) => 4 ;Two's-complement binary: ...0011110 (bit-count -30) => 4 ;Two's-complement binary: ...1100010 (bit-count (expt 2 100)) => 1 (bit-count (- (expt 2 100))) => 100 (bit-count (- (1+ (expt 2 100)))) => 1

(integer-length i)

The number of bits needed to represent i, i.e.

(ceiling (/ (log (if (negative? integer) (- integer) (+ 1 integer))) (log 2)))

The result is always non-negative. For non-negative i, this is the number of bits needed to represent i in an unsigned binary representation. For all i, (+ 1 (integer-length i)) is the number of bits needed to represent i in a signed twos-complement representation.

(integer-length 0) => 0 (integer-length 1) => 1 (integer-length -1) => 0 (integer-length 7) => 3 (integer-length -7) => 3 (integer-length 8) => 4 (integer-length -8) => 3

(bitwise-if mask i j)

Merge the bitstrings i and j, with bitstring mask determining from which string to take each bit. That is, if the kth bit of mask is 0, then the kth bit of the result is the kth bit of i, otherwise the kth bit of j. This is equivalent to:

(bitwise-ior (bitwise-and (bitwise-not mask) i) (bitwise-and mask j))

Single-bit operations

(bit-set? index i)

Is bit index set in bitstring i (where index is a non-negative exact integer)? As always, the rightmost/least-significant bit in i is bit 0.

(bit-set? 1 1) => false (bit-set? 0 1) => true (bit-set? 3 10) => true (bit-set? 1000000 -1) => true (bit-set? 2 6) => true (bit-set? 0 6) => false

(copy-bit index i boolean)

Returns an integer the same as i except in the indexth bit, which is 1 if boolean is #t and 0 if boolean is #f.

(copy-bit 0 0 #t) => #b1 (copy-bit 2 0 #t) => #b100 (copy-bit 2 #b1111 #f) => #b1011

(bit-swap index1 index2 i)

Returns an integer the same as i except that the index1th bit and the index2th bit have been exchanged.

(bit-swap 0 2 4) => #b1

(any-bit-set? test-bits i)
(every-bit-set? test-bits i)

Determines if any/all of the bits set in bitstring test-bits are set in bitstring i. I.e., returns (not (zero? (bitwise-and test-bits i))) or (= test-bits (bitwise-and ''test-bits i''))) respectively.

(first-set-bit i)

Return the index of the first (smallest index) 1 bit in bitstring i. Return -1 if i contains no 1 bits (i.e., if i is zero).

(first-set-bit 1) => 0 (first-set-bit 2) => 1 (first-set-bit 0) => -1 (first-set-bit 40) => 3 (first-set-bit -28) => 2 (first-set-bit (expt 2 99)) => 99 (first-set-bit (expt -2 99)) => 99

Bit field operations

These functions operate on a contiguous field of bits (a "byte," in Common-Lisp parlance) in a given bitstring. The start and end arguments, which are not optional, are non-negative exact integers specifying the field: it is the end-start bits running from bit start to bit end-1.

(bit-field i start end)

Returns the field from i, shifted down to the least-significant position in the result.

(bit-field-any? i start end)

Returns true if any of the field's bits are set in bitstring i, and false otherwise.

(bit-field-every? i start end)

Returns false if any of the field's bits are not set in bitstring i, and true otherwise.

(bit-field-clear i start end)
(bit-field-set i start end)

Returns i with the field's bits set to all 0s/1s.

(bit-field-replace dst src start end)

Returns dst with the field replaced by the least-significant end-start bits in src.

(bit-field-replace-same dst src start end)

Returns dst with its field replaced by the corresponding field in src.

(bit-field-rotate i count start end)

Returns i with the field cyclically permuted by count bits towards high-order.

(bit-field-reverse i start end)

Returns i with the order of the bits in the field reversed.

(bit-field-append i start end ...)

It is an error if the number of arguments is not a multiple of three. The field specified by each triple of i start end arguments is extracted, and the fields are concatenated in left-to-right order and returned as an integer.

Bits as booleans

(integer->list i [ len ])
(integer->vector i [ len ])

Returns a list/vector of len booleans corresponding to each bit of the non-negative integer i. #t is returned for each 1; #f for 0. The len argument defaults to (integer-length i).

(list->integer list)
(list->integer list)

Returns an integer formed from the booleans in list/vector; it is an error if list/vector contains non-booleans. A 1 bit is coded for each #t; a 0 bit for #f. Note that the result is never a negative integer. integer->list and list->integer are inverses in the sense of equal?, and so are integer->vector and vector->integer.

(bits bool ...)

Returns the integer coded by the bool arguments.

Fold, unfold, and generate

It is an error if the arguments named proc, stop?, mapper, successor are not procedures. The arguments named seed may be any Scheme object.

(bitwise-fold proc seed i)

For each bit b of i from bit 0 to (integer-length i), proc is called as (proc b r), where r is the current accumulated result. The initial value of r is seed, and the value returned by proc becomes the next accumulated result. When all bits are exhausted, the final accumulated result becomes the result of bitwise-fold.

(bitwise-for-each proc i)

Repeatedly applies proc to the bits of i starting with 0 and ending with (integer-length i). The values returned by proc are discarded. Returns an unspecified value.

(bitwise-unfold stop? mapper successor seed)

Generates a non-negative integer bit by bit, starting with bit 0. If the result of applying stop? to the current state (whose initial value is seed) is true, return the currently accumulated bits as an integer. Otherwise, apply mapper to the current state to obtain the next bit of the result by interpreting a true value as a 1 bit and a false value as a 0 bit. Then get a new state by applying successor to the current state, and repeat this algorithm.

(make-bitwise-generator i)

Returns a SRFI 121 generator that generates all the bits of i starting with bit 0. Note that it is an infinite generator.

Comparison of proposals

The following table compares the names of the bitwise (aka logical) functions of Common Lisp, SRFI 33, Olin's revisions, SRFI 60, R6RS, and this SRFI.

Function

CL

SRFI 33

SRFI 33 late revs

SRFI 60

R6RS

This SRFI

Bitwise NOT

lognot

bitwise-not

bitwise-not

lognot, bitwise-not

bitwise-not

bitwise-not

Bitwise AND

logand

bitwise-and

bitwise-and

logand, bitwise-and

bitwise-and

bitwise-and

Bitwise IOR

logior

bitwise-ior

bitwise-ior

logior, bitwise-ior

bitwise-ior

bitwise-ior

Bitwise XOR

logxor

bitwise-xor

bitwise-xor

logxor, bitwise-xor

bitwise-xor

bitwise-xor

Bitwise EQV

logeqv

bitwise-eqv

bitwise-eqv

---

---

bitwise-eqv

Bitwise NAND

lognand

bitwise-nand

bitwise-nand

---

---

bitwise-nand

Bitwise NOR

lognor

bitwise-nor

bitwise-nor

---

---

bitwise-nor

Bitwise AND with NOT of first arg

logandc1

bitwise-andc1

bitwise-andc1

---

---

bitwise-andc1

Bitwise AND with NOT of second arg

logandc2

bitwise-andc2

bitwise-andc2

---

---

bitwise-andc2

Bitwise OR with NOT of first arg

logorc1

bitwise-orc1

bitwise-orc1

---

---

bitwise-orc1

Bitwise OR with NOT of second arg

logorc2

bitwise-orc2

bitwise-orc2

---

---

bitwise-orc2

Arithmetic shift

ash

arithmetic-shift

arithmetic-shift

ash, arithmetic-shift

bitwise-arithmetic-shift

arithmetic-shift

Population count

logcount

bit-count

bit-count

logcount, bit-count

bitwise-bit-count

bit-count

Integer length

integer-length

integer-length

integer-length

integer-length

bitwise-integer-length

integer-length

Mask selects source of bits

---

bitwise-merge

bitwise-merge

bitwise-if, bitwise-merge

bitwise-if

bitwise-if

Test single bit

logbitp

bit-set?

bit-set?

logbit?, bit-set?

bitwise-bit-set?

bit-set?

See if any mask bits set

logtest

any-bits-set?

any-bit-set?

logtest, any-bit-set?

---

any-bit-set

See if all mask bits set

---

all-bits-set?

every-bit-set?

---

---

every-bit-set?

Replace single bit

---

---

copy-bit

bitwise-copy-bit

---

copy-bit

Swap bits

---

---

---

---

---

bit-swap

Find first bit set

---

first-bit-set

first-set-bit

log2-binary-factors, first-set-bit

---

first-set-bit

Extract bit field

ldb

extract-bit-field

extract-bit-field

bit-field

bitwise-bit-field

bit-field

Test bit field (any)

ldb-test

test-bit-field?

bit-field-any?

---

---

bit-field-any?

Test bit field (every)

---

---

bit-field-every?

---

---

bit-field-every?

Clear bit field

mask-field

clear-bit-field

bit-field-clear

---

---

bit-field-clear

Set bit field

---

---

---

---

---

bit-field-set

Replace bit field

dpb

replace-bit-field

bit-field-replace

copy-bit-field

bitwise-copy-bit-field

bit-field-replace

Replace corresponding bit field

deposit-field

deposit-field

copy-bit-field

---

---

bit-field-copy-same

Rotate bit field

---

---

---

rotate-bit-field

bitwise-rotate-bit-field

bit-field-rotate

Reverse bit field

---

---

---

reverse-bit-field

bitwise-reverse-bit-field

bit-field-reverse

Append bit fields

---

---

---

---

---

bit-field-append

Integer to boolean list

---

---

---

integer->list

---

integer->list

Integer to boolean vector

---

---

---

---

---

integer->vector

Boolean list to integer

---

---

---

list->integer

---

list->integer

Boolean vector to integer

---

---

---

---

---

vector->integer

Booleans to integer

---

---

---

booleans->integer

---

bits

Bitwise fold

---

---

---

---

---

bitwise-fold

Bitwise for-each

---

---

---

---

---

bitwise-for-each

Bitwise unfold

---

---

---

---

---

bitwise-unfold