Difference between revisions of "Bitwise math/Overflows"

Latest revision as of 04:18, 19 July 2012

back to Bitwise math

Now, overflow occurs in a "signed" integer when it increments too far. Using a nibble for an example,

The highest positive value is 7, 0111, the lowest negative value is -8, 1000. On a processor, the increment instruction(inc) changes this. If -8 is incremented, -7 is obtained, since it is incremented. Basically when moving to 7 and incremented, the next step in binary is 1000 and it lands on -8.

In an arithmetic shift, this is typically what processors do since signed numbers are worked with most of the times. Now of course, there are ways to use unsigned numbers, but this will be left for later. Most languages use an arithmetic shift, which is also called a 'signed shift'. This is because the number is "signed", that is, it has a + or - attatched to its value. Thus, when reading the hex, the way this works isn't going to change so terribly.

Example: 6 incremented left by 1, becomes -8 (1100)'

Operation	Hexadecimal	Binary	comment
Left Shift	6 1	0110 0001	shifted to the left once, the largest digit gets a 1. In this case, this gives the whole value a -8, not an eight.
=	"-8"	1100	The highest value "loops" back around to the lowest, like a clock/modular arithmetic.

The difference here is if that first bit is -8 and not an 8. A positive number has just been turned into a negative number. 6 left shift 1 = -4

Binary number 1100 = -8 + 4 = decimal number -4

Negative Eights -(1x2^3)	Fours (1x2^2)	Twos (1x2^1)	Ones (1x2^0)
-8	4	2	1
1	1	0	0

It's now -4.

If shifted to the right, a single shift will /always/ change the sign. If shifted to the left on any /unsigned/ binary number (shift by n), it is the same as multiplying it by 2^n. If shifted to the right on a two's complement signed number it is the same as dividing it by 2^n and always rounds down.

Example:

-8 right shift 1 or 1000 right shift 1 becomes 4. In other words, any signed number right shifted becomes positive immediately. Regardless of whether it was positive or not, it will always be positive once a right shift has been applied.

As stated before, x right shift n on a signed number is the same as x/(2^n). The problem that this could cause is that it always rounds down. So, if it always rounds down from 2^n (i.e. a fraction is obtained) it will round down until the fraction is gone.

The flow on problem from this is that if it rounds down and n is signed, the processor can run into a divide by zero error.