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

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.

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

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