"BitVector" (Data Structure)

"BitVector"

represents a set built from an array of bits.

Details

  • Typically, the bits stored are generated from integers, so this is useful for representing sets of integers:
  • CreateDataStructure[ "BitVector",capacity]create a new "BitVector" of specified capacity
    Typed[x,"BitVector"]give x the type "BitVector"
  • For a data structure of type "BitVector", the following operations can be used:
  • ds["BitClear",k]set the kth bit in ds to 0time: O(1)
    ds["BitClearAll"]set all the bits in ds to 0time: O(n)
    ds["BitCount"]return the number of bits in ds that are set to 1time: O(n)
    ds["BitGet",k]get the kth bit in dstime: O(1)
    ds["BitInvert",k]invert the value of the kth bit of dstime: O(1)
    ds["BitList"]return a list of bits that are set to 1 in dstime: O(n)
    ds["BitSet",k]set the kth bit in ds to 1time: O(1)
    ds["BitTest",k]return True if the kth bit of ds is set to 1 and False otherwisetime: O(1)
    ds["Capacity"]return the number of bits that can be stored in dstime: O(1)
    ds["Copy"]return a copy of dstime: O(n)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    FullForm[ds]full form of ds
    Information[ds]information about ds
    InputForm[ds]input form of ds
    Normal[ds]convert ds to a normal expression

Examples

open allclose all

Basic Examples  (1)

A new "BitVector" can be created with CreateDataStructure:

Set the 20th bit to 1:

It is possible to test if a bit is set:

Extract a bit:

Invert a bit:

Get a list of the bits that are set:

Return an expression version of ds:

A visualization of the data structure can be generated:

Scope  (1)

Information  (1)

A new "BitVector" can be created with CreateDataStructure:

Information about the data structure ds:

Properties & Relations  (1)

Create two bit vectors:

Both bit vectors are initialized with zeros:

Equality can be tested with SameQ:

Change one of the bit vectors by setting a bit:

The bit vectors are no longer the same:

Inequality can be tested with UnsameQ:

Introduced in 2020
 (12.1)