python - Finding BitVec weight efficently (aka access to bits of a bitvector) in z3 -

python - Finding BitVec weight efficently (aka access to bits of a bitvector) in z3 -

i'm computing weight of bitvectors using python api z3.

after searching through python api more straight forwards method, i'm implementing weight function bitvector st1 in next manner:

sum([( (st1 & (2**(i)))/(2**(i)) ) in range(bits)])

my question relatively straight-forward, there easier/more efficient way?

i have problems contain 1500+ of these weight constraints , create sure i'm doing things efficiently possible.

edit: i'll add together next clarification, i'm attempting calculate has name (it's hamming weight), know there ultra efficient ways of implementing functionality in imperative languages, ultimately i'm looking if there underlying methods access individual bits of z3 bitvector.

i played little bit illustration posted in question:

z3 pseudo-randomly hangs while parsing through sat model

i believe unsat instances hard solve because problem seems have many symmetries. if case, can improve performance including "symmetry breaking constraints". z3 can't break symmetries automatically kind of problem.

here minor encoding improvement. look ((st1 & (2**(i)))/(2**(i)) extracting i-th bit. can utilize extract(i, i, st1) extract i-th bit. result bit-vector of size 1. then, have "expand" avoid overflows. bit-vectors in problem have @ 28 bits. so, 5 bits plenty avoid overflows. therefore, can utilize zeroext(4, extract(i, i, st1)). is, replace

sum([( (st1 & (2**(i)))/(2**(i)) ) in range(bits)])

with

sum([ zeroext(4, extract(i,i,st1)) in range(bits) ])

i modest 2x speedup. so, z3 still cannot solve 6 bits unsat instance :(

python z3