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.
Best 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)$
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$