package bitv

  1. Overview
  2. Docs
A bit vector library

Install 

dune-project
 Dependency

github.com Readme Changelog Edit opam file Versions (6)

Authors

  1. J
    Jean-Christophe Filliâtre

Maintainers

  1. J
    Jean-Christophe.Filliatre@cnrs.fr

Sources

2.1.tar.gz
md5=03cac56cec6a26321bad06e519cc3847
sha512=ae52e352b35486d7f990dbabcb3a0a78201cfb8f16c7273dbc520bb59f326c3aaedd64fd0ad84a99b686089329ad7f0a9a84e87ba766dafa3431883202ecc087

doc/bitv/Bitv/index.html

Module BitvSource

This module implements bit vectors, as an abstract datatype t. Since bit vectors are particular cases of arrays, this module provides the same operations as module Array. It also provides bitwise operations and conversions to/from integer types.

In the following, false stands for bit 0 and true for bit 1.

Sourcetype t

the type of bit vectors

Creation, access and assignment.

Sourceval create : int -> bool -> t

(Bitv.create n b) creates a new bit vector of length n, initialized with b.

Sourceval init : int -> (int -> bool) -> t

(Bitv.init n f) returns a fresh vector of length n, with bit number i initialized to the result of (f i).

Sourceval random : int -> t

Bitv.random n returns a fresh vector of length n with random bits. This is equivalent to Bitv.init n (fun _ -> Random.bool ()), but much faster.

Sourceval set : t -> int -> bool -> unit

(Bitv.set v n b) sets the nth bit of v to the value b.

Sourceval get : t -> int -> bool

(Bitv.get v n) returns the nth bit of v.

Sourceval length : t -> int

Bitv.length returns the length (number of elements) of the given vector.

Sourceval equal : t -> t -> bool

Returns true if two bit vectors are of the same length and with the same bits.

Sourceval tanimoto : t -> t -> float

Bitv.tanimoto v1 v2 is |inter(v1,v2)| / |union(v1,v2)|. Also called the Jaccard score. (1 - tanimoto) is a proper distance. raises Invalid_argument if the two vectors do not have the same length

Sourceval max_length : int

This is typically Sys.max_string_length * 8 but may be smaller on small platform (e.g. Javascript).

Sourceval exceeds_max_length : int -> bool

Returns true if the argument exceeds the maximum length of a bit vector (System dependent).

Copies and concatenations.

Sourceval copy : t -> t

(Bitv.copy v) returns a copy of v, that is, a fresh vector containing the same elements as v.

Sourceval append : t -> t -> t

(Bitv.append v1 v2) returns a fresh vector containing the concatenation of the vectors v1 and v2.

Sourceval concat : t list -> t

Bitv.concat is similar to Bitv.append, but catenates a list of vectors.

Sub-vectors and filling.

Sourceval sub : t -> int -> int -> t

(Bitv.sub v start len) returns a fresh vector of length len, containing the bits number start to start + len - 1 of vector v. Raise Invalid_argument "Bitv.sub" if start and len do not designate a valid subvector of v; that is, if start < 0, or len < 0, or start + len > Bitv.length a.

Sourceval fill : t -> int -> int -> bool -> unit

(Bitv.fill v ofs len b) modifies the vector v in place, storing b in elements number ofs to ofs + len - 1. Raise Invalid_argument "Bitv.fill" if ofs and len do not designate a valid subvector of v.

Sourceval blit : t -> int -> t -> int -> int -> unit

(Bitv.blit v1 o1 v2 o2 len) copies len elements from vector v1, starting at element number o1, to vector v2, starting at element number o2. It does not work correctly if v1 and v2 are the same vector with the source and destination chunks overlapping. Raise Invalid_argument "Bitv.blit" if o1 and len do not designate a valid subvector of v1, or if o2 and len do not designate a valid subvector of v2.

Iterators

Sourceval iter : (bool -> unit) -> t -> unit

(Bitv.iter f v) applies function f in turn to all the elements of v.

Sourceval map : (bool -> bool) -> t -> t

Given a function f, (Bitv.map f v) applies f to all the elements of v, and builds a vector with the results returned by f.

Sourceval iteri : (int -> bool -> unit) -> t -> unit
Sourceval mapi : (int -> bool -> bool) -> t -> t

Bitv.iteri and Bitv.mapi are similar to Bitv.iter and Bitv.map respectively, but the function is applied to the index of the element as first argument, and the element itself as second argument.

Sourceval fold_left : ('a -> bool -> 'a) -> 'a -> t -> 'a

(Bitv.fold_left f x v) computes f (... (f (f x (get v 0)) (get v 1)) ...) (get v (n-1)), where n is the length of the vector v.

Sourceval fold_right : (bool -> 'a -> 'a) -> t -> 'a -> 'a

(Bitv.fold_right f a x) computes f (get v 0) (f (get v 1) ( ... (f (get v (n-1)) x) ...)), where n is the length of the vector v.

