### 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.