You can edit this page using wiki syntax for markup.

Article contents:== SRFI 151: Bitwise Operations [[toc:]] === Author John Cowan === Maintainer Sören Tempel === Repositories * Canonical SRFI-151 repository: [[https://github.com/scheme-requests-for-implementation/srfi-151|https://github.com/scheme-requests-for-implementation/srfi-151]] * SRFI-151 packaged as a CHICKEN egg: [[https://github.com/nmeum/srfi-151|https://github.com/nmeum/srfi-151]] (the egg comes from this repository) === Status This SRFI is currently in ''final'' status. Here is [[https://srfi.schemers.org/srfi-process.html|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 [[http://srfi.schemers.org/srfi-list-subscribe.html|these instructions]]. You can access previous messages via the mailing list [[https://srfi-email.schemers.org/srfi-151|archive]]. * Received: 2017-05-02 * Draft #1 published: 2017-05-03 * Draft #2 published: 2017-05-14 * Draft #3 published: 2017-05-21 * Draft #4 published: 2017-07-02 * Draft #5 published: 2017-07-10 * Finalized: 2017-07-10 * Revised to fix errata: ** 2017-07-25 (Fixed examples under {{bit-field-any?}} and {{bit-field-every?}}. Removed obsolete test.) ** 2017-10-18 (Fixed small errors in comparison table, which is in a non-normative section.) ** 2019-04-06 (Italicize {{integer->list}}, {{list->integer}}, and {{booleans->integer}} to reflect the changes made in SRFI 151 from SRFI 142.) === 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 [[https://srfi.schemers.org/srfi-33/srfi-33.html|SRFI 33]], with some changes and additions from [[http://srfi.schemers.org/srfi-33/mail-archive/msg00023.html|Olin's late revisions to SRFI 33]] (which were never consummated). [[https://srfi.schemers.org/srfi-60/srfi-60.html|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. [[http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-12.html#node_sec_11.4|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 [[https://srfi.schemers.org/srfi-133/srfi-133.html|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: # The {{bitwise-if}} function has the argument ordering of SLIB, SRFI 60, and R6RS rather than the ordering of SRFI 33. # 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 * These operations interpret exact integers using two's-complement representation. * The associative bitwise ops are required to be n-ary. Programmers can reliably write {{bitwise-and}} with 3 arguments, for example. * The word {{or}} is never used by itself, only with modifiers: {{xor}}, {{ior}}, {{nor}}, {{orc1}}, or {{orc2}}. This is the same rule as Common Lisp. * Extra and redundant functions such as {{bitwise-count}}, {{bitwise-nor}} and the bit-field ops have been included. 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, {{bitwise-or}}s, and {{bitwise-not}}s. What we gain is having an agreed-upon set of names by which we can refer to these functions. If you believe in "small is beautiful," then what is your motivation for including anything beyond {{bitwise-nand}}? * Programmers don't have to re-implement the redundant functions, and stumble over the boundary cases and error checking, but can express themselves using a full palette of building blocks. * Compilers can directly implement many of these ops for great efficiency gains without requiring any tricky analysis. * Logical right or left shift operations are excluded 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 zeros. Logical shifting operates on bit strings of some fixed size. If we shift left, then leftmost bits "fall off" the end (and zeros shift in on the right). If we shift right, then zeros 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. ==== Common Lisp The core of 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 they have nothing to do with the store. * {{boole}} has been removed; it is not one with the Way of Scheme. Boolean functions are directly encoded in Scheme as first-class functions. * The 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. * The prefix {{log}} has been changed to {{bitwise-}} (e.g, {{lognot}} to {{bitwise-not}}), as the prefix {{bitwise-}} more accurately reflects what they do. * The six trivial binary boolean ops that return constants, the left or right arguments, and the {{bitwise-not}} of the left or right arguments, do not appear in this SRFI. ==== SRFI 33 This SRFI contains all the procedures of SRFI 33, and retains their original names with these exceptions: * The name {{bitwise-merge}} is replaced by {{bitwise-if}}, the name used in SRFI 60 and R6RS. * The name {{extract-bit-field}} ({{bit-field-extract}} in Olin's revisions) is replaced by {{bit-field}}, the name used in SRFI 60 and R6RS. * The names {{any-bits-set?}} and {{all-bits-set?}} are replaced by {{any-bit-set?}} and {{every-bit-set?}}, in accordance with Olin's revisions. * The name {{test-bit-field?}} has been renamed {{bit-field-any?}} and supplemented with {{bit-field-every?}}, in accordance with Olin's revisions. * Because {{copy-bit-field}} means different things in SRFI 33 and SRFI 60, SRFI 33's name {{copy-bit-field}} ({{bit-field-copy}} in Olin's revisions) has been changed to {{bit-field-replace-same}}. ==== SRFI 60 SRFI 60 includes six procedures that do not have SRFI 33 equivalents. They are incorporated into this SRFI as follows: * The names {{rotate-bit-field}} and {{reverse-bit-field}} are replaced by {{bit-field-rotate}} and {{bit-field-reverse}}, by analogy with Olin's revisions. * The procedure {{copy-bit}} is incorporated into this SRFI with the same name. * The procedures {{integer->list}} and {{list->integer}} are incorporated into this SRFI with the slightly different names {{integer->bits}} and {{bits->integer}} because they are incompatible with SRFI 60. * The procedure {{booleans->integer}} is a convenient way to specify a bitwise integer: it accepts an arbitrary number of boolean arguments and returns a non-negative integer. So in this SRFI it has the short name {{bits}}, roughly analogous to {{list}}, {{string}}, and {{vector}}. ==== Other sources * The following procedures are inspired by [[https://srfi.schemers.org/srfi-133/srfi-133.html|SRFI 133]]: {{bit-swap}}, {{bitwise-fold}}, {{bitwise-for-each}}, {{bitwise-unfold}}. * The procedure {{bit-field-set}} is the counterpart of {{bit-field-clear}}. * The procedures {{bits->vector}} and {{vector->bits}} are inspired by their list counterparts. * The {{make-bitwise-generator}} procedure is a generator constructor similar to those provided by [[https://srfi.schemers.org/srfi/srfi-127.html|SRFI 127]]. ==== Argument ordering and semantics * In general, these procedures place the bitstring arguments to be operated on first. Where the operation is not commutative, the "destination" argument that provides the background bits to be operated on is placed before the "source" argument that provides the bits to be transferred to it. * In SRFI 33, {{bitwise-nand}} and {{bitwise-nor}} accepted an arbitrary number of arguments even though they are not commutative. Olin's late revisions made them dyadic, and so does this SRFI. * Common Lisp bit-field operations use a ''byte spec'' to encapsulate the position and size of the field. SRFI 33 bit-field operations had leading ''position'' and ''size'' arguments instead. These have been replaced in this SRFI by trailing ''start'' (inclusive) and ''end'' (exclusive) arguments, the convention used not only in SRFI 60 and R6RS but also in most other subsequence operations in Scheme standards and SRFIs. * In SRFI 60, the {{bitwise-if}} function was defined with a different argument ordering from SRFI 33's {{bitwise-merge}}, but was provided under both names, using the SLIB ordering. SRFI 142 adopted the SRFI 33 ordering rather than the SLIB and R6RS ordering. Since SLIB and R6RS have seen far more usage than SRFI 33, this SRFI adopts the SRFI 60 ordering instead. ==== 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 <nowiki>2⁰</nowiki> bit, bit #1 is the next or <nowiki>2¹</nowiki> bit, and so forth. ==== Basic operations <procedure>(bitwise-not i)</procedure> Returns the bitwise complement of ''i''; that is, all 1 bits are changed to 0 bits and all 0 bits to 1 bits. <enscript highlight=scheme> (bitwise-not 10) => -11 (bitwise-not -37) => 36 </enscript> 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><br> <procedure>(bitwise-ior i)</procedure><br> <procedure>(bitwise-xor i)</procedure><br> <procedure>(bitwise-eqv i)</procedure> 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 <enscript highlight=scheme> (bitwise-ior (bitwise-and a b c) (bitwise-and (bitwise-not a) (bitwise-not b) (bitwise-not c))) </enscript> Rather, it produces {{(bitwise-eqv a (bitwise-eqv b c))}} or the equivalent {{(bitwise-eqv (bitwise-eqv a b) c)}}. <enscript highlight=scheme> (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 </enscript> <procedure>(bitwise-nand i j)</procedure><br> <procedure>(bitwise-nor i j)</procedure><br> <procedure>(bitwise-andc1 i j)</procedure><br> <procedure>(bitwise-andc2 i j)</procedure><br> <procedure>(bitwise-orc1 i j)</procedure><br> <procedure>(bitwise-orc2 i j)</procedure> These operations are not associative. <enscript highlight=scheme> (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 </enscript> ==== Integer operations <procedure>(arithmetic-shift i count)</procedure> Returns the arithmetic left shift when ''count''>0; right shift when ''count < 0''. <enscript highlight=scheme> (arithmetic-shift 8 2) => 32 (arithmetic-shift 4 0) => 4 (arithmetic-shift 8 -1) => 4 (arithmetic-shift -100000000000000000000000000000000 -100) => -79 </enscript> <procedure>(bit-count i)</procedure> 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. <enscript highlight=scheme> (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 </enscript> <procedure>(integer-length i)</procedure> The number of bits needed to represent ''i'', i.e. <enscript highlight=scheme> (ceiling (/ (log (if (negative? integer) (- integer) (+ 1 integer))) (log 2))) </enscript> 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. <enscript highlight=scheme> (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 </enscript> <procedure>(bitwise-if mask i j)</procedure> Merge the bitstrings ''i'' and ''j'', with bitstring ''mask'' determining from which string to take each bit. That is, if the ''k''th bit of ''mask'' is 1, then the ''k''th bit of the result is the ''k''th bit of ''i'', otherwise the ''k''th bit of ''j''. <enscript highlight=scheme> (bitwise-if 3 1 8) => 9 (bitwise-if 3 8 1) => 0 (bitwise-if 1 1 2) => 3 (bitwise-if #b00111100 #b11110000 #b00001111) => #b00110011 </enscript> ==== Single-bit operations As always, the rightmost/least-significant bit in ''i'' is bit 0. <procedure>(bit-set? index i)</procedure> 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. <enscript highlight=scheme> (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 </enscript> <procedure>(copy-bit index i boolean)</procedure> Returns an integer the same as ''i'' except in the ''index''th 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. <enscript highlight=scheme> (copy-bit 0 0 #t) => #b1 (copy-bit 2 0 #t) => #b100 (copy-bit 2 #b1111 #f) => #b1011 </enscript> <procedure>(bit-swap index1 index2 i)</procedure> Returns an integer the same as ''i'' except that the ''index1''th bit and the ''index2''th bit have been exchanged. <enscript highlight=scheme> (bit-swap 0 2 4) => #b1 </enscript> <procedure>(any-bit-set? test-bits i)</procedure><br> <procedure>(every-bit-set? test-bits i)</procedure> 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''{{)))}} and {{(= }}''test-bits''{{ (bitwise-and}} ''test-bits i''))) respectively. <enscript highlight=scheme> (any-bit-set? 3 6) => #t (any-bit-set? 3 12) => #f (every-bit-set? 4 6) => #t (every-bit-set? 7 6) => #f </enscript> <procedure>(first-set-bit i)</procedure> 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). <enscript highlight=scheme> (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 </enscript> ==== 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)</procedure> Returns the field from ''i'', shifted down to the least-significant position in the result. <enscript highlight=scheme> (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 </enscript> <procedure>(bit-field-any? i start end)</procedure> Returns true if any of the field's bits are set in bitstring ''i'', and false otherwise. <enscript highlight=scheme> (bit-field-any? #b1001001 1 6) => #t (bit-field-any? #b1000001 1 6) => #f </enscript> <procedure>(bit-field-every? i start end)</procedure> Returns false if any of the field's bits are not set in bitstring ''i'', and true otherwise. <enscript highlight=scheme> (bit-field-every? #b1011110 1 5) => #t (bit-field-every? #b1011010 1 5) => #f </enscript> <procedure>(bit-field-clear i start end)</procedure><br> <procedure>(bit-field-set i start end)</procedure> Returns ''i'' with the field's bits set to all 0s/1s. <enscript highlight=scheme> (bit-field-clear #b101010 1 4) => #b100000 (bit-field-set #b101010 1 4) => #b101110 </enscript> <procedure>(bit-field-replace dest source start end)</procedure> Returns ''dest'' with the field replaced by the least-significant ''end-start'' bits in ''source''. <enscript highlight=scheme> (bit-field-replace #b101010 #b010 1 4) => #b100100 (bit-field-replace #b110 1 0 1) => #b111 (bit-field-replace #b110 1 1 2) => #b110 </enscript> <procedure>(bit-field-replace-same dest source start end)</procedure> Returns ''dest'' with its field replaced by the corresponding field in ''source''. <enscript highlight=scheme> (bit-field-replace-same #b1111 #b0000 1 3) => #b1001 </enscript> <procedure>(bit-field-rotate i count start end)</procedure> 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''. <enscript highlight=scheme> (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 </enscript> <procedure>(bit-field-reverse i start end)</procedure> Returns ''i'' with the order of the bits in the field reversed. <enscript highlight=scheme> (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 </enscript> ==== Bits conversion <procedure>(bits->list i [len])</procedure><br> <procedure>(bits->vector i [len])</procedure> 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. <enscript highlight=scheme> (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) </enscript> <procedure>(list->bits list)</procedure><br> <procedure>(vector->bits vector)</procedure> 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. <enscript highlight=scheme> (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 </enscript> 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 ...)</procedure> 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. <enscript highlight=scheme> (bits #t #f #t #f #t #t #t) => #b1110101 (bits #f #f #t #f #t #f #t #t #t) => #b111010100 </enscript> ==== 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)</procedure> 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}}. <enscript highlight=scheme> (bitwise-fold cons '() #b1010111) => (#t #f #t #f #t #t #t) </enscript> <procedure>(bitwise-for-each proc i)</procedure> 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. <enscript highlight=scheme> (let ((count 0)) (bitwise-for-each (lambda (b) (if b (set! count (+ count 1)))) #b1010111) count) </enscript> <procedure>(bitwise-unfold stop? mapper successor seed)</procedure> 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. <enscript highlight=scheme> (bitwise-unfold (lambda (i) (= i 10)) even? (lambda (i) (+ i 1)) 0)) => #b101010101 </enscript> <procedure>(make-bitwise-generator i)</procedure> Returns a [[https://srfi.schemers.org/srfi-121/srfi-121.html|SRFI 121]] generator that generates all the bits of ''i'' starting with bit #0. Note that the generator is infinite. <enscript highlight=scheme> (let ((g (make-bitwise-generator #b110))) (test #f (g)) (test #t (g)) (test #t (g)) (test #f (g))) </enscript> === Implementation The implementation is in the repository of this SRFI, and includes the following files: * {{bitwise-core.scm}} - the SRFI 60 sample implementation of the seven core operators, without dependencies * {{bitwise-33.scm}} - SRFI 33 sample implementation, some procedures renamed * {{bitwise-60.scm}} - part of SRFI 60 sample implementation, some procedures renamed * {{bitwise-other.scm}} - implementation of other procedures * {{srfi-151.scm}} - Chicken module * {{srfi-151.sld}} - R7RS library * {{chibi-test.scm}} - Chibi tests * {{chicken-test.scm}} - Chicken tests 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. <table> <tr><th>Function</th><th>CL</th><th>SRFI 33</th><th>SRFI 33 late revs</th><th>SRFI 60</th><th>R6RS</th><th>This SRFI </th></tr><tr><td>Bitwise NOT</td><td>{{lognot}}</td><td>{{bitwise-not}}</td><td>{{bitwise-not}}</td><td>{{lognot}}, {{bitwise-not}}</td><td>{{bitwise-not}}</td><td>{{bitwise-not}} </td></tr><tr><td>Bitwise AND</td><td>{{logand}}</td><td>{{bitwise-and}}</td><td>{{bitwise-and}}</td><td>{{logand}}, {{bitwise-and}}</td><td>{{bitwise-and}}</td><td>{{bitwise-and}} </td></tr><tr><td>Bitwise IOR</td><td>{{logior}}</td><td>{{bitwise-ior}}</td><td>{{bitwise-ior}}</td><td>{{logior}}, {{bitwise-ior}}</td><td>{{bitwise-ior}}</td><td>{{bitwise-ior}} </td></tr><tr><td>Bitwise XOR</td><td>{{logxor}}</td><td>{{bitwise-xor}}</td><td>{{bitwise-xor}}</td><td>{{logxor}}, {{bitwise-xor}}</td><td>{{bitwise-xor}}</td><td>{{bitwise-xor}} </td></tr><tr><td>Bitwise EQV</td><td>{{logeqv}}</td><td>{{bitwise-eqv}}</td><td>{{bitwise-eqv}}</td><td>---</td><td>---</td><td>{{bitwise-eqv}} </td></tr><tr><td>Bitwise NAND</td><td>{{lognand}}</td><td>{{bitwise-nand}}</td><td>{{bitwise-nand}}</td><td>---</td><td>---</td><td>{{bitwise-nand}} </td></tr><tr><td>Bitwise NOR</td><td>{{lognor}}</td><td>{{bitwise-nor}}</td><td>{{bitwise-nor}}</td><td>---</td><td>---</td><td>{{bitwise-nor}} </td></tr><tr><td>Bitwise AND with NOT of first arg</td><td>{{logandc1}}</td><td>{{bitwise-andc1}}</td><td>{{bitwise-andc1}}</td><td>---</td><td>---</td><td>{{bitwise-andc1}} </td></tr><tr><td>Bitwise AND with NOT of second arg</td><td>{{logandc2}}</td><td>{{bitwise-andc2}}</td><td>{{bitwise-andc2}}</td><td>---</td><td>---</td><td>{{bitwise-andc2}} </td></tr><tr><td>Bitwise OR with NOT of first arg</td><td>{{logorc1}}</td><td>{{bitwise-orc1}}</td><td>{{bitwise-orc1}}</td><td>---</td><td>---</td><td>{{bitwise-orc1}} </td></tr><tr><td>Bitwise OR with NOT of second arg</td><td>{{logorc2}}</td><td>{{bitwise-orc2}}</td><td>{{bitwise-orc2}}</td><td>---</td><td>---</td><td>{{bitwise-orc2}} </td></tr><tr><td>Arithmetic shift</td><td>{{ash}}</td><td>{{arithmetic-shift}}</td><td>{{arithmetic-shift}}</td><td>{{ash}}, {{arithmetic-shift}}</td><td>{{bitwise-arithmetic-shift}}</td><td>{{arithmetic-shift}} </td></tr><tr><td>Population count</td><td>{{logcount}}</td><td>{{bit-count}}</td><td>{{bit-count}}</td><td>{{logcount}}, {{bit-count}}</td><td>{{bitwise-bit-count}}</td><td>{{bit-count}} </td></tr><tr><td>Integer length</td><td>{{integer-length}}</td><td>{{integer-length}}</td><td>{{integer-length}}</td><td>{{integer-length}}</td><td>{{bitwise-length}}</td><td>{{integer-length}} </td></tr><tr><td>Mask selects source of bits</td><td>---</td><td>{{bitwise-merge}}</td><td>{{bitwise-merge}}</td><td>{{bitwise-if}}, {{bitwise-merge}}</td><td>{{bitwise-if}}</td><td>{{bitwise-if}} </td></tr><tr><td>Test single bit</td><td>{{logbitp}}</td><td>{{bit-set?}}</td><td>{{bit-set?}}</td><td>{{logbit?}}, {{bit-set?}}</td><td>{{bitwise-bit-set?}}</td><td>{{bit-set?}} </td></tr><tr><td>See if any mask bits set</td><td>{{logtest}}</td><td>{{any-bits-set?}}</td><td>{{any-bit-set?}}</td><td>{{logtest}}, {{any-bits-set?}}</td><td>---</td><td>{{any-bit-set?}} </td></tr><tr><td>See if all mask bits set</td><td>---</td><td>{{all-bits-set?}}</td><td>{{every-bit-set?}}</td><td>---</td><td>---</td><td>{{every-bit-set?}} </td></tr><tr><td>Replace single bit</td><td>---</td><td>---</td><td>{{copy-bit}}</td><td>{{copy-bit}}</td><td>{{bitwise-copy-bit}}</td><td>{{copy-bit}} </td></tr><tr><td>Swap bits</td><td>---</td><td>---</td><td>---</td><td>---</td><td>---</td><td>{{bit-swap}} </td></tr><tr><td>Find first bit set</td><td>---</td><td>{{first-set-bit}}</td><td>{{first-set-bit}}</td><td>{{log2-binary-factors}}, {{first-set-bit}}</td><td>{{bitwise-first-bit-set}}</td><td>{{first-set-bit}} </td></tr><tr><td>Extract bit field</td><td>''ldb''</td><td>{{extract-bit-field}}</td><td>{{extract-bit-field}}</td><td>{{bit-field}}</td><td>{{bitwise-bit-field}}</td><td>{{bit-field}} </td></tr><tr><td>Test bit field (any)</td><td>{{ldb-test}}</td><td>{{test-bit-field?}}</td><td>{{bit-field-any?}}</td><td>---</td><td>---</td><td>{{bit-field-any?}} </td></tr><tr><td>Test bit field (every)</td><td>---</td><td>---</td><td>{{bit-field-every?}}</td><td>---</td><td>---</td><td>{{bit-field-every?}} </td></tr><tr><td>Clear bit field</td><td>{{mask-field}}</td><td>{{clear-bit-field}}</td><td>{{bit-field-clear}}</td><td>---</td><td>---</td><td>{{bit-field-clear}} </td></tr><tr><td>Set bit field</td><td>---</td><td>---</td><td>---</td><td>---</td><td>---</td><td>{{bit-field-set}} </td></tr><tr><td>Replace bit field</td><td>{{dpb}}</td><td>{{replace-bit-field}}</td><td>{{bit-field-replace}}</td><td>{{copy-bit-field}}</td><td>{{bitwise-copy-bit-field}}</td><td>{{bit-field-replace}} </td></tr><tr><td>Replace corresponding bit field</td><td>{{deposit-field}}</td><td>{{copy-bit-field}}</td><td>{{bit-field-copy}}</td><td>---</td><td>---</td><td>{{bit-field-replace-same}} </td></tr><tr><td>Rotate bit field</td><td>---</td><td>---</td><td>---</td><td>{{rotate-bit-field}}</td><td>{{bitwise-rotate-bit-field}}</td><td>{{bit-field-rotate}} </td></tr><tr><td>Reverse bit field</td><td>---</td><td>---</td><td>---</td><td>{{reverse-bit-field}}</td><td>{{bitwise-reverse-bit-field}}</td><td>{{bit-field-reverse}} </td></tr><tr><td>Bits to boolean list</td><td>---</td><td>---</td><td>---</td><td>{{integer->list}}</td><td>---</td><td>{{bits->list}} </td></tr><tr><td>Bits to boolean vector</td><td>---</td><td>---</td><td>---</td><td>---</td><td>---</td><td>{{bits->vector}} </td></tr><tr><td>Boolean list to bits</td><td>---</td><td>---</td><td>---</td><td>{{list->integer}}</td><td>---</td><td>{{list->bits}} </td></tr><tr><td>Boolean vector to bits</td><td>---</td><td>---</td><td>---</td><td>---</td><td>---</td><td>{{vector->bits}} </td></tr><tr><td>Booleans to integer</td><td>---</td><td>---</td><td>---</td><td>{{booleans->integer}}</td><td>---</td><td>{{bits}} </td></tr><tr><td>Bitwise fold</td><td>---</td><td>---</td><td>---</td><td>---</td><td>---</td><td>{{bitwise-fold}} </td></tr><tr><td>Bitwise for-each</td><td>---</td><td>---</td><td>---</td><td>---</td><td>---</td><td>{{bitwise-for-each}} </td></tr><tr><td>Bitwise unfold</td><td>---</td><td>---</td><td>---</td><td>---</td><td>---</td><td>{{bitwise-unfold}} </td></tr><tr><td>Bit generator</td><td>---</td><td>---</td><td>---</td><td>---</td><td>---</td><td>{{make-bitwise-generator}} </td></tr></table> === Acknowledgements This SRFI would not exist without the efforts of Olin Shivers, Aubrey Jaffer, and Taylor Campbell. === CHICKEN egg version history ==== 1.0.2 * Removed SRFI files which are not needed for the egg (e.g. html markup) ==== 1.0.1 * Changed egg license to MIT ==== 1.0.0 * Initial release of SRFI-151 as a CHICKEN egg === Copyright 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. Description of your changes:

I would like to authenticate

Spam control

What do you get when you add 0 to 19?