Go to the first, previous, next, last section, table of contents.

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.

procedure+: bit-substring-find-next-set-bit bit-string start end
Returns the index of the first occurrence of a set bit in the substring of bit-string from start (inclusive) to end (exclusive). If none of the bits in the substring are set #f is returned. The index returned is relative to the whole bit string, not substring.

The following procedure uses bit-substring-find-next-set-bit to find all the set bits and display their indexes:

(define (scan-bitstring bs)
  (let ((end (bit-string-length bs)))
    (let loop ((start 0))
      (let ((next (bit-substring-find-next-set-bit bs start end)))
	(if next
	    (begin
	      (write-line next)
	      (if (< next end)
		  (loop (+ next 1)))))))))

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 first, previous, next, last section, table of contents.