CODEWITHSUNDEEP
binaryunsignedunsigned-integer
swimminggymnast
swimminggymnast

Reputation: 81

Unsigned binary integer subtraction

Is it possible to subtract a larger unsigned integer from a smaller unsigned integer? The example I'm trying to think about is 00000000-11111111, where both integers are unsigned.

Since unsigned ints can't be negative, what would this expression evaluate to?

Upvotes: 1

Views: 1007

Answers (1)

user555045
user555045

Reputation: 64913

Yes, at least under the common definition. "Cannot be negative" does not mean that subtraction becomes a partial function, ie "sometimes impossible". It means that there is some result, and by definition it is non-negative, by interpreting the top bit as having a positive weight rather than negative, so there is simply no combination of bits that is interpreted as a "negative value".

It is really just about the bits though. Signed and unsigned integers are slightly different interpretations for what the bits mean (eg for 8 bits, the top bit has a weight of -128 or +128 depending on whether we're interpreting it as signed or unsigned), resulting in some operations having separate signed and unsigned versions (obviously greater-than and less-than, also division and some others). Subtraction is notably absent from that list of anomalies: subtraction is subtraction, there are no "signed subtraction" and "unsigned subtraction".

There are a few ways to define subtraction without needing too many other definitions, for example:

  • x - y = ~(~x + y)
  • x - y = x + ~y + 1

(these are of course equivalent definitions, otherwise there would be a problem)

Bitwise complement is a primitive operation on bit-vectors, and addition is just the usual bit-vector addition, which is neither really signed nor unsigned, it does both.

So there are different ways to look a the example, 00000000 - 11111111. One is to notice that the right operand to the subtraction is also known as negative 1 (which makes sense to say even when looking through "unsigned glasses" since 11111111 + 00000001 = 00000000 and therefore the algebraic definition of negation is satisfied) and we known that 0 - (-1) = 1 so the answer must be 00000001. Or we can use a definition of subtraction, for example 00000000 - 11111111 = ~(~00000000 + 11111111) = ~(11111111 + 11111111) = ~11111110 = 00000001

Upvotes: 2

Related Questions