Z3 的位向量中所有位的总和

Question

给定 Z3 中的一个位向量，我想知道如何总结这个向量的每个位？

例如，

a = BitVecVal(3, 2)
sum_all_bit(a) = 2

有没有预先实现的 APIs/functions 支持这个？谢谢！

Answer 1

它不是位向量运算的一部分。您可以创建如下表达式：

def sub(b):
    n = b.size()
    bits = [ Extract(i, i, b) for i in range(n) ]
    bvs  = [ Concat(BitVecVal(0, n - 1), b) for b in bits ]
    nb   = reduce(lambda a, b: a + b, bvs)
    return nb


print sub(BitVecVal(4,7))

当然，如果您愿意，结果的 log(n) 位就足够了。

Answer 2

页面：

https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

有多种计算位数的算法；我想这可以相对容易地翻译成 Z3/Python。

我最喜欢的是：https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

它有很好的属性循环次数与输入中的设置位一样多。（但是你不应该从中推断出任何有意义的复杂度指标，因为你在每个循环中进行算术运算，这可能代价高昂。所有这些算法都是如此。）

话虽如此，如果您的输入是完全符号化的，您就无法真正击败简单的迭代算法，因为您无法缩短迭代次数。如果输入有具体位，上述方法可能会工作得更快。

Answer 3

因此，您正在计算位向量的汉明权重。根据我之前的一个问题，其中一位开发人员有 this answer。根据原来的答案，我今天是这样做的：

def HW(bvec):
    return Sum([ ZeroExt(int(ceil(log2(bvec.size()))), Extract(i,i,bvec)) for i in range(bvec.size())])

Z3 的位向量中所有位的总和

Sum of all the bits in a Bit Vector of Z3

z3

z3py