Next: , Previous: , Up: Numbers   [Contents][Index]

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

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
```

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
```

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
```

Next: Fixnum and Flonum Operations, Previous: Numerical input and output, Up: Numbers   [Contents][Index]