-1
$\begingroup$

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$

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

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.