How to model signed integer with BitVector?

Question

Suppose that a is an integer of 8-bit of value 254. If a is a signed integer, it is actually considered -2. In contrary, if a is unsigned, it remains 254.

I am trying to model this signed/unsigned integer problem with BitVector theory with Z3, but it seems BitVector doesnt allow this. Is this true? Then any idea on how to model this in Z3py?

Thanks so much.

Answer 1

Z3 has APIs for the signed and unsigned interpretations. For example, in the C API, Z3_mk_bvslt creates the signed less than, and Z3_mk_bvult the unsigned one. In Z3Py, we overloaded <, <=, ... using the signed ones. For creating, the unsigned a < b, we have to use ULT(a,b). Here is the list of unsigned operators: ULE (<=), ULT (<), UGE (>=), UGT (>), UDiv (unsigned division), URem (unsigned remainder). You can find more information here:

http://research.microsoft.com/en-us/um/redmond/projects/z3/namespacez3py.html

Answer 2

You are correct to observe that bit-vector values don't carry a sign. On the other hand, there are signed versions of bit-vector operations and relations. SO you can treat the same bit-vector entity as a signed or unsigned number by passing them to a signed or unsigned comparison (signed less/unsigned less) or signed or unsigned operation (signed division/unsigned division). Other arithmetical operations work the same on signed and unsigned entities. For example addition moves the bits around the same way whether you want to interpret them as signed or unsigned.

Z3 follows the conventions of the SMT-LIB2 theories, and you can find extensive documentation on these on: http://smtlib.cs.uiowa.edu/theories/FixedSizeBitVectors.smt2