Search code examples
binarybitwise-operatorsbit-shiftnegative-numberones-complement

Left shift operation with Ones' complement binary


I'm in researching about bitwise operation and signed number representations​. I've recognized that if we do left shift on ones' complement pattern. It does not correctly multiply the original number.

For example (Ones' complement):

11100101 (-26) << 1 = 11001010 (-53)

11110100 (-11) << 2 = 11010000 (-47)

-26 left shift 1 bit give -53 (not -52), -11 left shift 2 bits give -47 (not -44). So is this a reason why people choose two's complement for precision number operation. I've searched on google but no post mention about the left shift and ones' complement. Almost mention left shift with two's complement


Solution

  • In two's complement, a negative number A is coded by the positive number 2n-|A| and it is possible to find its value by -2n-1 × an-1 + ∑0n-2 2i × ai It is easy to show that shifting this value left by k bits will give the code of A×2k, provided there is no overflow (ie only zeroes or only ones are shifted out).

    In ones complement, a negative number A is coded by (2's complement of A)-1. Its value is -2n-1 × an-1 + ∑0n-2 2i × ai-1. If we left shift it by k, the numeric value of the result is (2's complement of 2k*A)-2k*1 (provided there is no overflow). It is different by 2k-1 from the expected result which would be (2's complement of 2k*A)-1

    We can verify it on your examples:

    C1(-26)<<1=-53(=-52-(21-1))
    C1(-11)<<2=-47(=-44-(22-1))

    So to multiply a negative number coded in 1's complement by 2k, you need to left shift it by k and to add to your result 2k-1

    In general, only two's complement gives simple arithmetic operations. Other codes (excess k, one's complement, sign absolute value) always require a correction (and it is the reason why they are very rarely used).