The SRFI-33 integer bitwise-operation library -*- outline -*- Olin Shivers First draft: 1996/6/3 Last update: 2002/7/21 Emacs should display this document in outline mode. Say c-h m for instructions on how to move through it by sections (e.g., c-c c-n, c-c c-p). * Table of contents ------------------- Abstract Function index Function Specification Rationale & general discussion Summaries of related designs Reference implementation Topics to be resolved during discussion phase SIZE/POSITION vs. FROM/TO field specs Order of arguments for non-bitstring parameters The name "bit-set?" References & Links Copyright ------------------------------------------------------------------------------- * Abstract ---------- R5RS Scheme has no utilities for performing bitwise logical operations on integers or bitstrings, which is a problem for authors of portable code. This SRFI proposes a coherent and comprehensive set of these functions; it is accompanied by a reference implementation of the spec in terms of a set of seven core operators. The reference implementation is - portable - efficient - completely open, public-domain 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. ------------------------------------------------------------------------------- * Function 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-merge bit-set? any-bits-set? all-bits-set? first-set-bit extract-bit-field test-bit-field? clear-bit-field replace-bit-field copy-bit-field ------------------------------------------------------------------------------- * Function specifications ------------------------- In a Scheme system that has a module or package system, these functions should be contained in a module named "bitwise-lib". They may additionally be provided as part of the general suite of numerical operations. In the following function 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 zeroes (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 2^0 bit, bit #1 is the next or 2^1 bit, and so forth. bitwise-not i -> exact-integer Bitwise logical negation, i.e., -(i+1). (bitwise-not 10) => -11 (bitwise-not -37) => 36 N-ary operators, for n >= 0 Procedure Bit function ------------------ --------------------------------- bitwise-and i ... And bitwise-ior i ... Inclusive or bitwise-xor i ... Exclusive or bitwise-eqv i ... (eqv b1 b2) = (not (xor b1 b2)) bitwise-nand i ... (not (and b ...)) bitwise-nor i ... (not (or b ...)) Note that the and, ior, xor and eqv operations are associative. Exactly two arguments Procedure Bit function ----------------- ----------------- bitwise-andc1 i j (and (not bi) bj) bitwise-andc2 i j (and bi (not bj)) bitwise-orc1 i j (ior (not bi) bj) bitwise-orc2 i j (ior bi (not bj)) Trivial, hence not provided Procedure Definition ----------------- ------------------------------ bitwise-const0 i j (lambda (i j) 0) bitwise-const1 i j (lambda (i j) -1) bitwise-arg1 i j (lambda (i j) i) bitwise-arg2 i j (lambda (i j) j) bitwise-not1 i j (lambda (i j) (bitwise-not i)) bitwise-not2 i j (lambda (i j) (bitwise-not j)) - These 16 procedures correspond to the complete set of two-argument boolean functions, that is, the complete set of bit x bit -> bit functions. For each such function, the corresponding bitwise operator maps that function across a pair of bitstrings in a bit-wise fashion. I have chosen to provide the full set, barring the last, trivial group of six. The core idea of this group of functions is this bitwise "lifting" of the set of dyadic boolean functions to bitstring parameters; the variadic generalisations are made where sensible. - The n-ary functions have these base, nullary cases: (bitwise-and) => -1 (bitwise-ior) => 0 (bitwise-nand) => 0 (bitwise-nor) => -1 (bitwise-xor) => 0 (bitwise-eqv) => -1 - Note that (bitwise-eqv a b c) does *not* produce a 1 bit everywhere a, b & 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) - Examples (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 11 26 12) => -9 (bitwise-nor 11 26 12) => -32 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))) For i >= 0, 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-merge mask i0 i1 -> exact-integer Merge the bitstrings I0 and I1, with bitstring MASK determining from which string to take each bit. That is, RESULT[k] := if MASK[k] = 0 then I0[k] else I1[k]. or (bitwise-ior (bitwise-and (bitwise-not mask) i0) (bitwise-and mask i1)) bit-set? index i -> boolean Is bit INDEX set in bitstring I? INDEX is a non-negative exact integer. The rightmost/least-significant bit in the bitstring 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 any-bits-set? test-bits i -> boolean all-bits-set? test-bits i -> boolean Determines if any / all of the bits set in bitstring TEST-BITS are set in bitstring I. I.e., return (not (zero? (bitwise-and TEST-BITS I))) or (= TEST-BITS (bitwise-and TEST-BITS I))) respectively. first-set-bit i -> exact-integer 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 extract-bit-field size position i -> exact-integer test-bit-field? size position i -> boolean clear-bit-field size position i -> exact-integer replace-bit-field size position new-field i -> exact-integer copy-bit-field size position from to -> exact-integer These functions operate on a contiguous field of bits (a "byte," in Common-Lisp parlance) in a given bitstring I. SIZE and POSITION are non-negative exact integers specifying the field: it is the SIZE bits running from bit POSITION to bit POSITION+SIZE-1. - EXTRACT-BIT-FIELD returns the designated bit field from I, shifted down to the least-significant position in the result. - TEST-BIT-FIELD? returns true if any of the field's bits are set in bitstring I. - CLEAR-BIT-FIELD returns I with the selected field's bits zeroed out. - REPLACE-BIT-FIELD returns I with the designated bit field replaced by the least-significant SIZE bits in NEW-FIELD. - COPY-BIT-FIELD returns TO with the selected field's bits replaced by the same field's bits in FROM. ------------------------------------------------------------------------------- * Rationale & general discussion -------------------------------- - These operations interpret exact integers using two's-complement representation; integers thus represent semi-infinite bit-strings. They are only defined for exact integer arguments. - It is not optional for the associative bitwise ops to be n-ary instead of merely binary. They are required to be n-ary. Programmers can *reliably* write BITWISE-AND with 3 arguments, for example. - This design mirrors the structure of Common Lisp's pretty closely. Here are some differences: + "load" and "deposit" are the wrong verbs (e.g., Common Lisp's LDB and DPB ops), since these guys have nothing to do with the store. I chose "extract" and "replace." + Common Lisp's byte datatype doesn't seem to buy you anything over just spelling out size & position, or [start,end) values. + I punted BOOLE; it is not one with the Way of Scheme. Boolean functions are directly encoded in Scheme as first-class functions. + My name choices are more in tune with Scheme conventions (hyphenation, using "?" to mark a predicate, etc.). Common Lisp's name choices were more historically motivated, for reasons of backward compatibility with Maclisp and Zetalisp. + I punted the prefix "log" in favor of "bitwise-" (e.g, LOGNOT, BITWISE-NOT) * The integer ops are no more "logical" than the #f/#t ops, so the "log" prefix is misleading. * The integer ops are bitwise in nature; the prefix "bitwise-" more accurately reflects what they do. * There is general agreement among people I've polled that this is the right prefix. + I also punted the 6 trivial binary boolean ops. I kept the six non-trivial but less common ops. - Is the inclusive-or function written "or" or "ior"? This kind of thing trips me up all the time when I use these types of functions. In my design, there's a simple rule: it is *never* simply "or." The "or" always has modifiers -- "xor," "ior," "nor," "orc1," and "orc2." As it turns out, my boolean op names are *exactly* Common Lisp's. Although that was not an important criterion for the design, it's an extra plus. - Why not a minimal set of ops? I included extra and redundant functions such as BIT-COUNT, BITWISE-NOR, and the bit-field ops in my design. Doing so helps readability, writability, and efficiency. + Readability: Settling on a standard choice of names makes it easier to read code that uses these sorts of operations. It also means computations can be clearly expressed using the more powerful ops rather than synthesized with a snarled mess of BITWISE-AND's, -OR's, and -NOT's. Most of these derived ops are simple to implement in under three lines of code. Providing a basic implementation does not put a burden on the implementor. In fact, all but seven of the ops can be defined in 31 lines of code, which I append below. What we gain is having an agreed-upon set of names by which we can refer to these functions. + Writability: The programmer doesn't have to re-implement these functions, and stumble over the boundary cases and error checking. The programmer can express himself using a full palette of building blocks. + Efficiency: Compilers can directly implement these ops for great efficiency gains without requiring any tricky analysis. If you believe in "small is beautiful," then what is your motivation for including anything beyond BITWISE-NAND? - Why no "logical" right or left shift operations? Because they are not well defined on general integers; they are only defined on integers in some finite range. Remember that, in this library, integers are interpreted as *semi-infinite* bit strings that have only a finite number of ones or a finite number of zeroes. "Logical" shifting shifts bit strings of some fixed size. If we shift left, then leftmost bits "fall off" the end (and zeroes shift in on the right). If we shift right, then zeroes shift into the string on the left (and rightmost bits fall off the end). So to define a logical shift operation, *we must specify the size of the window.* Typically this is the width of the underlying machine's register set (e.g., 32 bits). This is blatantly machine-specific & unportable, and clearly not the right thing for Scheme's more machine-independent general integers. For Scheme's integers, arithmetic shift is the right thing. Note that this situation pertains as well in Common Lisp, and Common Lisp does exactly what this SRFI does: arithmetic shift, but no logical shift. If we were to define a "width 32" or "width 64" or "fixnum" integer datatype, then we could meaningfully define logical shift for these values. Alternately, we could define a "general" logical shift operation that took as an extra argument the size of the bitstring. At this point, we are bending over backward to force-fit an operation into Scheme that fundamentally doesn't belong. Arithmetic shift is the right thing for general integers. - In June 1996, this proposal went through a round of discussion on the Net, in particular with Will Clinger and Aubrey Jaffer. This resulted in several updates: - The functions were explicitly required to operate only on exact integers. - ASH was renamed ARITHMETIC-SHIFT. - BIT-COUNT was preferred to POP-COUNT and POPULATION-COUNT. Note that, as Clinger points out, "BIT-" is the proper prefix for this operation. After the discussion converged, the proposal sat on my disk for six years. - This is a purely functional, side-effect-free implementation of bit operations -- all operations produce new, fresh results, rather than modifying old values. This can be implemented very efficiently for small bit vectors -- small enough to be unboxed values. Algorithms that work on larger bit vectors, however (such as data-flow analysis engines), might wish an alternate data-structure and associated set of operations that permits side-effecting or linear-updating operations (or both) on bit vectors. MIT Scheme, for example, provides such a facility. This should be considered for another SRFI. (See the short summary of the MIT Scheme system below.) I suggest that the design of such a system be deferred until SRFIs for strings and vectors have been finalised. Than a bit-vector SRFI could be designed that would preserve common structure with these other SRFIs, as well as the bitwise library in this SRFI. Note also that finite bit vectors have an isomorphism to finite sets. The design of both set-package and bit-vector SRFIs would probably want to keep this in mind -- maintaining parallel functional structure in the design. ------------------------------------------------------------------------------- * Summaries of related designs ------------------------------ Below are summaries of the related libraries currently found in Common Lisp, PLT Scheme, slib, Bigloo, Scheme 48, Kawa, and MIT Scheme. I was unable to find anything for Gambit. ** Common Lisp ============== lognot n Associative: log{ior,xor,and,eqv} Non-associative: log{nand,nor,andc1,andc2,orc1,orc2} (boole op i j) op one of boole-{clr,set,1,2,c1,c2,and,ior,xor,eqv,nand,nor, andc1,andc2,orc1,orc2} (logtest testbits n) ; #t if any of the 1 bits in TESTBITS are set in N. (not (zerop (logand x y))) (logbitp index n) ; #t if bit # INDEX in N is set. (not (zero? (logand n (ash 1 index)))) ash n count logcount n ; pop-count integer-length n A CL byte is a contiguous field of bits in an int. (byte size position) -> byte-specifier (byte-size byte-spec) -> int (byte-position byte-spec) -> int (ldb bytespec n) ; Extracted byte is shifted down to lsb position. (ldb-test bytespec n) #t if any bits in the byte are 1's. (mask-field bytespec n) Zero out all bits not in bytespec. (dpb newbyte bytespec n) ; Replacement bits are low bits of newbyte (deposit-field from bytespec n) ; Replacement bits are (ldb from bytespec) ** PLT Scheme ============= bitwise-ior i1 ... bitwise-and i1 ... bitwise-xor i1 ... bitwise-not i arithmetic-shift i j ** slib ======= Slib has a clone of a chunk of CL's design. It also has (bit-extract n start end) which is like ldb on bits [start,end) of n. ** Bigloo ========= bit-or i1 i2 bit-xor i1 i2 bit-and i1 i2 bit-not i bit-lsh i1 i2 bit-rsh i1 i2 ** Chez ======= General integers: integer-length i ash i count Fixnums: fxlogand i j fxlogor i j fxlogxor i j fxlognot i fxsll i count ("shift left logical") fxsrl i count ("shift right logical") fxsla i count ("shift left arithmetic") fxsra i count ("shift right arithmetic") ** Scheme 48 ============ bitwise-not i bitwise-and i1 ... bitwise-ior i1 ... bitwise-xor i1 ... arithmetic-shift i count ** MIT Scheme ============= Fixnums: fix:not i fix:and i j fix:andc i j fix:or i j fix:xor i j fix:lsh i count MIT Scheme also has a distinct datatype, the "bit vector." A bit vector is *very* different, in that it its elements are mutable -- it is a mutable vector of bits. Constants are written with a sharp-star prefix, e.g. #*11111. (make-bit-string k init) (bit-string-allocate k) (bit-string-copy bs) (bit-string? object) (bit-string-length bs) (bit-string-ref bs k) -> boolean (bit-string-set! bs k) (bit-string-clear! bs k) (bit-substring-find-next-set-bit bs start end) (bit-string-append bs1 bs2) (bit-substring bs start end) (bit-string-zero? bs) (bit-string=? bs1 bs2) (bit-string-not bs) (bit-string-movec! target-bs source-bs) ; Destructive NOT operation (bit-string-and bs1 bs2) (bit-string-and! target-bs1 bs2) (bit-string-andc bs1 bs2) (bit-string-andc! target-bs1 bs2) (bit-string-or bs1 bs2) (bit-string-or! target-bs1 bs2) (bit-string-xor bs1 bs2) (bit-string-xor! target-bs1 bs2) (bit-string-fill! bs init) ; init is a boolean (bit-string-move! target-bs bs) ; Must be of the same length (bit-substring-move-right! source-bs start1 end1 target-bs start2) (unsigned-integer->bit-string length integer) (signed-integer->bit-string length integer) (bit-string->unsigned-integer bit-string) (bit-string->signed-integer bit-string) ** Guile & Kawa =============== logand i1 ... logior i1 ... logxor i1 ... lognot i logtest i j (any-bit-set?) logbit? index i ash i count logcount i integer-length i bit-extract i start end ------------------------------------------------------------------------------- * Reference implementation -------------------------- There are 24 functions in the spec. 15 can be defined in under two lines of code; REPLACE-BIT-FIELD needs three lines; and BITWISE-EQV needs five. This is not an onerous implementation load; I provide the code below. As this is only 31 lines of code, it hardly seems reasonable to bother discussing copyright. To lay the issue to rest, I am the sole author, and I place it in the public domain. That leaves 7 basic functions that must be primitively defined for each implementation: BITWISE-{NOT,AND,IOR,XOR}, ARITHMETIC-SHIFT, BIT-COUNT, and INTEGER-LENGTH. Slib has implementations of even these functions using R4RS arithmetic, so a simple-minded implementation again doesn't need to do much to support them -- however, slib's general implementations are terribly inefficient relative to native support and should *not* be used except in case of dire emergency. (It's quite clever code, nonetheless, to provide the semantics with such little support.) A good implementation might choose to provide direct compiler/interpreter support for these derived functions, or might simply define them to be integrable -- i.e., inline-expanded. The n-ary BITWISE-EQV function should also receive primitive compiler/interpreter support so that the expensive n-ary mechanism is not invoked in the standard cases -- that is, an application of BITWISE-EQV should be rewritten into an equivalent tree applying some two-argument primitive to the arguments, in the same manner that statically-known n-ary applications of associative operations such as + and * are handled efficiently: (bitwise-eqv) => -1 (bitwise-eqv i) => i (bitwise-eqv i j) => (%bitwise-eqv i j) (bitwise-eqv i j k) => (%bitwise-eqv (%bitwise-eqv i j) k) (bitwise-eqv i j k l) => (%bitwise-eqv (%bitwise-eqv (%bitwise-eqv i j) k) l) ;;; The seven non-trivial boolean functions in terms ;;; of not, and, or & xor. (define (bitwise-nand i j) (bitwise-not (bitwise-and i j))) (define (bitwise-nor i j) (bitwise-not (bitwise-ior i j))) (define (bitwise-andc1 i j) (bitwise-and (bitwise-not i) j)) (define (bitwise-andc2 i j) (bitwise-and i (bitwise-not j))) (define (bitwise-orc1 i j) (bitwise-ior (bitwise-not i) j)) (define (bitwise-orc2 i j) (bitwise-ior i (bitwise-not j))) (define (bitwise-eqv . args) (let lp ((args args) (ans -1)) (if (pair? args) (lp (cdr args) (bitwise-not (bitwise-xor ans (car args)))) ans))) ;;; Helper function -- make a mask of SIZE 1-bits, e.g. (%MASK 3) = #b111. ;;; Suppose your Scheme's fixnums are N bits wide (counting the sign bit, ;;; not counting any tag bits). This version, due to Marc Feeley, will ;;; handle SIZE in the range [0,N-1] without overflowing to bignums. ;;; (For SIZE >= N, the correct bignum value is also produced.) (define (%mask size) (bitwise-not (arithmetic-shift -1 size))) ;;; This alternate, mathematically-equivalent expression ;;; (- (arithmetic-shift 1 size) 1) ;;; is not as good -- it only handles SIZE in the range [0,N-2] without ;;; overflowing to bignums. ;;; ;;; Finally, note that even Feeley's expression can't build an N-bit mask ;;; without bignum help. This is fundamental, since the interpretation ;;; of fixed-size fixnum bit patterns as semi-infinite-bit-strings is that ;;; you replicate the high bit out to infinity. So you have to have a ;;; zero "stop bit" appearing after that highest one bit to turn off the ;;; replication of the ones. (define (bit-set? index n) (not (zero? (bitwise-and (arithmetic-shift 1 index) n)))) (define (any-bits-set? test-bits n) (not (zero? (bitwise-and test-bits n)))) (define (all-bits-set? test-bits n) (= test-bits (bitwise-and test-bits n))) (define (bitwise-merge mask n0 n1) (bitwise-ior (bitwise-and mask n1) (bitwise-and (bitwise-not mask) n0))) ;;; Bit-field ops (define (extract-bit-field size position n) (bitwise-and (%mask size) (arithmetic-shift n (- position)))) (define (test-bit-field? size position n) (not (zero? (bitwise-and (arithmetic-shift n (- position)) (%mask size))))) ;; Integrating i-b-f reduces nicely. (define (clear-bit-field size position n) (replace-bit-field size position 0 n)) ;;; Oops -- intermediate ARITHMETIC-SHIFT can fixnum-overflow on fixnum args. ;(define (replace-bit-field size position newfield n) ; (copy-bit-field size position (arithmetic-shift newfield position) n)) ;;; This three-line version won't fixnum-overflow on fixnum args. (define (replace-bit-field size position newfield n) (let ((m (%mask size))) (bitwise-ior (bitwise-and n (bitwise-not (arithmetic-shift m position))) (arithmetic-shift (bitwise-and newfield m) position)))) (define (copy-bit-field size position from to) (bitwise-merge (arithmetic-shift (%mask size) position) to from)) ;; Simple definition ;(define (first-set-bit i) ; (and (not (zero? i)) ; (let lp ((j 0) (i start)) ; (if (bit-set? i 0) j ; (lp (+ j 1) (arithmetic-shift i 1)))))) ;;; Clever definition, assuming you have a fast BIT-COUNT. (define (first-set-bit i) (- (bit-count (bitwise-xor i (- i 1))) 1)) ------------------------------------------------------------------------------- * Topics to be resolved during discussion phase ----------------------------------------------- I particularly solicit comments about the following topics. ** SIZE/POSITION vs. FROM/TO field specs ======================================== Several functions in this library extract-bit-field size position i -> integer test-bit-field? size position i -> boolean clear-bit-field size position i -> integer replace-bit-field size position new-field i -> integer copy-bit-field size position from to -> integer specify a contiguous "field" of bits in a bitstring. There are two conventions we might use to do so: - SIZE/POSITION E.g., "the 8-bit field beginning at bit 3", and - FROM/TO E.g., "the field from bit 3 up to, but not including, bit 11", or, perhaps, "the field from bit 3 up to bit 10, inclusive." FROM/TO specs are conventionally and most usefully "half-open" specs, meaning "all i such that FROM <= i and i < TO" -- the FROM index is included and the TO index is excluded. I have chosen to use SIZE/POSITION instead of FROM/TO for this library. Doing so eliminates any possibility of fencepost errors on the TO endpoint. It is also the convention chosen by Common Lisp. It is not, however, a widely-used convention within Scheme. Most ranges in Scheme are specified with half-open intervals of the [from,to) form (e.g., (substring s from to)). One might argue that SIZE/POSITION is still the right thing for bit fields, as they are, in practice, frequently of fixed size, unlike element ranges in strings or vectors. ** Order of arguments for non-bitstring parameters ================================================== The "bitwise boolean" functions such as BITWISE-AND only take bitstring parameters. But the following 10 functions are different in that they take other *kinds* of parameters (masks, indices, field sizes) that indicate *the exact operation to perform* on the bitstring parameter(s): arithmetic-shift i count -> integer bitwise-merge mask i0 i1 -> integer bit-set? index i -> boolean any-bits-set? test-bits i -> boolean all-bits-set? test-bits i -> boolean extract-bit-field size position i -> integer test-bit-field? size position i -> boolean clear-bit-field size position i -> integer replace-bit-field size position new-field i -> integer copy-bit-field size position from to -> integer Note that in all of these functions, with the sole exception of ARITHMETIC-SHIFT, the bitstring parameter comes last. This is consistent with an "operation currying" convention, wherein the arguments that determine the operation come first, and the actual value upon which we operate comes last. MAP and FOLD, for example, work this way, too. (The "op currying" convention is actually useful in SML; in Scheme, its utility is almost entirely as a mnemonic convention to aid programmers in remembering argument order.) ARITHMETIC-SHIFT is entrenched by long and consistent tradition in the indicated parameter order; it would be a mistake to alter this. Every implementation of Scheme I have checked that offers a bit-shift operation on integers (PLT Scheme, slib, Bigloo, Scheme 48, and MIT Scheme), as well as Common Lisp, uses the "i count" argument order. As an alternative to the "op currying" order, we could use the "data-structure accessor" convention, wherein the data-structure being accessed (the bitstring) comes first, and the "selector" arguments come after. For example, this is the convention used for the functions VECTOR-REF and STRING-REF. One could make the argument that this convention could be reasonably applied to some of these operators, such as BIT-SET? I recommend leaving things as they are, for maximal consistency with a simple rule. This also provides consistency with Common Lisp, whose bitwise functions uniformly use the ops-curry convention (see the "related designs" summary below). ** The name "bit-set?" ====================== BIT-SET? uses the term "bit set," but that sounds like "Is this a set of bits?" as well as the intended "is the bit set?" On the other hand, a set of bits is a not-very-useful notion (there are, after all, only four such sets), so I haven't pre-empted anything we'd ever really want for some other purpose, such as a term like "bit vector" or something... ------------------------------------------------------------------------------- * References & Links -------------------- This document, in HTML: http://srfi.schemers.org/srfi-33/srfi-33.html [This link may not be valid while the SRFI is in draft form.] This document, in simple text format: http://srfi.schemers.org/srfi-33/srfi-33.txt Archive of SRFI-33 discussion-list email: http://srfi.schemers.org/srfi-33/mail-archive/maillist.html SRFI web site: http://srfi.schemers.org/ [CommonLisp] Common Lisp: the Language Guy L. Steele Jr. (editor). Digital Press, Maynard, Mass., second edition 1990. Available at http://www.elwood.com/alu/table/references.htm#cltl2 The Common Lisp "HyperSpec," produced by Kent Pitman, is essentially the ANSI spec for Common Lisp: http://www.xanalys.com/software_tools/reference/HyperSpec/ [R5RS] Revised^5 Report on the Algorithmic Language Scheme, R. Kelsey, W. Clinger, J. Rees (editors). Higher-Order and Symbolic Computation, Vol. 11, No. 1, September, 1998. and ACM SIGPLAN Notices, Vol. 33, No. 9, October, 1998. Available at http://www.schemers.org/Documents/Standards/ ------------------------------------------------------------------------------- * Copyright ----------- This document is copyright (C) Olin Shivers (1998, 1999). All Rights Reserved. However, the program source found in section "Reference Implementation" is by Olin Shivers and explicitly placed in the public domain. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ------------------------------------------------------------------------------- * Ispell "buffer local" dictionary ---------------------------------- Ispell dumps "buffer local" words here. Please ignore. LocalWords: ops SRFI RS bitstrings ary ior xor eqv nand andc orc const arg CL LocalWords: op neg CL's LDB DPB datatype BOOLE Maclisp Zetalisp LOGNOT Jaffer LocalWords: Clinger lognot boole clr logtest testbits zerop logand logbitp bs LocalWords: logcount int ldb bytespec lsb dpb newbyte slib HTML init ref lib LocalWords: fixnum newfield srfi html txt Rees SIGPLAN movec finalised expt LocalWords: bitstring nullary writability AND's OR's NOT's unboxed PLT LocalWords: SRFIs Bigloo Kawa lsh rsh Chez Fixnums fxlogand fxlogor fxlogxor LocalWords: fxlognot fxsll fxsrl fxsla fxsra logior logxor logbit slib's args LocalWords: inline lp cdr fixnums Feeley bignums bignum Feeley's indices SML LocalWords: accessor pre empted CommonLisp cltl HyperSpec