使用 SMT 2 输入格式计算 Z3 中 BitVec 中的个数

Question

是否有一种紧凑的方法来计算使用 SMT 2 输入格式在 Z3 中的 BitVec 中设置为 1 的位数？

这个问题的公认答案：显示了一种使用 Python.

的方法

Answer 1

目前确实没有简单的方法可以直接在 SMTLib 中执行此操作 being.The 您真正能做的最好的事情就是为每个位向量大小自己滚动；相当丑陋，但易于生成代码：

(set-logic QF_BV)
(set-option :produce-models true)

(define-fun popCount8 ((x (_ BitVec 8))) (_ BitVec 8)
                      (bvadd (ite (= #b1 ((_ extract 0 0) x)) #x01 #x00)
                             (ite (= #b1 ((_ extract 1 1) x)) #x01 #x00)
                             (ite (= #b1 ((_ extract 2 2) x)) #x01 #x00)
                             (ite (= #b1 ((_ extract 3 3) x)) #x01 #x00)
                             (ite (= #b1 ((_ extract 4 4) x)) #x01 #x00)
                             (ite (= #b1 ((_ extract 5 5) x)) #x01 #x00)
                             (ite (= #b1 ((_ extract 6 6) x)) #x01 #x00)
                             (ite (= #b1 ((_ extract 7 7) x)) #x01 #x00)))


; test
(define-fun x () (_ BitVec 8) #xAB)
(declare-fun result () (_ BitVec 8))
(assert (= result (popCount8 x)))
(check-sat)
; Should be 5!
(get-value (result))

这会打印：

sat
((result #x05))

使用递归

SMTLib 标准的最新版本允许使用递归函数来执行此操作"programmatically,"，但是当涉及递归函数时，求解器支持仍然相当粗略。以下适用于 z3，但其他求解器可能效果不佳。有了这个警告，这里有一种使用递归的奇特方法：

(set-logic BV)
(set-option :produce-models true)

(define-fun-rec popCount8_rec ((x (_ BitVec 8)) (i (_ BitVec 8)) (accum (_ BitVec 8))) (_ BitVec 8)
    (ite (= i #x08)
         accum
         (popCount8_rec (bvshl x #x01)
                        (bvadd i #x01)
                        (bvadd accum (ite (= #b1 ((_ extract 7 7) x)) #x01 #x00)))))

(define-fun popCount8 ((x (_ BitVec 8))) (_ BitVec 8) (popCount8_rec x #x00 #x00))

; test
(define-fun x () (_ BitVec 8) #xAB)
(declare-fun result () (_ BitVec 8))
(assert (= result (popCount8 x)))
(check-sat)
; Should be 5!
(get-value (result))

这还会打印：

sat
((result #x05))

参数多态性

请注意，无论选择哪种方法，都必须在popCountN中为每个尺寸N编写一个单独的函数。 SMTLib 不允许用户定义适用于 "parametric" 类型的函数。这是逻辑的基本限制，也是许多人更喜欢从高级语言编写 SMT 求解器脚本以避免此类样板代码的主要原因之一（虽然绝对不是唯一的！）。

一个Python技巧

最好的办法是按照上面的概述展开您自己的版本。在 Z3 中使用的一个常见技巧是您可以使用您链接的 Python 程序和 print s.sexpr() 在某些时候查看生成器生成的内容。然后，您可以根据需要将其剪切粘贴到 SMTLib 中；当然要注意常见的剪切和粘贴错误。

使用 SMT 2 输入格式计算 Z3 中 BitVec 中的个数

Count ones in BitVec in Z3 with SMT 2 input format

z3

使用递归

参数多态性

一个Python技巧