6
$\begingroup$

I'm a programmer and not a professional mathematician so I need some abstract-algebra help regarding the following question:

Introduction:

When performing integer comparison x86 CPUs have some instructions that compares only signed 2's complement integers. So in order to perform unsigned comparison we usually use the following proposition:

$a \leq_{signed} b \iff a + 2^{n-1} \leq_{unsigned} b + 2^{n-1}$

for $n$-bit integers (i.e xor 0x800...000). This is not really obvious for me so I'm looking for a formal proof of that "ought to be obvious" fact.

My thoughts:

Consider $\mathbb{Z}_{2^n}$ group with + operation and for any $m \in \mathbb{Z}_{2^n}$ define the following relations $\forall a \neq m: a \leq_m a + 1$. So the signed and unsigned comparison can be defined as $\leq_{2^{n-1} -1}$ and $\leq_{2^n-1}$.

The first thing I'm considering to prove is that for each $m\in\mathbb{Z}_{2^n}$ there is only one total order relation $\leq_m$. This can be easily proven by assuming two different total order relations with $\forall a \neq m: a \leq_m a + 1$ which are equal then.

Now I'm considering to prove that for any $m, k \in\mathbb{Z}_{2^n}$ we have $a \leq_m b \iff a + (m - k)\leq_k b + (m - k)$.

The question is if the latter statement is even true? If so, can you give a hint how to prove this.

$\endgroup$
1
$\begingroup$

As I understood, (see here) a signed $n$-bit integer $a$ (that is a integer $a$ such that $-2^{n-1}\le a\le 2^{n-1}-1$) is presented in a memory in the unsigned form of its $n$-complement $a^*$, which is a binary representation of a unique integer $0\le a’\le 2^n-1$ such that $a=a’\pmod 2^n$. See also a bit below

In two's complement notation, a non-negative number is represented by its ordinary binary representation; in this case, the most significant bit is $0$... negative numbers are represented by the two's complement of the absolute value.

Now let $-2^{n-1}\le a,b\le 2^{n-1}-1$. Then $a\le b$ iff $a+2^{n-1}\le b+2^{n-1}$ and $0\le a+2^{n-1},b^{n-1}\le 2^n-1$. But not necessarily $a’\le b’$. For instance, if $n=2$, $a=-1$, and $b=1$ then $a<b$, whereas $a’=3>b’=1$. But when $a$ and $b$ have the same sign then $a’\le b’$ iff $a\le b$, see also, “Why it works”.

$\endgroup$
0
$\begingroup$

I'm not sure if the following reasoning can be considered strongly mathematically correct, but anyway I will provide the way I currently see it:

Now I'm considering to prove that for any $m,k\in\mathbb{Z}_{2^n}$ we have

$a\leq_m b \iff a + (m - k) \leq_k b + (m - k)$

For any $m\in\mathbb{Z}_{2^n}$:

$ a\leq_m b \iff \exists i \in \{0, 1, ..., m - a\}: b = a + i \iff \exists i \in \{0, 1, ..., m - a\}: 1 + b = 1 + a + i \iff \exists i \in \{0, 1, ..., (m + 1)- (a + 1)\}: 1 + b = 1 + a + i\iff a + 1 \leq_{m + 1} b + 1$

Now by induction we can see that $a \leq_m b \iff a + (k - m)\leq_{m + (k - m)} b + (k - m) \iff a + k - m \leq_{k} b + k - m$.

So as noted in the question the unsigned comparison is $\leq_{2^n -1}$ and signed comparison is $\leq_{2^{n-1} - 1}$ we have that:

$a \leq_{signed} b \iff a + 2^{n-1} \leq_{unsigned} b + 2^{n-1}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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