Two’s Complement Encoding and Decoding
Let denote the integer field with usual arithmetic addition and subtraction. Let be a natural number no smller than two, which will be fixed throughout this note. Write We primarily treat each as an unsigned integer and identify it with its -bit binary representation.
An important unary operator on is the bitwise NOT operator. It flips each position in the binary representation of a given unsigned number. Because the bitwidth of the resulting number is , the bitwise NOT operator maps each member of to a member of . Also, we see that the sum of and its bitwise NOT is represented by the -bit binary representation all of whose positions are set, i.e., or equivalently, Based on this fact, we define a function by
A function whose inverse is the function itself is called an involution.
Proof. The function is involution, because for each , ◻
Besides unsigned integers, we need to deal with signed integers. Because the compouters only deal with binary data, each signed integer needs to converted to the binary data containing information on both its signs and magnitude. If the data width is bits, one bit is consumed by the information on the sign. We can naturally cover signed integers that can be expressed in bits.
A widely used method for the encoding of signed numbers is the two’s complement method. Write and define the function defined by
Proof. For each nennegative , we have that , so that It follows that is a bijection from to This verifies ().
For each negative , we have that , so that It follows that is a bijection from to Claim () therefore follows.
Given claims () and (), is an injection on . It is also a surjection, because Thus, Claim () holds. ◻
As Proposition shows, maps nonnegative integers in to the same values in the lower half of , while it maps negative integers in to the upper half of . For a negative integer , we have that In this view, maps each negative to the two’s complement of the magnitude of . So, we can take as an encoder using the two’s complement method.
In addition to the encoding method for signed integers, we also need a decoding method. Define by Then:
Proof. For each , we have that Because , the right-hand side of this equality is equal to The result therefore follows. ◻
Bitwise Shift Operations
We sometimes need to take bitwise shift operations on an integer of a particular bitwidth. Define , , , and by and respectively. The values of and are obtained by logical left and right shifts of the -bit unsigned integer by , respectively. On the other hand, the values of and are obtained by arthmetic left and right shifts of by . While and work exactly in the same say, fills the vacant bit positions created by the shift by zeros, while fills the vancant bit positions by the most significant bit of ().
The bitwise shift operations with signed integers encoded by the two’s complement method requires some care.
Proof. Suppose that . Then we have where the last equality holds because . The claim follows by Propositions () and .
Now, suppose instead that . Then it holds that Because , the first term on the right-hand side is equal to , it follows that Because , the claim follows by Propositions () and . ◻
Addition and Subtraction
The computers have instructions for arithmetic operations. Define functions and by and respectively, which perform the addition and subtraction operations on unsigned integers. If , then the addition instruction causes an overflow. When , the subtraction instruction again cuases an overflow. The modularization by in these definitions ensure that the result from the functions stay within even when an overflow occurs.
An overflow occurs in subtracting from occurs if and only if . This condition is easy to check. For the addition operation:
Proof. Without loss of generality, assume that . If , we have that , so that Claim () therefore follows.
To prove claim (), we verify its contraposition. Suppose that . Then we have that so that and . The result therefore follows. ◻
Given a signed integer encoded by the two’s complement method, we sometimes need to find the encoded value of the signed integer with an opposite sign. The defined by does such task.
Proof. Pick arbitrarily. Then ◻
The subtraction instruction can be created by combining the addition and the instructions, because:
Proof. ◻
An interesting feature of the two’s complement method is that the unsigned addition of the signed integers encoded by it delivers the correct result in the encoded form, as long as an overflow does not occur.
Proof. By the definitions of and , we have that Under the hypothesis of claim (), the right-hand side of this equality is equal to . Claim () follows by Proposition .
Under the hypothesis of claim (), it holds that , so that where the last equality holds by (). Claim () follows by Proposition .
Under the hytpothesis of claim (), it holds that , so that Claim () follows by Proposition . ◻
The two’s complement encoding also works with the unsigned subtraction.
Proof. By the definitions of and , we have that Under the hypothesis of claim (), the right-hand side of this equality is equal to . Claim () follows by Proposition .
Under the hypothesis of claim (), it holds that , so that where the last equality holds by (). Claim () follows by Proposition .
Under the hytpothesis of claim (), it holds that , so that Claim () follows by Proposition . ◻
Multiplication
We now consideer another arithmetic operation, multiplication. When we take a pair of unsigned -bit integers, the binary representation of their product can be as long as bits. To eliminate or reduce the chance of overflows, we can perform multiplication using a longer bitwidth than the input integers. Let be a natural number no less than , and define by Complete avoidance of overflows in unsigned multiplication requires that . But some CPU multiplication instructions are designed for .
Addition and subtraction combined with the two’s complement encoding work well for signed addition and subtraction. Because multiplication can be viewed as repeated additions or subtractions, it is not surprising to see the same kind of properties for the multiplication operation. But the multiplication operation is subtly different from addition and subtraction because the bitwidth, , of values of which we want to take the product can be smaller than the bitwidth, , of the values the multiplication operator handles. The two’s complement of a signed integer depends on the bitwidth to work with.
Let be an -bit unsigned integer with the most significant bit . A -bit unsigned integer each of whose most significant bits is and the remining bits are is called the sign expansion of . Note that is 1 if and only if . Define a function by
Proof. Suppose that . Then it follows from Proposition that and that , as . Thus, the equality in question holds. Suppose instead that . Then we have that Because , we also have that The equality in question again holds. ◻
The unsigned addition and subtraction combinaed with the two’s complement encoding work well in signed addition and subtraction. We try the same strategy in multiplication.
Proof. In general, we have that The result follows by Proposition . ◻
Division
Define a function where This function calculates the quotient and remaindere in division of the first parameter by the second parameter, when the division is possible, i.e., the divisor is nonzero and the quotient fits in the W-bit unsigned integer range. The third return value of the function is binary and equal to zero if and only if the division is possible. The values of and are meaningless when .
When , the quotient is always in , provided that the divisor is not zero. In such case, becomes 1 if and only if the divisor is zero. We below devise signed division of a -valued dividend by a -valued divisor using .
Let and be integers such that . Also, let and be the quotient and the remainder in the division of by . Then the quotient and the remainder in the division of by (rounded toward zero) can be written as and
Given () and (), we can perform signed division operation through unsigned division of the absolute value of the dividend by the absolute value of the divisor. Define by where is the most significant bit of , which is one if and only if .
Proof. If , then the most significant bit of is zero, the result clearly holds. If , on the other hand, the most significant bit of is one. We have that where the second equality holds by Proposition . The result therefore follows. ◻
Define by where and
Proof. If , then it holds that , so that and , as claimed by the proposition.
Suppose that . Then () is equivalent to . We can think of four possibilities about the values of and : (a) and ; (b) and ; (c) and ; and (d) and . When () is satisfied, it is tedious but easy to verify that the claim holds in each of these four cases. If () instead is violated, it clearly holds that , the claim again holds. ◻