# Proof involving two's complement arithmetic of binary numbers

I have a "clock" - a 32-bit unsigned number - that wraps around from $4,294,967,295$ ($2^{32}-1$) back to $0$.
At point 'A' in time, I stamp the clock into a variable - call it $x$.
Later, at point 'B' in time, I stamp the clock again into another variable - call it $y$.
I want to convince myself that as long as the clock hasn't been wrapped around more than once between the two points 'A' and 'B', the result of the subtraction $(y - x)$ will always give the correct result - regardless of which is bigger (the correct result being how many 'ticks' the clock has counted from 'A' to 'B').

I know that when dealing with unsigned numbers in a binary system (with two's complement arithmetic), it holds that $z = 2^N -z'\hspace{10pt}\forall z=0,1,...,2^N-1$, where $z'$ is the "negative" (i.e. the two's) complement of $z$. I feel like it's relevant, but still can't prove the above to myself...
Can someone help proving it?

Example where $N=4$:

$\begin{array}{ccccccc}0& 1& 2& 3& 4& 5& 6& 7\\ 0000& 0001& 0010& 0011& 0100& 0101& 0110& 0111\end{array}$

$\begin{array}{ccccccc}8& 9& 10& 11& 12& 13& 14& 15\\ 1000& 1001& 1010& 1011& 1100& 1101& 1110& 1111\end{array}$

$2 - 11 = -9$ which is equivalent to $7$, having only $4$ digits, and is exactly the number of ticks passed from $11$ to $2$, when considering clock wrap around.

• You probably want $y-x$ rather than $x-y$, since $x$ is stored earlier. Anyway, you'll always get a result that is "correct modulo $2^{32}$". But you only get the correct result if there were fewer than $2^{32}$ ticks between $A$ and $B$. If at time $A$, the clock was at $10$, say, and time $B$ is $2^{32} + 10$ ticks later, the clock wrapped only once, but you get the wrong result ($10$ instead of $2^{32} + 10$). – Daniel Fischer May 12 '16 at 21:07
• Yes, you're right. I meant y - x... Regarding the rest - I can understand the intuition, just wondered if this can be proved mathematically... – so.very.tired May 12 '16 at 22:06

## 1 Answer

Let $0\leq x,y\leq2^{N}-1$, s.t. $x<y$.
To show that I get the "correct result", means to show that: $(x-y)\mod2^N = 2^N-(y-x)$
(I guess that what I was having difficulty defining...).
Now if I apply $\mod 2^N$ on RHS:
$(2^N-(y-x))\mod 2^N$
$(2^N+(x-y))\mod 2^N=$
$(2^N\mod 2^N+(x-y)\mod 2^N)\mod 2^N=$
$(0 + (x-y)\mod 2^N)\mod 2^N=$
$(x-y)\mod 2^N$