WOLFRAM

Wolfram 语言与系统参考资料中心

"BitVector" （数据结构）

"BitVector"

表示布尔值向量或根据位元数组构建的集合的成员.

更多信息

  • "BitVector" 是一种非常紧凑的数据表示，只能采用两个值，例如布尔数据，也可以是集合的高效表示.
  • 位元的编号与 BitSet 等其他位元运算一致，因此 0 表示第一位.
  • CreateDataStructure[ "BitVector",length]创建新的指定 length 的 "BitVector"
    CreateDataStructure["BitVector",blist]根据含有 True 和 False 的布尔列表 blist 创建新的 "BitVector"
    Typed[x,"BitVector"]设 x 的类型为 "BitVector"
  • 对于类型为 "BitVector" 的数据结构，可进行以下运算：
  • ds["BitAnd",dsi]用按位 And 将 ds 和 dsi 中的位元组合在一起用时: O(n/8)
    ds["BitClear",k]将 ds 中的第 k 个位元设为 0用时：O(1)
    ds["BitClearAll"]将 ds 中的所有位元设为 0用时：O(n)
    ds["BitCount"]返回 ds 中被设为 1 的位元的数量用时：O(n)
    ds["BitGet",k]获取 ds 中的第 k 个位元用时：O(1)
    ds["BitInvert",k]反转 ds 中第 k 个位元的值用时：O(1)
    ds["BitList"]返回 ds 中被设为 1 的位元的列表用时：O(n)
    ds["BitNand",dsi]用逐位 Nand 组合 ds 和 dsi 中的位元用时：O(n/8)
    ds["BitNor",dsi]用逐位 Nor 组合 ds 和 dsi 中的位元用时：O(n/8)
    ds["BitNot",dsi]翻转 ds 中的位元用时：O(n/8)
    ds["BitOr",dsi]用按位 Or 将 ds 和 dsi 中的位元组合在一起用时: O(n/8)
    ds["BitSet",k]将 ds 中的第 k 个位元设为 1用时：O(1)
    ds["BitTest",k]如果 ds 中的第 k 个位元被设为 1 则返回 True，否则设为 False用时：O(1)
    ds["BitXnor",dsi]用逐位 Xnor 组合 ds 和 dsi 中的位元用时：O(n/8)
    ds["BitXor",dsi]用按位 Xor 将 ds 和 dsi 中的位元组合在一起用时: O(n/8)
    ds["Boole"]返回一个数值数组，其中 ds 中的置位位元为 1，其他位元为 0用时：O(n)
    ds["Capacity"]返回可以存储在 ds 中的位元的数量用时：O(1)
    ds["Copy"]返回 ds 的拷贝用时：O(n)
    ds["Length"]返回 ds 中可以存储的位元的数量用时：O(1)
    ds["OffBitList"]返回 ds 中关闭的位元的列表用时：O(n/8)
    ds["OffBitList",dsi]返回在 ds 和 dsi 中皆 Off 的位元的列表用时：O(n/8)
    ds["OnBitList",dsi]返回在 ds 和 dsi 中皆 On 的位元的列表用时: O(n/8)
    ds["Visualization"]返回 ds 的可视化用时：O(n)
  • 还支持以下函数：
  • dsi===dsj如果 dsi 等于 dsj 则为 True
    FullForm[ds]ds 的完全形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换成普通表达式
    Pick[list,ds]提取 ds 中 1 对应的 list 中的元素

范例

打开所有单元 关闭所有单元

基本范例  (3)

可用 CreateDataStructure 创建新的 "BitVector"：

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

将第 20 个位元设为 1：

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

测试一个位元是否被设置为 1：

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

提取位元：

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

反转位元：

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

获取被设为 1 的位元的列表：

Wolfram Language code: ds["BitList"]

返回表达式形式的 ds：

Wolfram Language code: list = Normal[ds]

可用普通列表创建新的 "BitVector"：

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

验证它们是相等的：

Wolfram Language code: ds1 === ds

可视化数据结构：

Wolfram Language code: ds["Visualization"]

测试共有的位元：

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

两者中皆 on 的位元：

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

两者中皆 off 的位元：

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

组合：

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

"BitVector" 只含有两者中皆 on 的位元：

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

范围  (2)

信息  (1)

可用 CreateDataStructure 创建新的 "BitVector"：

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

数据结构 ds 的信息：

Wolfram Language code: Information[ds]

选择  (1)

创建类型为 "BitVector" 且长度为 5 的数据结构：

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

将其第二位和第四位设为 1，注意它是从 0 开始索引的，而不是从 1 开始索引的：

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

用数据结构提取列表的元素：

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

应用  (1)

将 Pick 与由 True 和 False 组成哦列表一起使用：

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

用相应的位向量进行相同的操作要快得多：

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

结果是一样的：

Wolfram Language code: pick === pick2

属性和关系  (3)

"BitVector" 中位的编号与 Power 和位运算（如 BitSet）一致.

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

创建两个位向量：

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

用零初始化两个位向量：

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

用 SameQ 测试相等性：

Wolfram Language code: ds1 === ds2

通过将一个位元设为 1 改变其中一个位向量：

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

两个位向量不再相等：

Wolfram Language code: ds1 === ds2

用 UnsameQ 测试不相等性：

Wolfram Language code: ds1 =!= ds2

创建位向量：

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}]

获取与位元对应的 0/1 值组成的数组：

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

当位元被置位时，数组的值为 1，否则为 0：

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

这相当于对布尔列表应用 Boole：

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