# SML/NJ Library Manual

## The `BitVector` structure

#### Synopsis

> `signature `BIT_VECTOR`
> structure `BitVector` : BIT_VECTOR
> `

The BitVector structure provides compacted vectors of booleans, with one bit for each boolean value. A 0 (1) bit corresponds to the boolean value `false` (`true`), respectively. These vectors can be used to implement sets of integers. Member testing takes constant time.

#### Interface

> `include MONO_VECTOR
> where type elem = bool
> val fromString : string -> vector
> val bits : (int * int list) -> vector
> val getBits : vector -> int list
> val toString : vector -> string
> val isZero : vector -> bool
> val extend0 : (vector * int) -> vector
> val extend1 : (vector * int) -> vector
> val eqBits : (vector * vector) -> bool
> val equal : (vector * vector) -> bool
> val andb : (vector * vector * int) -> vector
> val orb : (vector * vector * int) -> vector
> val xorb : (vector * vector * int) -> vector
> val notb : vector -> vector
> val lshift : (vector * int) -> vector
> val rshift : (vector * int) -> vector
> `

#### Description

`fromString s`
  creates a vector from the string argument s, which should contain a hexadecimal representation of the bits set in the vector. Characters 0-9, a-f and A-F are allowed. For example, `fromString "1af8" = 0001101011111000`. (By convention, 0 corresponds to `false` and 1 corresponds to `true`, bit 0 appears on the right, and indices increase to the left.) The length of the vector will be `4*(size s)`. Raises Fail if a non-hexadecimal character appears in the string.
`bits (sz, l)`
  creates a vector of length sz with the indices of its set bits given by l. Raises Subscript if a list item is less than 0, or greater than or equal to sz.
`getBits vec`
  returns a list of indices of the bits set in vec, in increasing order.
`toString vec`
  encodes a bit vector as a string. The bit vector is zero-padded to the next length that is a multiple of 4.
`isZero vec`
  returns true if and only if no bits are set.
`extend0 (vec, len)`
`extend1 (vec, len)`
  create a new vectors by extending the argument bit vector by 0's or 1's to given length. If vec is already as long as len, return a copy of the bit vector. Raises Size if len is negative.
`eqBits (vec, vec2)`
  returns true if the set bits in the two vectors are the same. This is equivalent to:

                  getBits vec = getBits vec2

`equal (vec, vec2)`
  returns true if the two vectors are equivalent, i.e., have the same length and set bits.
`andb (vec, vec2, len)`
`orb (vec, vec2, len)`
`xorb (vec, vec2, len)`
  creates a new vector of length len by logically combining the bits of vec and vec2 using and, or and xor, respectively. If necessary, the vectors are implicitly extended by 0 to be the same length as the new array.
`notb vec`
  creates a new vector with all bits of original vector inverted.
`lshift (vec, i)`
  creates a new vector by inserting n 0's on the right of vec. The new vector has length n + `length` vec. Raises Fail if n is negative.
`rshift (vec, i)`
  creates a new vector of length max(0,`length` vec - n) consisting of bits n,n+1,...,`length` vec - 1 of vec. If n >= `length` vec, the new vector has length 0.

#### See Also

> BitArray, MONO_VECTOR

[ Top | Parent | Contents | Index | Root ]

Last Modified June 9, 1998
Comments to John Reppy
Copyright © 1998 Bell Labs, Lucent Technologies