I'm reading a section of the book Computer Systems: A Programmer's Perspective by Randal Bryant about integer arithmetic. There is the following definition:
To better understand this quantity, let us define $z$ as the integer sum $z = x + y$, $z'$ as $z'= z \mod2^w$ ....
And then they consider some cases:
- $-2^w \leq z < -2^{w - 1}$. Then we will have $z' = z + 2^w$...
- $-2^w \leq z < 0$. Then we will again have $z' = z + 2^w$...
I don't completely understand how they get to $z' = z + 2^w$. I have some thoughts, but I'm not sure about them and would like to find some better understanding of why the things are as they write them.
My thoughts are the following:
- Since $z'= z \mod2^w$, then we know that $z = q * 2^w + z'$, where $q \in Z$ and $0 \leq z' < 2^w$.
- Since $-2^w \leq z$, $q$ should be negative, otherwise we never get $z$ by summing up two positive numbers ($2^w$ and $z'$).
- My confusion starts here. It seems that $q$ can be only $-1$, because otherwise $2^w * q + z' > 2^w$, meaning that it will always be greaten than $z$
- Since the only possible $q$ is $-1$, then we have $z = 2^w * (-1) + z'$. Consequently we have $z' = z - (2^w * -1) = z + 2^w$.
Are my conclusions correct? I still can't have an intuition of why this works this way. Probably someone have much better and intuitive ideas to explain this or probably someone knows some easier ways to derive that equation. I'd be glad if you could share them.