Sourceval foldi_left : ('a -> int -> bool -> 'a) -> 'a -> t -> 'a
Sourceval foldi_right : (int -> bool -> 'a -> 'a) -> t -> 'a -> 'a

Pop count and other iterations

Sourceval pop : t -> int

Population count, i.e., number of 1 bits

Sourceval iteri_true : (int -> unit) -> t -> unit

iteri_true f v applies function f in turn to all indexes of the elements of v which are set (i.e. true); indexes are visited from least significant to most significant.

Sourceval gray_iter : (t -> unit) -> int -> unit

gray_iter f n iterates function f on all bit vectors of length n, once each, using a Gray code. The order in which bit vectors are processed is unspecified.

Bitwise operations.

All the bitwise operations return fresh vectors.

Sourceval bw_and : t -> t -> t

bitwise AND; raises Invalid_argument if the two vectors do not have the same length

Sourceval bw_or : t -> t -> t

bitwise OR; raises Invalid_argument if the two vectors do not have the same length

Sourceval bw_xor : t -> t -> t

bitwise XOR; raises Invalid_argument if the two vectors do not have the same length

Sourceval bw_not : t -> t

bitwise NOT

Sourceval shiftl : t -> int -> t

moves bits from least to most significant; introduces zeros

Sourceval shiftr : t -> int -> t

moves bits from most to least significant; introduces zeros

Sourceval rotatel : t -> int -> t

moves bits from least to most significant with wraparound

Sourceval rotater : t -> int -> t

moves bits from most to least significant with wraparound

Bitwise in place operations.

This part of the API extends some bitwise operations by making them operate in place, that is mutating a destination bit vector supplied as a labeled argument dst, rather than returning a fresh one.

These in place operations support being called with dst being one of the operands supplied to the function call.

For example bw_and_in_place ~dst:a a b will store in a the result of the operation bw_and a b.

Sourceval bw_and_in_place : dst:t -> t -> t -> unit

bitwise AND in place into dst; raises Invalid_argument if the three vectors do not have the same length

Sourceval bw_or_in_place : dst:t -> t -> t -> unit

bitwise OR in place into dst; raises Invalid_argument if the three vectors do not have the same length

Sourceval bw_xor_in_place : dst:t -> t -> t -> unit

bitwise XOR in place into dst; raises Invalid_argument if the three vectors do not have the same length

Sourceval bw_not_in_place : dst:t -> t -> unit

bitwise NOT in place into dst; raises Invalid_argument if the two vectors do not have the same length

Test functions

Sourceval all_zeros : t -> bool

returns true if and only if the vector only contains zeros

Sourceval all_ones : t -> bool

returns true if and only if the vector only contains ones

Conversions to and from strings

Sourcemodule L : sig ... end

With least significant bits first.

Sourcemodule M : sig ... end

With most significant bits first.

Input/output in a machine-independent format

The following functions export/import a bit vector to/from a channel or bytes, in a way that is compact, independent of the machine architecture, and independent of the OCaml version. For a bit vector of length n, the number of bytes of this external representation is 8+ceil(n/8).

Sourceval output_bin : out_channel -> t -> unit
Sourceval input_bin : in_channel -> t
Sourceval to_bytes : t -> bytes
Sourceval of_bytes : bytes -> t

Conversions to and from lists of integers

The list gives the indices of bits which are set (i.e. true).

Sourceval to_list : t -> int list
Sourceval of_list : int list -> t
Sourceval of_list_with_length : int list -> int -> t

Interpretation of bit vectors as integers

Least significant bit comes first (ie is at index 0 in the bit vector). to_xxx functions truncate when the bit vector is too wide. Suffix _s means that sign bit is kept, and _us that it is discarded.

type int (length 31/63 with sign, 30/62 without)

Sourceval of_int_s : int -> t
Sourceval to_int_s : t -> int
Sourceval of_int_us : int -> t
Sourceval to_int_us : t -> int

type Int32.t (length 32 with sign, 31 without)

Sourceval of_int32_s : Int32.t -> t
Sourceval to_int32_s : t -> Int32.t
Sourceval of_int32_us : Int32.t -> t
Sourceval to_int32_us : t -> Int32.t

type Int64.t (length 64 with sign, 63 without)

Sourceval of_int64_s : Int64.t -> t
Sourceval to_int64_s : t -> Int64.t
Sourceval of_int64_us : Int64.t -> t
Sourceval to_int64_us : t -> Int64.t

type Nativeint.t (length 32/64 with sign, 31/63 without)

Sourceval of_nativeint_s : Nativeint.t -> t
Sourceval to_nativeint_s : t -> Nativeint.t
Sourceval of_nativeint_us : Nativeint.t -> t
Sourceval to_nativeint_us : t -> Nativeint.t

Only if you know what you are doing...

Sourceval unsafe_set : t -> int -> bool -> unit
Sourceval unsafe_get : t -> int -> bool