0
$\begingroup$

Suppose I have a number 1 in floating point:

let initial = 1;

It has the following binary representation in IEEE-754:

0011111111110000000000000000000000000000000000000000000000000000

Now, I have the following algorithm to convert the number to 8-bit two's complement with the last and most important steps being:

Let int8bit be int modulo 2^8.
If int8bit ≥ 2^7, return int8bit − 2^8, otherwise return int8bit.

where int is original number representation.

The resulting number is represented as:

00000001

So as I understand the number is converted using modulo operation. What's the retional here and how is it applied to the actual bits?

$\endgroup$

1 Answer 1

1
$\begingroup$

The rationale is that the result has to be valid for 8-bit integer, that is the result $n$ must be an integer in the range $-128 \leq n \leq +127$.

So what the last two steps does is to find a number in that range such that the difference to the number in the previous step is a multiple of $2^8$.

The modulo $2^n$ operation is actually a special case of a remainder when dividing by $2^n$. We have the general case if we have an integer $n$ that it can be written as $n=q\cdot 2^8 + r$ where $q$ is the quotient and $r$ is the remainder. Now there exists multiple choices of $r$, but there exists only one in each set of $2^8$ integers. The modulo $2^8$ operation chooses $r$ in the range $0 \leq r \leq 255$ while in this case we want to have a number in the range $-128 \leq n \leq 127$.

The reason $2^8$ is important is because the way computers normally are constructed and the language is specified to accomodate this. To fully understand this you need to know how computers adds integers, which actually is straight forward, but one need to know that the integers are stored binary with a fixed number (depending on the type) of bits (bit is the binary counterpart to digit). The way it is done is the same as you do when adding with paper and pen with two differences, first they use binary numbers (while you probably uses decimal), second they are still restricted to a fixed number of bits which have consequences. Normally if you when adding get a carry from the leftmost digit you just extend with one more digit (which will be the carry digit), but since computers work with fixed number of bits this can't do that. What they do instead in this case is that they simply discard that carry. The consequence is that one get a result that differ from the true result by $2^n$ (a multiple of $2^n$) where $n$ is the number of bits. Similar feature is present in other operations, in case of overflow the result of the operation tends to be off by a multiple of $2^n$ bits. This is called that the computer does modulo $2^n$ arithmetics.

So that's why it's considered important that the result differs a multiple of $2^8$ to the true result - because the result of virtually any other operation will do just that.

You may wonder how negative numbers are handled in computers. It actually uses this feature too. A signed 8-bit integer is basically represented as an unsigned, but interpreted to be in the range $ \{ -128, -127, ..., 126, 127 \} $ in a way that it differs a multiple of $2^8$ from the unsigned integer. The range is not arbitrarily chosen, it's because negative numbers will be represented as $(10000000)_2$ and above and positive as $(01111111)_2$ and below -- the leftmost bit shows whether the number is considered negative or not (and as negative it actually represent the number $2^8$ less than the raw number).

$\endgroup$
5
  • $\begingroup$ thanks a lot for you answer, such that the difference to the number in the previous step is a multiple of 2^8. - why is it important? $\endgroup$ Commented Mar 7, 2017 at 11:08
  • $\begingroup$ can you please respond to my comment? $\endgroup$ Commented Mar 9, 2017 at 15:41
  • $\begingroup$ @Maximus Sorry for the delay, I've updated the answer a bit... $\endgroup$
    – skyking
    Commented Mar 10, 2017 at 6:42
  • $\begingroup$ thanks a lot for your elaboration! I need to work a bit on understanding it) may I conclude that for the conversion algorithm it's not important how exactly the modulo operation is implemented on the binary level, but rather that a resulting number differs a multiple of 2^8? $\endgroup$ Commented Mar 10, 2017 at 7:11
  • $\begingroup$ @Maximus Yes. The only thing you need to know how the modulo operation is implemented is to understand why differences of only multiple of $2^8$ is important. $\endgroup$
    – skyking
    Commented Mar 10, 2017 at 8:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .