1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
###############################################################################
# Top contributors (to current version):
# Alex Ozdemir
#
# This file is part of the cvc5 project.
#
# Copyright (c) 2009-2025 by the authors listed in the file AUTHORS
# in the top-level source directory and their institutional affiliations.
# All rights reserved. See the file COPYING in the top-level source
# directory for licensing information.
# #############################################################################
#
# A simple demonstration of the solving capabilities of the cvc5
# bit-vector solver.
##
from cvc5.pythonic import *
if __name__ == '__main__':
# The following example has been adapted from the book A Hacker's Delight
# by Henry S. Warren.
#
# Given a variable x that can only have two values, a or b. We want to
# assign to x a value other than the current one. The straightforward code
# to do that is:
#
# (0) if (x == a ) x = b;
# else x = a;
#
# Two more efficient yet equivalent methods are:
#
# (1) x = a xor b xor x;
#
# (2) x = a + b - x;
#
# We will use cvc5 to prove that the three pieces of code above are all
# equivalent by encoding the problem in the bit-vector theory.
x, a, b = BitVecs('x a b', 32)
x_is_a_or_b = Or(x == a, x == b)
# new_x0 set per (0)
new_x0 = If(x == a, b, a)
# new_x1 set per (1)
new_x1 = a ^ b ^ x
# new_x2 set per (2)
new_x2 = a + b - x
prove(Implies(x_is_a_or_b, new_x0 == new_x1))
prove(Implies(x_is_a_or_b, new_x0 == new_x2))
|
