Benchmark

non-incremental/QF_ABV/brummayerbiere2/countbitstable016.smt2 

Count bits pop(x) algorithm, table lookup method
From the book "Hacker's delight" by Henry S. Warren, Jr., page 71
The algorithm precomputes pop(x) for x in range 0 to 255 and stores it
into a lookup table.

We cross-check it with the obvious method of counting bits:
for (s = i = 0; i < BW; i++)
  if (x & (1 << i))
    s++;

Contributed by Robert Brummayer (robert.brummayer@gmail.com)
Benchmark
Size11203
Compressed Size1366
License Creative Commons Attribution 4.0 International (CC-BY-4.0)
Categorycrafted
First Occurrence2008-07-07
Generated By—
Generated On—
Generator—
Dolmen OK1
strict Dolmen OK1
check-sat calls1
Query 1
Status unsat
Inferred Status unsat
Size 11195
Compressed Size1384
Max. Term Depth260
Asserts 1
Declared Functions0
Declared Constants2
Declared Sorts 0
Defined Functions0
Defined Recursive Functions 0
Defined Sorts0
Constants0
Declared Datatypes0

Symbols

ite33 not1 =34 let15
concat2 extract2 bvnot17 bvand16
bvadd17 bvshl16 bvlshr1 zero_extend16
select2 store256

Evaluations

Evaluation Rating Solver Variant Result Wallclock CPU Time
SMT Evaluation 2013 Boolector Boolector-1.5.118-SMT-EVAL-2013 default unsat ✅ 0.53988 —
Boolector-SMT-COMP-2011 default unsat ✅ 4.04086 —
Boolector-SMT-COMP-2012 default unsat ✅ 0.71835 —
CVC3 CVC3-SMT-COMP-2010 default unknown ❌ 334.34600 —
CVC3-SMT-COMP-2011 default unsat ✅ 385.54800 —
CVC3-SMT-COMP-2012 default unsat ✅ 385.62400 —
CVC4 CVC4-SMT-COMP-2012-Resubmission default unsat ✅ 271.55000 —
CVC4-SMT-EVAL-2013 default unsat ✅ 380.99400 —
MathSAT MathSAT5-5.2.6-SMT-EVAL-2013 default unsat ✅ 5.58784 —
MathSAT5-SMT-COMP-2011 default unsat ✅ 98.45910 —
MathSAT5-SMT-COMP-2012 default unsat ✅ 253.69700 —
SONOLAR SONOLAR-2013-05-15-SMT-EVAL-2013 default unsat ✅ 17.22490 —
SONOLAR-SMT-COMP-2011 default unsat ✅ 17.92670 —
SONOLAR-SMT-COMP-2012 default unsat ✅ 18.40800 —
Tiffany de Wintermonte TdW-SMT-COMP-2012 default unsat ✅ 0.51074 —
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-EVAL-2013 default unsat ✅ 19.63390 —
Z3-SMT-COMP-2011 default unsat ✅ 111.79800 —
SMT-COMP 2014 Boolector Boolector boolectord unsat ✅ 1.20330 1.19282
Boolector boolectorj unsat ✅ 1.21053 1.19982
CVC4 CVC4 f7118b2 default unsat ✅ 713.53700 713.76000
Kleaver Kleaver-indie-more-typed kleaver_indie_1 unsat ✅ 0.50479 0.49592
Kleaver-indie-more-typed kleaver_portfolio unsat ✅ 0.66142 1.92771
MathSAT MathSAT-5.2.12-Main default unsat ✅ 5.57848 5.57215
SONOLAR sonolar_smtcomp-2014 default unsat ✅ 13.23290 13.22800
Yices2 Yices-2.2.1-smtcomp2014 default unsat ✅ 0.92782 0.91986
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-COMP-2014 default unsat ✅ 29.64490 29.64650
SMT-COMP 2015 Boolector Boolector SMT15 QF_AUFBV final boolector_qf_aufbv unsat ✅ 0.60707 0.60591
CVC4 CVC4-master-2015-06-15-9b32405-main default unsat ✅ 508.11900 508.32200
CVC4-experimental-2015-06-15-ff5745a-main default unsat ✅ 156.40600 156.46500
MathSAT MathSat 5.3.6 main smtcomp2015_main unsat ✅ 4.37252 4.37333
Yices2 Yices default unsat ✅ 0.97552 0.97485
Z3 z3 4.4.0 default unsat ✅ 25.26240 25.27320
SMT-COMP 2016 Boolector Boolector boolector unsat ✅ 0.60761 0.60834
CVC4 CVC4-master-2016-05-27-cfef263-main default unsat ✅ 152.85900 152.91600
MathSAT mathsat-5.3.11-linux-x86_64-Main default unsat ✅ 4.11730 4.12088
Yices2 Yices-2.4.2 default unsat ✅ 0.97914 0.97968
Z3 z3-4.4.1 default unsat ✅ 29.17130 29.18950
SMT-COMP 2017 Boolector Boolector SMT17 final boolector unsat ✅ 1.14629 1.14448
CVC4 CVC4-smtcomp2017-main default unsat ✅ 166.01800 165.98500
MathSAT mathsat-5.4.1-linux-x86_64-Main default unsat ✅ 4.07208 4.07213
Yices2 Yices2-Main default unsat ✅ 0.96447 0.96368
Z3 z3-4.5.0 default unsat ✅ 32.16430 32.15880
SMT-COMP 2018 0.20 (4/5) Boolector Boolector_default unsat ✅ 1.27739 1.27736
CVC4 master-2018-06-10-b19c840-competition-default_default unsat ✅ 185.85100 185.82500
MathSAT mathsat-5.5.2-linux-x86_64-Main_default unknown ❌ 5.38535 5.38249
Yices2 Yices 2.6.0_default unsat ✅ 0.86604 0.86573
Z3 z3-4.7.1_default unsat ✅ 26.78520 26.78330
SMT-COMP 2019 Boolector Boolector-wrapped-sq_default unsat ✅ 0.95046 0.95041
Poolector-wrapped-sq_default unsat ✅ 1.01614 3.37908
CVC4 CVC4-2019-06-03-d350fe1-wrapped-sq_default unsat ✅ 237.07500 237.04700
Par4 Par4-wrapped-sq_default unsat ✅ 0.93481 2.72000
Yices2 Yices 2.6.2-wrapped-sq_default unsat ✅ 1.23042 1.23037
Z3 z3-4.8.4-d6df51951f4c-wrapped-sq_default unsat ✅ 29.66840 29.66510
SMT-COMP 2022 Bitwuzla Bitwuzla-wrapped_default unsat ✅ 1.01465 1.01460
cvc5 cvc5-default-2022-07-02-b15e116-wrapped_sq unsat ✅ 177.70500 177.70300
MathSAT MathSAT-5.6.8_default unsat ✅ 10.36270 10.36170
Yices2 Yices 2.6.2 for SMTCOMP 2021_default unsat ✅ 1.25973 1.25968
Z3 z3-4.8.17_default unsat ✅ 224.31900 224.22500
SMT-COMP 2025 0.50 (3/6) Bitwuzla Bitwuzla unsat ✅ 7.60595 7.48708
cvc5 cvc5 unknown ❌ 1201.75703 1200.91870
SMTInterpol SMTInterpol unknown ❌ 1201.36393 1246.21757
Yices2 Yices2 unsat ✅ 1.02961 0.91430
Z3 Z3-Owl-base unknown ❌ 1201.28500 1200.88102
Z3-Owl Z3-Owl unsat ✅ 146.55067 146.40220