Go to the first, previous, next, last section, table of contents.
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.
- 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.
- 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)))))))))
- 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).
- 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.
- 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?.
- 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.