Next: , Previous: Mathematical Packages, Up: Mathematical Packages


5.1 Bit-Twiddling

(require 'logical) or (require 'srfi-60) The bit-twiddling functions are made available through the use of the logical package. logical is loaded by inserting (require 'logical) before the code that uses these functions. These functions behave as though operating on integers in two's-complement representation.

5.1.1 Bitwise Operations

— Function: logand n1 ...
— Function: bitwise-and n1 ...

Returns the integer which is the bit-wise AND of the integer arguments.

Example:

          (number->string (logand #b1100 #b1010) 2)
             ⇒ "1000"
— Function: logior n1 ...
— Function: bitwise-ior n1 ...

Returns the integer which is the bit-wise OR of the integer arguments.

Example:

          (number->string (logior #b1100 #b1010) 2)
             ⇒ "1110"
— Function: logxor n1 ...
— Function: bitwise-xor n1 ...

Returns the integer which is the bit-wise XOR of the integer arguments.

Example:

          (number->string (logxor #b1100 #b1010) 2)
             ⇒ "110"
— Function: lognot n
— Function: bitwise-not n

Returns the integer which is the one's-complement of the integer argument.

Example:

          (number->string (lognot #b10000000) 2)
             ⇒ "-10000001"
          (number->string (lognot #b0) 2)
             ⇒ "-1"
— Function: bitwise-if mask n0 n1
— Function: bitwise-merge mask n0 n1

Returns an integer composed of some bits from integer n0 and some from integer n1. A bit of the result is taken from n0 if the corresponding bit of integer mask is 1 and from n1 if that bit of mask is 0.

— Function: logtest j k
— Function: any-bits-set? j k
          (logtest j k) == (not (zero? (logand j k)))
          
          (logtest #b0100 #b1011) ⇒ #f
          (logtest #b0100 #b0111) ⇒ #t

5.1.2 Integer Properties

— Function: logcount n

Returns the number of bits in integer n. If integer is positive, the 1-bits in its binary representation are counted. If negative, the 0-bits in its two's-complement binary representation are counted. If 0, 0 is returned.

Example:

          (logcount #b10101010)
             ⇒ 4
          (logcount 0)
             ⇒ 0
          (logcount -2)
             ⇒ 1

On discuss@r6rs.org Ben Harris credits Simon Tatham with the idea to have bitwise-bit-count return a negative count for negative inputs. Alan Bawden came up with the succinct invariant.

— Function: bitwise-bit-count n

If n is non-negative, this procedure returns the number of 1 bits in the two's-complement representation of n. Otherwise it returns the result of the following computation:

          (bitwise-not (bitwise-bit-count (bitwise-not n)))
— Function: integer-length n

Returns the number of bits neccessary to represent n.

Example:

          (integer-length #b10101010)
             ⇒ 8
          (integer-length 0)
             ⇒ 0
          (integer-length #b1111)
             ⇒ 4
— Function: log2-binary-factors n
— Function: first-set-bit n

Returns the number of factors of two of integer n. This value is also the bit-index of the least-significant ‘1’ bit in n.

          (require 'printf)
          (do ((idx 0 (+ 1 idx)))
                ((> idx 16))
              (printf "%s(%3d) ==> %-5d %s(%2d) ==> %-5d\n"
                      'log2-binary-factors
                      (- idx) (log2-binary-factors (- idx))
                      'log2-binary-factors
                      idx (log2-binary-factors idx)))
          -|
          log2-binary-factors(  0) ==> -1    log2-binary-factors( 0) ==> -1
          log2-binary-factors( -1) ==> 0     log2-binary-factors( 1) ==> 0
          log2-binary-factors( -2) ==> 1     log2-binary-factors( 2) ==> 1
          log2-binary-factors( -3) ==> 0     log2-binary-factors( 3) ==> 0
          log2-binary-factors( -4) ==> 2     log2-binary-factors( 4) ==> 2
          log2-binary-factors( -5) ==> 0     log2-binary-factors( 5) ==> 0
          log2-binary-factors( -6) ==> 1     log2-binary-factors( 6) ==> 1
          log2-binary-factors( -7) ==> 0     log2-binary-factors( 7) ==> 0
          log2-binary-factors( -8) ==> 3     log2-binary-factors( 8) ==> 3
          log2-binary-factors( -9) ==> 0     log2-binary-factors( 9) ==> 0
          log2-binary-factors(-10) ==> 1     log2-binary-factors(10) ==> 1
          log2-binary-factors(-11) ==> 0     log2-binary-factors(11) ==> 0
          log2-binary-factors(-12) ==> 2     log2-binary-factors(12) ==> 2
          log2-binary-factors(-13) ==> 0     log2-binary-factors(13) ==> 0
          log2-binary-factors(-14) ==> 1     log2-binary-factors(14) ==> 1
          log2-binary-factors(-15) ==> 0     log2-binary-factors(15) ==> 0
          log2-binary-factors(-16) ==> 4     log2-binary-factors(16) ==> 4

5.1.3 Bit Within Word

— Function: logbit? index n
— Function: bit-set? index n
          (logbit? index n) == (logtest (expt 2 index) n)
          
          (logbit? 0 #b1101) ⇒ #t
          (logbit? 1 #b1101) ⇒ #f
          (logbit? 2 #b1101) ⇒ #t
          (logbit? 3 #b1101) ⇒ #t
          (logbit? 4 #b1101) ⇒ #f
— Function: copy-bit index from bit

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

Example:

          (number->string (copy-bit 0 0 #t) 2)       ⇒ "1"
          (number->string (copy-bit 2 0 #t) 2)       ⇒ "100"
          (number->string (copy-bit 2 #b1111 #f) 2)  ⇒ "1011"

5.1.4 Field of Bits

— Function: bit-field n start end

Returns the integer composed of the start (inclusive) through end (exclusive) bits of n. The startth bit becomes the 0-th bit in the result.

Example:

          (number->string (bit-field #b1101101010 0 4) 2)
             ⇒ "1010"
          (number->string (bit-field #b1101101010 4 9) 2)
             ⇒ "10110"
— Function: copy-bit-field to from start end

Returns an integer the same as to except possibly in the start (inclusive) through end (exclusive) bits, which are the same as those of from. The 0-th bit of from becomes the startth bit of the result.

Example:

          (number->string (copy-bit-field #b1101101010 0 0 4) 2)
                  ⇒ "1101100000"
          (number->string (copy-bit-field #b1101101010 -1 0 4) 2)
                  ⇒ "1101101111"
          (number->string (copy-bit-field #b110100100010000 -1 5 9) 2)
                  ⇒ "110100111110000"
— Function: ash n count
— Function: arithmetic-shift n count

Returns an integer equivalent to (inexact->exact (floor (* n (expt 2 count)))).

Example:

          (number->string (ash #b1 3) 2)
             ⇒ "1000"
          (number->string (ash #b1010 -1) 2)
             ⇒ "101"
— Function: rotate-bit-field n count start end

Returns n with the bit-field from start to end cyclically permuted by count bits towards high-order.

Example:

          (number->string (rotate-bit-field #b0100 3 0 4) 2)
              ⇒ "10"
          (number->string (rotate-bit-field #b0100 -1 0 4) 2)
              ⇒ "10"
          (number->string (rotate-bit-field #b110100100010000 -1 5 9) 2)
              ⇒ "110100010010000"
          (number->string (rotate-bit-field #b110100100010000 1 5 9) 2)
              ⇒ "110100000110000"
— Function: reverse-bit-field n start end

Returns n with the order of bits start to end reversed.

          (number->string (reverse-bit-field #xa7 0 8) 16)
            ⇒ "e5"

5.1.5 Bits as Booleans

— Function: integer->list k len
— Function: integer->list k

integer->list returns a list of len booleans corresponding to each bit of the non-negative integer k. #t is coded for each 1; #f for 0. The len argument defaults to (integer-length k).

— Function: list->integer list

list->integer returns an integer formed from the booleans in the list list, which must be a list of booleans. A 1 bit is coded for each #t; a 0 bit for #f.

          (list->integer (integer->list k))  ⇒  k
— Function: booleans->integer bool1 ...

Returns the integer coded by the bool1 ... arguments.