Guaranteeing negative result when left shifting a negative number in two's complement?

7
votes

Assuming a negative binary number is represented in two's complement, how can we guarantee the sign is preserved?

Let's say we represent a decimal number -5 in four bits: 1011, and want to left-shift one place to multiply by 2:

1011 << 1

This operation returns 0110, which is 6, not -10 as we would have hoped.

(I assume this is only the case for negative numbers whose second bit is 0, ie negative numbers close to the smallest representable negative number of some range)

1
binarybit-manipulationbit-shifttwos-complementnegative-number
@PaulR I've read that most implementations of << meet the requirements of both ASL and LSL. Does an ASL operation somehow preserve the most significant bit (sign bit)? If so, does it do it by shifting out bits, starting with the second bit instead of the MSB? – sgarza62
The image on this Wikipedia article suggests the MSB is shifted out and replaced, which is fine for unsigned numbers, but not so for signed negative numbers – right? en.wikipedia.org/wiki/Arithmetic_shift – sgarza62
Sorry - I realise I was talking nonsense in my comment above: for 2's complement, LSL and ASL are exactly the same. The OP's confusion comes from a different misunderstanding. – Paul R
So, how do you express -10 in a 4-bit field? – Hot Licks
@HotLicks You can't in a 4-bit field. The first bit denotes the sign in a two's complement system, so we're left with three bits. You would need at least 5 bits total to represent -10: 10110. – sgarza62

1 Answers

6
votes

OP here. I found the answer to my question.

Shifting left may trigger arithmetic overflow.

The range of numbers expressible by a two's complement system is from -(2^(n-1)) to 2^(n-1)-1, where n is the number of bits available, including the sign bit (MSB). So, in the above example where each number uses 4 bits, the range of possible values is -8 to 7, inclusive.

Shifting left by m bits will multiply the number by 2^m. So, in the above example -5 << 1 would yield -10, which is beyond the range of possible numbers in a 4-bit signed representation – that's an overflow.

1111 << 1 == 1110 // -1 * 2 is -2
1110 << 1 == 1100 // -2 * 2 is -4
1101 << 1 == 1010 // -3 * 2 is -6
1100 << 1 == 1000 // -4 * 2 is -8
1011 << 1 == 0110 // overflow
1010 << 1 == 0100 // overflow
1001 << 1 == 0010 // overflow
1000 << 1 == 0000 // overflow

In conclusion, while using ASL to multiply by powers of two, it is important to make sure the product lies within the range of possible values.