SRFI 151: Bitwise Operations

  1. SRFI 151: Bitwise Operations
    1. Author
    2. Maintainer
    3. Repositories
    4. Status
    5. Abstract
    6. Rationale
      1. General design principles
      2. Common Lisp
      3. SRFI 33
      4. SRFI 60
      5. Other sources
      6. Argument ordering and semantics
      7. Bit processing order
    7. Specification
      1. Procedure index
      2. Basic operations
      3. Integer operations
      4. Single-bit operations
      5. Bit field operations
      6. Bits conversion
      7. Fold, unfold, and generate
    8. Implementation
  2. Comparison of proposals
    1. Acknowledgements
    2. CHICKEN egg version history
      1. 1.0.2
      2. 1.0.1
      3. 1.0.0
    3. Copyright

Author

John Cowan

Maintainer

Sören Tempel

Repositories

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi+minus+151+at+srfi+dotschemers+dot+org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

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 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 has been clarified and some of the procedures' names have been changed. See Bit processing order for details.

Rationale

General design principles

Common Lisp

The core of this 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

Argument ordering and semantics

Bit processing order

In SLIB and SRFI 60, the the order in which bits were processed by integer->list and list->integer was not clearly specified. When SRFI 142 was written, the specification was clarified to process bits from least significant to most significant, so that (integer->list 6) => (#f #t #t). However, the SLIB and SRFI 60 implementation processed them from the most significant bit to the least-significant bit, so that (integer->list 6) => (#t #t #f). This SRFI retains the little-endian order, but renames the procedures to bits->list and list->bits to avoid a silent breaking change from SLIB and SRFI 60. The same is true of the closely analogous integer->vector, vector->integer, and bits procedures.

Specification

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
   
   bits->list list->bits bits->vector vector->bits
   bits
   bitwise-fold bitwise-for-each bitwise-unfold
   make-bitwise-generator
   

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

[procedure] (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.

[procedure] (bitwise-and i)
[procedure] (bitwise-ior i)
[procedure] (bitwise-xor i)
[procedure] (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
[procedure] (bitwise-nand i j)
[procedure] (bitwise-nor i j)
[procedure] (bitwise-andc1 i j)
[procedure] (bitwise-andc2 i j)
[procedure] (bitwise-orc1 i j)
[procedure] (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

[procedure] (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
[procedure] (bit-count i)

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

Compatibility note: The R6RS analogue bitwise-bit-count applies bitwise-not to the population count before returning it if i is 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
[procedure] (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
[procedure] (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 1, then the kth bit of the result is the kth bit of i, otherwise the kth bit of j.

    (bitwise-if 3 1 8) => 9
    (bitwise-if 3 8 1) => 0
    (bitwise-if 1 1 2) => 3
    (bitwise-if #b00111100 #b11110000 #b00001111) => #b00110011

Single-bit operations

As always, the rightmost/least-significant bit in i is bit 0.

[procedure] (bit-set? index i)

Is bit index set in bitstring i (where index is a non-negative exact integer)?

Compatibility note: The R6RS analogue bitwise-bit-set? accepts its arguments in the opposite order.

    (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
[procedure] (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.

Compatibility note: The R6RS analogue bitwise-copy-bit as originally documented has a completely different interface. (bitwise-copy-bit dest index source) replaces the index'th bit of dest with the index'th bit of source. It is equivalent to (bit-field-replace-same dest source index (+ index 1)). However, an erratum made a silent breaking change to interpret the third argument as 0 for a false bit and 1 for a true bit. Some R6RS implementations applied this erratum but others did not.

(copy-bit 0 0 #t) => #b1
(copy-bit 2 0 #t) => #b100
(copy-bit 2 #b1111 #f) => #b1011
[procedure] (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
[procedure] (any-bit-set? test-bits i)
[procedure] (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-andtest-bits i))) and (= test-bits (bitwise-and test-bits i))) respectively.

    (any-bit-set? 3 6) => #t
    (any-bit-set? 3 12) => #f
    (every-bit-set? 4 6) => #t
    (every-bit-set? 7 6) => #f
[procedure] (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.

[procedure] (bit-field i start end)

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

   (bit-field #b1101101010 0 4) => #b1010
   (bit-field #b1101101010 3 9) => #b101101
   (bit-field #b1101101010 4 9) => #b10110
   (bit-field #b1101101010 4 10) => #b110110
   (bit-field 6 0 1) => 0
   (bit-field 6 1 3) => 3
   (bit-field 6 2 999) => 1
   (bit-field #x100000000000000000000000000000000 128 129) => 1
[procedure] (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-any? #b1001001 1 6) => #t
  (bit-field-any? #b1000001 1 6) => #f
[procedure] (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-every? #b1011110 1 5) => #t
  (bit-field-every? #b1011010 1 5) => #f
[procedure] (bit-field-clear i start end)
[procedure] (bit-field-set i start end)

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

   (bit-field-clear #b101010 1 4) => #b100000
   (bit-field-set #b101010 1 4) => #b101110
[procedure] (bit-field-replace dest source start end)

Returns dest with the field replaced by the least-significant end-start bits in source.

   (bit-field-replace #b101010 #b010 1 4) => #b100100
   (bit-field-replace #b110 1 0 1) => #b111
   (bit-field-replace #b110 1 1 2) => #b110
[procedure] (bit-field-replace-same dest source start end)

Returns dest with its field replaced by the corresponding field in source.

   (bit-field-replace-same #b1111 #b0000 1 3) => #b1001
[procedure] (bit-field-rotate i count start end)

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

Compatibility note: The R6RS analogue bitwise-rotate-bit-field uses the argument ordering i start end count.

   (bit-field-rotate #b110 0 0 10) => #b110
   (bit-field-rotate #b110 0 0 256) => #b110
   (bit-field-rotate #x100000000000000000000000000000000 1 0 129) => 1
   (bit-field-rotate #b110 1 1 2) => #b110
   (bit-field-rotate #b110 1 2 4) => #b1010
   (bit-field-rotate #b0111 -1 1 4) => #b1011
[procedure] (bit-field-reverse i start end)

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

   (bit-field-reverse 6 1 3) => 6
   (bit-field-reverse 6 1 4) => 12
   (bit-field-reverse 1 0 32) => #x80000000
   (bit-field-reverse 1 0 31) => #x40000000
   (bit-field-reverse 1 0 30) => #x20000000
   (bit-field-reverse #x140000000000000000000000000000000 0 129) => 5

Bits conversion

[procedure] (bits->list i [len])
[procedure] (bits->vector i [len])

Returns a list/vector of len booleans corresponding to each bit of the non-negative integer i, returning bit #0 as the first element, bit #1 as the second, and so on. #t is returned for each 1; #f for 0.

   (bits->list #b1110101)) => (#t #f #t #f #t #t #t)
   (bits->list 3 5)) => (#t #t #f #f #f)
   (bits->list 6 4)) => (#f #t #t #f)

   (bits->vector #b1110101)) => #(#t #f #t #f #t #t #t)
[procedure] (list->bits list)
[procedure] (vector->bits vector)

Returns an integer formed from the booleans in list/vector, using the first element as bit #0, the second element as bit #1, and so on. 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.

   (list->bits '(#t #f #t #f #t #t #t)) => #b1110101
   (list->bits '(#f #f #t #f #t #f #t #t #t)) => #b111010100
   (list->bits '(#f #t #t)) => 6
   (list->bits '(#f #t #t #f)) => 6
   (list->bits '(#f #f #t #t)) => 12

   (vector->bits '#(#t #f #t #f #t #t #t)) => #b1110101
   (vector->bits '#(#f #f #t #f #t #f #t #t #t)) => #b111010100
   (vector->bits '#(#f #t #t)) => 6
   (vector->bits '#(#f #t #t #f)) => 6
   (vector->bits '#(#f #f #t #t)) => 12

For positive integers, bits->list and list->bits are inverses in the sense of equal?, and so are bits->vector and vector->bits.

[procedure] (bits bool ...)

Returns the integer coded by the bool arguments. The first argument is bit #0, the second argument is bit #1, and so on. Note that the result is never a negative integer.

  (bits #t #f #t #f #t #t #t) => #b1110101
  (bits #f #f #t #f #t #f #t #t #t) => #b111010100

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.

[procedure] (bitwise-fold proc seed i)

For each bit b of i from bit #0 (inclusive) to bit (integer-length i) (exclusive), 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 the last bit has been processed, the final accumulated result becomes the result of bitwise-fold.

  (bitwise-fold cons '() #b1010111) => (#t #f #t #f #t #t #t)
[procedure] (bitwise-for-each proc i)

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

      (let ((count 0))
        (bitwise-for-each (lambda (b) (if b (set! count (+ count 1))))
                          #b1010111)
       count)
[procedure] (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.

  (bitwise-unfold (lambda (i) (= i 10))
                  even?
                  (lambda (i) (+ i 1))
                  0)) => #b101010101
[procedure] (make-bitwise-generator i)

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

  (let ((g (make-bitwise-generator #b110)))
    (test #f (g))
    (test #t (g))
    (test #t (g))
    (test #f (g)))

Implementation

The implementation is in the repository of this SRFI, and includes the following files:

It is very important for performance to provide a C or assembly implementation of the core operators. There is a cond-expand in srfi-151.sld that can be extended to take advantage of this. Currently it contains options for Chibi and Gauche. In addition, if the R6RS library (rnrs arithmetic bitwise) is available, it will be used in place of bitwise-core.scm.

Temporary note: Chibi assumes a C library named bit. The bit.{so,dll} file can be found in $PREFIX/lib/chibi/srfi/{33,142}. Even more temporary note: this is buggy, so the Chibi arm of the conditional is currently commented out.

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. ''Italic procedure names'' indicate that the equivalence is only rough: argument orderings or precise semantics are not the same as in 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-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-bits-set? --- any-bit-set?
See if all mask bits set --- all-bits-set? every-bit-set? --- --- every-bit-set?
Replace single bit --- --- copy-bit copy-bit bitwise-copy-bit copy-bit
Swap bits --- --- --- --- --- bit-swap
Find first bit set --- first-set-bit first-set-bit log2-binary-factors, first-set-bit bitwise-first-bit-set 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 copy-bit-field bit-field-copy --- --- bit-field-replace-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
Bits to boolean list --- --- --- integer->list --- bits->list
Bits to boolean vector --- --- --- --- --- bits->vector
Boolean list to bits --- --- --- list->integer --- list->bits
Boolean vector to bits --- --- --- --- --- vector->bits
Booleans to integer --- --- --- booleans->integer --- bits
Bitwise fold --- --- --- --- --- bitwise-fold
Bitwise for-each --- --- --- --- --- bitwise-for-each
Bitwise unfold --- --- --- --- --- bitwise-unfold
Bit generator --- --- --- --- --- make-bitwise-generator

Acknowledgements

This SRFI would not exist without the efforts of Olin Shivers, Aubrey Jaffer, and Taylor Campbell.

CHICKEN egg version history

1.0.2

1.0.1

1.0.0

 Copyright (C) John Cowan (2016).  All Rights Reserved.
 
 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.