Benchmark

non-incremental/QF_ABV/brummayerbiere2/countbitstableuninit0064.smt2

Count bits pop(x) algorithm, table lookup method, buggy version
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. However, one precomputed value is uninitialized.

We try to 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
Size	20352
Compressed Size	1842
License	Creative Commons Attribution 4.0 International (CC-BY-4.0)
Category	crafted
First Occurrence	2008-07-07
Generated By	—
Generated On	—
Generator	—
Dolmen OK	1
strict Dolmen OK	1
check-sat calls	1

Query 1

Status	sat
Inferred Status	sat
Size	20344
Compressed Size	1838
Max. Term Depth	259
Asserts	1
Declared Functions	0
Declared Constants	2
Declared Sorts	0
Defined Functions	0
Defined Recursive Functions	0
Defined Sorts	0
Constants	0
Declared Datatypes	0

Symbols

ite	129	not	1	=	130	let	69
concat	8	extract	8	bvnot	65	bvand	64
bvadd	71	bvshl	64	bvlshr	7	zero_extend	64
select	8	store	255

Evaluations

Evaluation	Rating	Solver	Variant	Result	Wallclock	CPU Time
SMT-COMP 2010		Boolector	Boolector 1.2	sat ✅	1.10000	—
		CVC3	CVC3 2.3	sat ✅	18.90000	—
SMT Evaluation 2013		Boolector	Boolector-1.5.118-SMT-EVAL-2013 default	sat ✅	1.03910	—
			Boolector-SMT-COMP-2011 default	sat ✅	0.77622	—
			Boolector-SMT-COMP-2012 default	sat ✅	0.24571	—
		CVC3	CVC3-SMT-COMP-2010 default	sat ✅	10.65600	—
			CVC3-SMT-COMP-2011 default	sat ✅	9.70202	—
			CVC3-SMT-COMP-2012 default	sat ✅	9.80391	—
		CVC4	CVC4-SMT-COMP-2012-Resubmission default	sat ✅	402.11000	—
			CVC4-SMT-EVAL-2013 default	sat ✅	368.76200	—
		MathSAT	MathSAT5-5.2.6-SMT-EVAL-2013 default	sat ✅	3.46196	—
			MathSAT5-SMT-COMP-2011 default	sat ✅	87.91810	—
			MathSAT5-SMT-COMP-2012 default	sat ✅	69.33620	—
		SONOLAR	SONOLAR-2013-05-15-SMT-EVAL-2013 default	sat ✅	1.44795	—
			SONOLAR-SMT-COMP-2011 default	sat ✅	0.63530	—
			SONOLAR-SMT-COMP-2012 default	sat ✅	1.31360	—
		Tiffany de Wintermonte	TdW-SMT-COMP-2012 default	sat ✅	0.54166	—
		Z3	Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-EVAL-2013 default	sat ✅	36.70530	—
			Z3-SMT-COMP-2011 default	unknown ❌	—	—
SMT-COMP 2014		Boolector	Boolector boolectord	sat ✅	0.31369	0.31095
			Boolector boolectorj	sat ✅	0.27798	0.26796
		CVC4	CVC4 f7118b2 default	sat ✅	59.27850	59.27700
		Kleaver	Kleaver-indie-more-typed kleaver_indie_1	sat ✅	0.30972	0.30095
			Kleaver-indie-more-typed kleaver_portfolio	sat ✅	0.38765	1.12183
		MathSAT	MathSAT-5.2.12-Main default	sat ✅	4.24755	4.24035
		SONOLAR	sonolar_smtcomp-2014 default	sat ✅	2.29120	2.27765
		Yices2	Yices-2.2.1-smtcomp2014 default	sat ✅	0.78449	0.77588
		Z3	Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-COMP-2014 default	sat ✅	128.48800	128.52100
SMT-COMP 2015		Boolector	Boolector SMT15 QF_AUFBV final boolector_qf_aufbv	sat ✅	1.11191	1.11083
		CVC4	CVC4-master-2015-06-15-9b32405-main default	sat ✅	501.78500	501.89400
			CVC4-experimental-2015-06-15-ff5745a-main default	sat ✅	2.71438	2.71259
		MathSAT	MathSat 5.3.6 main smtcomp2015_main	sat ✅	3.91947	3.92040
		Yices2	Yices default	sat ✅	0.45390	0.45293
		Z3	z3 4.4.0 default	sat ✅	35.11510	35.12970
SMT-COMP 2016		Boolector	Boolector boolector	sat ✅	0.54117	0.54143
		CVC4	CVC4-master-2016-05-27-cfef263-main default	sat ✅	6.56729	6.57178
		MathSAT	mathsat-5.3.11-linux-x86_64-Main default	sat ✅	4.02616	4.02954
		Yices2	Yices-2.4.2 default	sat ✅	0.78553	0.78573
		Z3	z3-4.4.1 default	sat ✅	53.42080	53.45420
SMT-COMP 2017		Boolector	Boolector SMT17 final boolector	sat ✅	0.51111	0.51036
		CVC4	CVC4-smtcomp2017-main default	sat ✅	18.55800	18.55540
		MathSAT	mathsat-5.4.1-linux-x86_64-Main default	sat ✅	5.19898	5.19935
		Yices2	Yices2-Main default	sat ✅	0.37957	0.37950
		Z3	z3-4.5.0 default	sat ✅	114.58000	114.55600
SMT-COMP 2018	0.20 (4/5)	Boolector	Boolector_default	sat ✅	0.49549	0.49541
		CVC4	master-2018-06-10-b19c840-competition-default_default	sat ✅	11.35930	11.35920
		MathSAT	mathsat-5.5.2-linux-x86_64-Main_default	unknown ❌	3.73093	3.73151
		Yices2	Yices 2.6.0_default	sat ✅	0.40389	0.40386
		Z3	z3-4.7.1_default	sat ✅	156.80000	156.79900
SMT-COMP 2021	0.33 (2/3)	MathSAT	mathsat-5.6.6_default	sat ✅	10.53870	10.53860
		Yices2	Yices 2.6.2 bug fix_default	sat ✅	0.62737	0.62736
			Yices 2.6.2 for SMTCOMP2020_default	sat ✅	0.62825	0.62818
		Z3	z3-4.8.11_default	unknown ❌	1200.01000	1199.86000
SMT-COMP 2025	0.50 (3/6)	Bitwuzla	Bitwuzla	sat ✅	0.71010	0.59379
		cvc5	cvc5	unknown ❌	1201.78623	1201.03137
		SMTInterpol	SMTInterpol	unknown ❌	1201.48677	1257.54844
		Yices2	Yices2	sat ✅	0.64718	0.52943
		Z3	Z3-Owl-base	unknown ❌	1201.29651	1201.04381
		Z3-Owl	Z3-Owl	sat ✅	798.98580	798.75415