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`k`th bit is 1; otherwise returns`#f`

.`K`must be a valid index of`bit-string`.

__procedure+:__**bit-string-set!***bit-string k*-
Sets the
`k`th 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
`k`th 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.

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