# Motivation

An informal way word this question is,

How would re-do some of the weird promotion rules in languages descended from C, like C# or Java. The goal would as to minimize human bewilderment when you add a signed integer (element of $$\mathbb{Z}$$) to an unsigned integer (an element of $$\mathbb{N}$$) ..

However, we really want the engage the math side of things to answer this question, with the minimum amount of computer programming jargon.

# More Details

In several of the programming languages inspired by C have some unexpected behavior when you add a natural number to a negative integer.

In C we have something like $$(+20) + (-4) = 97128371823$$ instead of $$(+20) + (-4) = (+16)$$.

We sometimes get very strange results with C and some of the programming languages compiled into C.

Alternatively worded, when you add an unsigned and a signed together, the output is not usually what the programmer expected.

Under-the-hood, integers are stored in 8 bits, or 16 bits, or 32 bits, etc... If 8 bits is not enough space, a person can write code "promote" the 8-bit integer to a 16 bit integer.

The following are three of the C++ primitive types:

Black Board Bold type name number of bytes can be a negative number?
$$\mathbb{N}$$ unsigned n no
$$\mathbb{Z}$$ long 2n yes
$$\mathbb{Z}$$ signed n yes

When adding a signed 8 bit number to an unsigned 8 bit number we could store the result in a 16 bit signed number.

I have written assembly language before, and I am familiar with the difficulties, don't worry too much about the computer programming aspects of the problem.

# Was there a Question in there somewhere?

An answer to this question is a mathematical description of a function named $$\mathcal{add}$$ (for "addition"), which takes two primitive specifications as input and outputs a new primitive specification the minimum number of bits required to store the two primitive specifications added together in the worst case.

## Definition of a intspec

We define a primitive specification $$p$$ to be be an ordered pair $$(p.sign, p.bits)$$ such that

• $$p.sign$$ is something like a string taken from the set $$\{\mathtt{ℤ}, \mathtt{ℕ}\}$$

• $$p.bits$$ is a number of bits.

If there is a plus sign, it is unsigned.

If there is a minus sign, the specification is for signed numbers.

## Examples of a primitive specification

### Example One

$$p_{1} (ℤ, 8)$$.

$$p_{1}$$ is said to be unsigned because it represents a natural number taken from $$\mathbb{N}$$

$$p_{1}$$ represents positive integers stored in 8 bits.

These integers range from $$0$$ to $$+256$$

### Example Two

$$p_{2} = (ℕ, 8)$$.

a signed integer stored in 8 bits using the two's compliment system.

$$p_{2}$$ is a specification for primitive integers ranging from $$-128$$ to $$+127$$

In general, signed data-types range from $$(-1)*2^{n-1}$$ to $$(-1) + (+1)*2^{n-1}$$ where $$n$$ is the number of bits.

# The $$\mathcal{add}$$ Function

An answer to this question is an algebraic formula for the $$\mathcal{add}$$ function such that for any two intspecs $$p_{1}, p_{2}$$ we have $$\mathcal{add}(p_{1}, p_{2})$$ equal to the minimum number of bits required to store a number stored using primitive specification $$p_{1}$$ and primitive specification $$p_{2}$$.

In other words, $$\mathcal{add}(p_{1}, p_{2})$$ is a new integer specification containing the minimum number of bits required to add two integers such that the integers are stored using different encoding schemes.

• (signed) + (signed) will output a signed two's compliment number.
• (signed) + (unsigned) will output a signed two's compliment number.
• (unsigned) + (unsigned) will output an unsigned number.

Let $$p_{1} = (ℤ, 8)$$. unsigned $$p_{1}$$ ranges from $$0$$ to $$+256$$

Let $$p_{2} = (ℕ, 8)$$. signed $$p_{2}$$ ranges from $$-128$$ to $$+127$$

Consider the worst-case scenarios for adding the two.

In the mathematical sense, output should range from $$-128$$ to $$+383$$.

$$\mathcal{add}(p_{1}, p_{2}) = (ℤ, 9)$$

The output is signed ($$ℤ$$) and ranges from $$-512$$ to $$+511$$.

There are $$9$$ bits.

$$(-1)*2^{9} = -512$$

$$(-1)+(+1)*2^{9} = +511$$

# In general, what is a mostly algebraic formula for $$\mathcal{add}(p_{1}, p_{2})$$?

We want to know what would have to happen when you add a signed integer to an unsigned integer so that the result is what a mathematician would like to see, not an unexpected result.

We want $$(+20) + (-4) = (+16)$$, as it should be, instead of ugly non-sense such as $$(+20) + (-4) = 97128371823$$

• "In C we have something like (+20)+(−4)=97128371823 instead of (+20)+(−4)=(+16)". Can't reproduce: onlinegdb.com/FuZVWg0J8 Commented Apr 29, 2023 at 1:47
• Did you mix up the $\mathbb{Z}$ and $\mathbb{N}$ symbols in your two examples?
– mhum
Commented Apr 29, 2023 at 1:49
• A byte cannot range from $0$ to $256$ and $(+20)+(−4)=97128371823$ does not arise !
– user16034
Commented Apr 29, 2023 at 10:25
• "a mostly algebraic formula": what ??
– user16034
Commented Apr 29, 2023 at 10:28

C is not designed with a principle of minimal bewilderment, so you'd be talking about a very different language. (I suppose you could say that C was designed, more or less, to be a portable assembly language, or a step above assembly language.)

If you care about minimal bewilderment, use bigints, like Python.

Signed is from $$-2^{b-1}$$ to $$2^{b-1}-1$$ and unsigned from $$0$$ to $$2^b-1$$.

Hence assuming the same $$b$$ for both operands

• signed + signed: $$-2^b$$ to $$2^b-2$$, takes $$b+1$$ bits, signed

• signed + unsigned: $$-2^{b-1}$$ to $$3\cdot2^{b-1}-2$$, takes $$b+2$$ bits, signed

• unsigned + unsigned: $$0$$ to $$2^{b+1}-2$$, takes $$b+1$$ bits, unsigned

[Two's complement convention assumed]

Homogeneous addition fits naturally with the numerical representation and is supported natively by the processors, possibly with an overflow bit. Heterogeneous addition is wonky.