---

4.7 Bit operations

This section describes operations on exact integers as strings of bits in two’s-complement representation. All arguments must be exact integers.

procedure: bitwise-not x ¶

Bitwise complement. Equivalent to (- -1 x).

procedure: bitwise-and x1 x2 … ¶

procedure: bitwise-andc2 x1 x2 ¶

procedure: bitwise-andc1 x1 x2 ¶

procedure: bitwise-xor x1 x2 … ¶

procedure: bitwise-ior x1 x2 … ¶

procedure: bitwise-nor x1 x2 ¶

procedure: bitwise-eqv x1 x2 … ¶

procedure: bitwise-orc2 x1 x2 ¶

procedure: bitwise-orc1 x1 x2 ¶

procedure: bitwise-nand x1 x2 ¶

Bitwise operations. The ‘c1’/‘c2’ variants take the complement of their first or second operand, respectively; for example, (bitwise-andc2 x1 x2) is equivalent to (bitwise-and x1 (bitwise-not x2)).

The four bitwise operations that are associative are extended to arbitrary numbers of arguments with an appropriate identity:

(bitwise-and)           ⇒ -1
(bitwise-xor)           ⇒ 0
(bitwise-ior)           ⇒ 0
(bitwise-eqv)           ⇒ -1

procedure: shift-left x n ¶

procedure: shift-right x n ¶

procedure: arithmetic-shift x n ¶

Multiplication and integer division by 2^n: (shift-left x n) is equivalent to (* x (expt 2 n)), and (shift-left x n) is equivalent to (euclidean-quotient x (expt 2 n)).

Shift-left and shift-right require n to be nonnegative; arithmetic-shift is equivalent to shift-left for positive n, and equivalent to shift-right for the negation of negative n.

procedure: bit-mask size position ¶

Returns an integer with size consecutive bits set starting at position, zero-based, and all other bits clear. Both arguments must be nonnegative.

(bit-mask 0 123)        ⇒ 0
(bit-mask 4 3)          ⇒ #b1111000

procedure: bit-antimask size position ¶

Returns an integer with size consecutive bits clear starting at position, zero-based, and all other bits set. Both arguments must be nonnegative. Equivalent to (bitwise-not (bit-mask size position)).

(bit-antimask 0 123)    ⇒ -1
(bit-antimask 4 3)      ⇒ #b-1111001  ; ‘#b...10000111’

procedure: bit-count x ¶

Returns the number of 1 bits in x, if it is nonnegative, or the number of 0 bits, if it is negative. Sometimes known as ‘pop count’ or ‘population count’.

procedure: hamming-distance x y ¶

Returns the Hamming distance between x and y—that is, the number of bits that differ in corresponding positions of their finite representations, or -1 if they have opposite signs (meaning that they differ in an infinite number of positions). Equivalent to (bit-count (bitwise-xor x y)).

(hamming-distance 1 3)          ⇒ 1
(hamming-distance 7 8)          ⇒ 4
(hamming-distance -8 -9)        ⇒ 4
(hamming-distance 1 -1)         ⇒ -1

procedure: integer-length x ¶

Returns the number of bit positions needed to represent x in two’s-complement: zero when x is zero; the exact value of (ceiling (/ (log x) (log 2))) when x is positive; (integer-length (bitwise-not x)) when x is negative.

(integer-length -129)           ⇒ 9
(integer-length -128)           ⇒ 8
(integer-length -127)           ⇒ 7
(integer-length -1)             ⇒ 0
(integer-length 0)              ⇒ 0
(integer-length 1)              ⇒ 1
(integer-length 127)            ⇒ 7
(integer-length 128)            ⇒ 8

procedure: first-set-bit x ¶

Returns the zero-based position of the first set bit in x. For zero, returns -1.

procedure: set-bit n x ¶

procedure: clear-bit n x ¶

procedure: toggle-bit n x ¶

procedure: extract-bit n x ¶

procedure: bit-set? n x ¶

procedure: bit-clear? n x ¶

Set-bit returns the integer x with the bit at position n set. Clear-bit returns the integer x with the bit at position n clear. Toggle-bit returns the integer x with the bit at position n in the opposite state.

Extract-bit returns the bit at position n in x as an integer, 0 or 1. Bit-set? returns true if that bit is set, false if clear. Bit-clear? returns false if that bit is set, true if clear.

procedure: bit n ¶

procedure: bits n m ¶

(bit n) returns a mask with the nth bit set and all other bits clear. (bits n m) returns a mask with bits n through m set, inclusive and zero-based, and all other bits clear. n and m may occur in either order.

(bit 7)                 ⇒ 128
(bits 4 5)              ⇒ #b110000
(bits 5 4)              ⇒ #b110000

procedure: shiftout x mask ¶

procedure: shiftin x mask ¶

mask must be a nonnegative integer with a contiguous substring of bits set, representing a contiguous field of bits.

(shiftout x mask) returns the corresponding value of that field in x; that is, (bitwise-and (shift-right x n) mask), where n is the position of the first set bit in mask.

(shiftin x mask) returns an an integer with that field set to x; that is, (shift-left x n).

Intended to be used with bit and bits. For example:

(define foo:x (bits 0 3))
(define foo:y (bits 4 5))
(define foo:z (bits 6 7))

(define (make-foo x y z)
  (bitwise-ior (shiftin x foo:x)
               (shiftin y foo:y)
               (shiftin z foo:z)))

(define (foo-x foo) (shiftout foo foo:x))
(define (foo-y foo) (shiftout foo foo:y))
(define (foo-z foo) (shiftout foo foo:z))

(make-foo 1 2 3)                ⇒ #b11100001
(foo-z (make-foo 1 2 3))        ⇒ 3