Total order relations on $\mathbb{Z}_{2^n}$

Question

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.

Answer 1

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”.

Answer 2

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}$