WOLFRAM

Wolfram Language & System Documentation Center

"BitVector" (Data Structure)

"BitVector"

represents a vector of Boolean values or members of a set built from an array of bits.

Details

  • A "BitVector" is a very compact representation of data that can only take on two values, such as Boolean data, and can also be an efficient representation of sets.
  • The numbering of bits is consistent with other bit operations such as BitSet, so that 0 refers to the first bit.
  • CreateDataStructure[ "BitVector",length]create a new "BitVector" of specified length
    CreateDataStructure["BitVector",blist]create a new "BitVector" from a Boolean list blist with True and False elements
    Typed[x,"BitVector"]give x the type "BitVector"
  • For a data structure of type "BitVector", the following operations can be used:
  • ds["BitAnd",dsi]combine the bits in ds and dsi using bitwise Andtime: O(n/8)
    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["BitNand",dsi]combine the bits in ds and dsi using bitwise Nandtime: O(n/8)
    ds["BitNor",dsi]combine the bits in ds and dsi using bitwise Nortime: O(n/8)
    ds["BitNot",dsi]toggle the bits in dstime: O(n/8)
    ds["BitOr",dsi]combine the bits in ds and dsi using bitwise Ortime: O(n/8)
    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["BitXnor",dsi]combine the bits in ds and dsi using bitwise Xnortime: O(n/8)
    ds["BitXor",dsi]combine the bits in ds and dsi using bitwise Xortime: O(n/8)
    ds["Boole"]return a numeric array with ones for the set bits in ds and zeroes elsewhere.time: O(n)
    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["Length"]return the number of bits that can be stored in dstime: O(1)
    ds["OffBitList"]return a list of the bits that are off in dstime: O(n/8)
    ds["OffBitList",dsi]return a list of the bits that are off in both ds and dsitime: O(n/8)
    ds["OnBitList",dsi]return a list of the bits that are on in both ds and dsitime: O(n/8)
    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
    Pick[list,ds]extract the elements of list corresponding to 1 in ds

Examples

open all close all

Basic Examples  (3)

A new "BitVector" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["BitVector", 64]

Set the 20th bit to 1:

Wolfram Language code: ds["BitSet", 20]

It is possible to test if a bit is set:

Wolfram Language code: ds["BitTest", 20]
Wolfram Language code: ds["BitTest", 21]

Extract a bit:

Wolfram Language code: ds["BitGet", 21]

Invert a bit:

Wolfram Language code: ds["BitInvert", 21]

Get a list of the bits that are set:

Wolfram Language code: ds["BitList"]

Return an expression version of ds:

Wolfram Language code: list = Normal[ds]

The normal list can be used to create a new "BitVector" :

Wolfram Language code: ds1 = CreateDataStructure["BitVector", list]

Verify that they are equal:

Wolfram Language code: ds1 === ds

A visualization of the data structure can be generated:

Wolfram Language code: ds["Visualization"]

Testing for common bits:

Wolfram Language code: ds = CreateDataStructure["BitVector", 8]; ds["BitSet", 2];ds["BitSet", 4]; ds1 = CreateDataStructure["BitVector", 8]; ds1["BitSet", 2];ds1["BitSet", 5];

The bits that are on in both:

Wolfram Language code: ds["OnBitList", ds1]

The bits that are off in both:

Wolfram Language code: ds["OffBitList", ds1]

Combining:

Wolfram Language code: ds = CreateDataStructure["BitVector", 8]; ds["BitSet", 2];ds["BitSet", 4]; ds1 = CreateDataStructure["BitVector", 8]; ds1["BitSet", 2];ds1["BitSet", 5];

The "BitVector" only contains bits that were on in both:

Wolfram Language code: ds["BitAnd", ds1]; ds["BitList"]

Scope  (2)

Information  (1)

A new "BitVector" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["BitVector", 64]

Information about the data structure ds:

Wolfram Language code: Information[ds]

Pick  (1)

Create a data structure of type "BitVector" and length 5:

Wolfram Language code: ds = CreateDataStructure["BitVector", 5];

Set its second and fourth bits to 1, cognizant of the fact that it is 0-indexed rather than 1-indexed:

Wolfram Language code: ds["BitSet", 1]; ds["BitSet", 3]

Extract those elements of a list using the data structure:

Wolfram Language code: Pick[{a, b, c, d, e}, ds]

Applications  (1)

Use Pick with a normal list of True and False:

Wolfram Language code: selector = RandomChoice[{True, False}, 10 ^ 7]; data = Range[10 ^ 7]; AbsoluteTiming[pick = Pick[data, selector];]

The same operation using the corresponding bit vector is much faster:

Wolfram Language code: ds = CreateDataStructure["BitVector", selector]; AbsoluteTiming[pick2 = Pick[data, ds];]

The results are the same:

Wolfram Language code: pick === pick2

Properties & Relations  (3)

The numbering for bits in a "BitVector" is consistent with Power and bit operations such as BitSet.

Wolfram Language code: ds = CreateDataStructure["BitVector", 8]; ds["BitSet", 1]; Normal[ds]
Wolfram Language code: 2^1
Wolfram Language code: BitSet[0, 1]

Create two bit vectors:

Wolfram Language code: ds1 = CreateDataStructure["BitVector", 32]; ds2 = CreateDataStructure["BitVector", 32];

Both bit vectors are initialized with zeros:

Wolfram Language code: ds1["Visualization"]
Wolfram Language code: ds2["Visualization"]

Equality can be tested with SameQ:

Wolfram Language code: ds1 === ds2

Change one of the bit vectors by setting a bit:

Wolfram Language code: ds1["BitSet", 1]

The bit vectors are no longer the same:

Wolfram Language code: ds1 === ds2

Inequality can be tested with UnsameQ:

Wolfram Language code: ds1 =!= ds2

Create a bit vector:

Wolfram Language code: ds = CreateDataStructure["BitVector", {True, False, True, True, False, False, True, False}]
Wolfram Language code: DataStructure["BitVector", {"Data" -> ByteArray["TQ=="], "ElementSize" -> 8, "Capacity" -> 8}]

Get an array of zero/one values corresponding to the bits:

Wolfram Language code: bar = ds["Boole"]

When the bit is set, the array value is one, otherwise zero:

Wolfram Language code: TableForm[{Normal[ds], Normal[bar]}]

This is equivalent to Boole applied to the Boolean list:

Wolfram Language code: Boole[Normal[ds]] == bar