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-08-09 05:11:33
11history
source

Bitwise arithmetic procedures

This proposal is based mainly on SRFI 33, with some changes and additions from Olin's late revisions to SRFI 33 (which were never consummated) and a few procedures from SRFI 60 and the general vector SRFI 133.

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.

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

Differences from Common Lisp

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

Changes to SRFI 33 names

BitwiseCowan retains SRFI 33 names for procedures adapted from SRFI 33, 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

The following procedures are inspired by SRFI 133: bit-swap, bit-field-append, bitwise-fold, bitwise-for-each, bitwise-unfold.

Argument ordering and semantics

Specification

In the following procedure specifications all parameters are exact integers; unless otherwise indicated, all return values are exact integers. It is an error to pass values of other types as arguments to these functions.

Bitstrings are represented by 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) -> exact-integer

Bitwise logical negation.

(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 ...) -> exact-integer
(bitwise-ior i ...) -> exact-integer
(bitwise-xor i ...) -> exact-integer
(bitwise-eqv i ...) -> exact-integer

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 negation 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) -> exact-integer
(bitwise-nor i j) -> exact-integer
(bitwise-andc1 i j) -> exact-integer
(bitwise-andc2 i j) -> exact-integer
(bitwise-orc1 i j) -> exact-integer
(bitwise-orc2 i j) -> exact-integer

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) -> exact-integer

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) -> nonnegative-exact-integer

Population count of 1's (i >= 0) or 0's (i < 0).

(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) -> nonnegative-exact-integer

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

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

(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 This is equivalent to: (bitwise-ior (bitwise-and (bitwise-not mask) i) (bitwise-and mask j)) 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 returns (not (zero? (bitwise-and ''test-bits i'')))` (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 The field specified The initial value of r When The values returned by proc are discarded. Returns Otherwise, apply mapper Then get a new state Note that it is an infinite generator. SRFI 33 was never finalized, but is a comprehensive proposal. 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, but all procedure names begin with a bitwise- prefix.

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

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

Fill bit field

---

---

---

---

---

bit-field-fill

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

Boolean list to integer

---

---

---

list->integer

---

list->integer

Booleans to integer

---

---

---

booleans->integer

---

bits

||Bitwise fold||---||---||---||---||---||bitwise-fold|

Bitwise for-each

---

---

---

---

---

bitwise-for-each

Bitwise unfold

---

---

---

---

---

bitwise-unfold