Go to the previous, next section.

Bit Strings

A bit string is a sequence of bits. Bit strings can be used to represent sets or to manipulate binary data. The elements of a bit string are numbered from zero up to the number of bits in the string less one, in right to left order, (the rightmost bit is numbered zero). When you convert from a bit string to an integer, the zero-th bit is associated with the zero-th power of two, the first bit is associated with the first power, and so on.

Bit strings are encoded very densely in memory. Each bit occupies exactly one bit of storage, and the overhead for the entire bit string is bounded by a small constant. However, accessing a bit in a bit string is slow compared to accessing an element of a vector or character string. If performance is of overriding concern, it is better to use character strings to store sets of boolean values even though they occupy more space.

The length of a bit string is the number of bits that it contains. This number is an exact non-negative integer that is fixed when the bit string is created. The valid indexes of a bit string are the exact non-negative integers less than the length of the bit string.

Bit strings may contain zero or more bits. They are not limited by the length of a machine word. In the printed representation of a bit string, the contents of the bit string are preceded by `#*'. The contents are printed starting with the most significant bit (highest index).

Note that the external representation of bit strings uses a bit ordering that is the reverse of the representation for bit strings in Common Lisp. It is likely that MIT Scheme's representation will be changed in the future, to be compatible with Common Lisp. For the time being this representation should be considered a convenience for viewing bit strings rather than a means of entering them as data.

#*11111
#*1010
#*00000000
#*

All of the bit-string procedures are MIT Scheme extensions.

Construction of Bit Strings

procedure+: make-bit-string k initialization

Returns a newly allocated bit string of length k. If initialization is #f, the bit string is filled with 0 bits; otherwise, the bit string is filled with 1 bits.

(make-bit-string 7 #f)                  =>  #*0000000

procedure+: bit-string-allocate k

Returns a newly allocated bit string of length k, but does not initialize it.

procedure+: bit-string-copy bit-string

Returns a newly allocated copy of bit-string.

Selecting Bit String Components

procedure+: bit-string? object

Returns #t if object is a bit string; otherwise returns #f.

procedure+: bit-string-length bit-string

Returns the length of bit-string.

procedure+: bit-string-ref bit-string k

Returns #t if the kth bit is 1; otherwise returns #f. K must be a valid index of bit-string.

procedure+: bit-string-set! bit-string k

Sets the kth bit in bit-string to 1 and returns an unspecified value. K must be a valid index of bit-string.

procedure+: bit-string-clear! bit-string k

Sets the kth bit in bit-string to 0 and returns an unspecified value. K must be a valid index of bit-string.

Cutting and Pasting Bit Strings

procedure+: bit-string-append bit-string-1 bit-string-2

Appends the two bit string arguments, returning a newly allocated bit string as its result. In the result, the bits copied from bit-string-1 are less significant (smaller indices) than those copied from bit-string-2.

procedure+: bit-substring bit-string start end

Returns a newly allocated bit string whose bits are copied from bit-string, starting at index start (inclusive) and ending at end (exclusive).

Bitwise Operations on Bit Strings

procedure+: bit-string-zero? bit-string

Returns #t if bit-string contains only 0 bits; otherwise returns #f.

procedure+: bit-string=? bit-string-1 bit-string-2

Compares the two bit string arguments and returns #t if they are the same length and contain the same bits; otherwise returns #f.

procedure+: bit-string-not bit-string

Returns a newly allocated bit string that is the bitwise-logical negation of bit-string.

procedure+: bit-string-movec! target-bit-string bit-string

The destructive version of bit-string-not. The arguments target-bit-string and bit-string must be bit strings of the same length. The bitwise-logical negation of bit-string is computed and the result placed in target-bit-string. The value of this procedure is unspecified.

procedure+: bit-string-and bit-string-1 bit-string-2

Returns a newly allocated bit string that is the bitwise-logical "and" of the arguments. The arguments must be bit strings of identical length.

procedure+: bit-string-andc bit-string-1 bit-string-2

Returns a newly allocated bit string that is the bitwise-logical "and" of bit-string-1 with the bitwise-logical negation of bit-string-2. The arguments must be bit strings of identical length.

procedure+: bit-string-or bit-string-1 bit-string-2

Returns a newly allocated bit string that is the bitwise-logical "inclusive or" of the arguments. The arguments must be bit strings of identical length.

procedure+: bit-string-xor bit-string-1 bit-string-2

Returns a newly allocated bit string that is the bitwise-logical "exclusive or" of the arguments. The arguments must be bit strings of identical length.

procedure+: bit-string-and! target-bit-string bit-string

procedure+: bit-string-or! target-bit-string bit-string

procedure+: bit-string-xor! target-bit-string bit-string

procedure+: bit-string-andc! target-bit-string bit-string

These are destructive versions of the above operations. The arguments target-bit-string and bit-string must be bit strings of the same length. Each of these procedures performs the corresponding bitwise-logical operation on its arguments, places the result into target-bit-string, and returns an unspecified result.

Modification of Bit Strings

procedure+: bit-string-fill! bit-string initialization

Fills bit-string with zeroes if initialization is #f; otherwise fills bit-string with ones. Returns an unspecified value.

procedure+: bit-string-move! target-bit-string bit-string

Moves the contents of bit-string into target-bit-string. Both arguments must be bit strings of the same length. The results of the operation are undefined if the arguments are the same bit string.

procedure+: bit-substring-move-right! bit-string-1 start1 end1 bit-string-2 start2

Destructively copies the bits of bit-string-1, starting at index start1 (inclusive) and ending at end1 (exclusive), into bit-string-2 starting at index start2 (inclusive). Start1 and end1 must be valid substring indices for bit-string-1, and start2 must be a valid index for bit-string-2. The length of the source substring must not exceed the length of bit-string-2 minus the index start2.

The bits are copied starting from the MSB and working towards the LSB; the direction of copying only matters when bit-string-1 and bit-string-2 are eqv?.

Integer Conversions of Bit Strings

procedure+: unsigned-integer->bit-string length integer

Both length and integer must be exact non-negative integers. Converts integer into a newly allocated bit string of length bits. Signals an error of type condition-type:bad-range-argument if integer is too large to be represented in length bits.

procedure+: signed-integer->bit-string length integer

Length must be an exact non-negative integer, and integer may be any exact integer. Converts integer into a newly allocated bit string of length bits, using two's complement encoding for negative numbers. Signals an error of type condition-type:bad-range-argument if integer is too large to be represented in length bits.

procedure+: bit-string->unsigned-integer bit-string

procedure+: bit-string->signed-integer bit-string

Converts bit-string into an exact integer. bit-string->signed-integer regards bit-string as a two's complement representation of a signed integer, and produces an integer of like sign and absolute value. bit-string->unsigned-integer regards bit-string as an unsigned quantity and converts to an integer accordingly.

Go to the previous, next section.