Method of complements

Introduction

The method of complements is an algorithm to subtract two numbers. It uses only addition of positive numbers. This method is not particularly useful for decimal numbers, but it is very useful in binary arithmetic used in computer systems. Here we want algorithms and digital circuitry to be as simple as possible, only dealing with bits and not, for instance, with minus signs in the representation of negative numbers. The method of complements for addition/subtraction and the two's complement for representing negative (binary) numbers, happen to be particularly suitable to fulfill that goal.

JavaScript uses two's complement representation and the method of complements in the background, when performing bitwise logic operations on numbers. More about this below in the section Two's complement in JavaScript.

To explain the fundamentals of complements, we will start with numbers in the decimal numeral system.

Complements

The method uses complements of a digit to a digit. The i's complement of a digit d is what must be added to that digit d to get i. The compliment itself is also a digit. We can also write this as:

So for example, the nines' complement of 9 is 0, the nines' complement of 8 is 1, the nines' complement of 7 is 2, the nines' complement of 6 is 3, the nines' complement of 5 is 4 and vice versa.

We used subtraction to calculate the nines' complement of 2. We can also view this as how many times do we need to add one to 2, to get 9, which is 7 times. We can capture this in an algorithm as shown in the next JavaScript:

function iComplementOfd (i,d) {
  let complement = 0;
  for(let t=d; t<i; t++) { complement++; }
  return complement;
}	

console.log(iComplementOfd (9,7)); // logs: 2
console.log(iComplementOfd (9,4)); // logs: 5

To form the nines' complement of a number with multiple digits, each digit needs to be replaced by its nines' complement. We can also write this as:

For example:

218 [x]
781 [nines' complement of x]
===
999 [x + nines' complement of x]

The ten's complement of 218 would be 1000 − 218 = 782. So, the ten's complement is the nines' complement plus 1. The radix complement is the ten's complement in the decimal system, since the base or radix of the decimal system is ten. The diminished radix complement is the radix complement minus 1. In the decimal system the diminished radix complement is the nines' complement. In general:

Also note that:

Subtracting two numbers by only adding positive numbers

Now let's see how we can use this to subtract two numbers by only adding positive numbers.

  185 [x]
− 329 [y]
  ===

  873 [x]
− 218 [y]
  ===

  185 [x]
+ 670 [nines' complement of y]
  ===
  855

  873 [x]
+ 781 [nines' complement of y]
  ===
 1654

  185
+ 670
  ===
  855
− 999
  === 
 −144 [= negated nines' complement
       of 855:
       855 − 999]

  873
+ 781
  ===
 1654 [Cancel the leading "1" digit:
−1000            this equals − 1000]
 ====
  654
+   1 [− 1000 + 1 = − 999]
  ===
  655  

185 − 329 = −144

873 − 218 = 655 

Now, this all may look ridiculously redundant, but just hang in there, things will make sense soon. We can describe the above method in two alternative implementations; one involving the nines' complement and one involving the ten's complement.

x − y:

1. Add x and the nines' complement of y.
2. If a left-most carry out appeared, perform an end-around carry. The result is the correct answer.
3. If no left-most carry out appeared, the correct answer is the result's negated nines' complement (the result is negative).

x − y:

1. Add x and the ten's complement of y.
2. If a left-most carry out appeared, cancel/ignore it. The result is the correct answer
3. If no left-most carry out appeared, the correct answer is the result's negated ten's complement (the result is negative).

The second implementation involving the radix complement is used in the popular two's complement negative binary number representation, which will be discussed further below.

  99999 [x]
−   999 [y]
  =====

1 1111  [carry]
  99999 [x]
+ 99000 [nines' complement of 00999]
+     1 [nines' complement +1 is ten's complement]
  =====
  99000

The left-most carry out "1" is ignored. Thus 99 999 − 999 = 99 000.

  185 [x]
− 329 [y]
  =====

  1   [carry]
  185 [x]
+ 670 [nines' complement of y]
+   1 [ten's complement = nines' complement + 1]
  ===
  856
      [No left-most carry out appeared:]
  143 [nines' complement of 856]
+   1 [+1 to get the ten's complement of 856] 
  ===
 −144 [negated ten's complement]
 
Thus 185 − 329 = −144.

In binary

As mentioned, the method of complements is especially useful in binary (radix 2) arithmetic used by computer systems. This is because the diminished radix complement, the ones' complement in binary, is very easily obtained by inverting each bit (changing '0' to '1' and vice versa). This is the same as performing a bitwise NOT.

  0110 0100  [x, equals decimal 100]
− 0001 0110  [y, equals decimal 22]
  =========

1 11     1   [carry]
  0110 0100  [x]
+ 1110 1001  [bitwise NOT y = ones' complement]
+         1  [bitwise NOT y + 1 = two's complement]
  =========
  0100 1110  [78]

The left-most carry out "1" is ignored. Thus 0110 0100 − 0001 0110 = 0100 1110 (100 − 22 = 78).

Signed number representations

In the example above the subtraction 100 − 22 is performed in binary. We can also perceive this as an addition of 100 and negative 22. If we look at it like that, and perceive the ones' complement or the two's complement of a number as the representation of the number's negative counterpart, we have a simple algorithm to add numbers, positive or negative, that only deals with bits (minus signs do not play a role in the algorithm). This is exactly why ones' complement and more predominantly two's complement are used as signed number representations in binary.

In the next sections ones' complement and two's complement signed number representations will be explained in more detail. But we will start with the sign-magnitude representation, the simplest form of signed digital number representation. All three representations have in common that positivity or negativity of the number is not denoted by a "+" or "−" sign, but by the left-most bit, the so called "sign bit".

Sign-and-magnitude representation

The simplest method to represent both positive and negative numbers in binary is the sign-and-magnitude representation in which the left-most bit is used as a sign bit. The sign bit set to 0 represents a positive number, the sign bit set to 1 represents a negative number. The remaining bits in the number indicate the magnitude (or absolute value).

As a consequence, sign-magnitude representation allows two ways to represent zero. For example in an eight-bit byte both 00000000 (0) and 10000000 (−0) represent zero.

With sign-magnitude representation the sign bit requires a prior evaluation and special treatment in an arithmetic algorithm. For example, a straightforward execution of an addition or subtraction algorithm with a negative number and a positive number does not necessarily yield a correct result. Also carries from the magnitude part may propagate into the sign bit, interfering with the sign bit.

        1   [borrow] 
  0000 0101 [5]
− 0000 0011 [3]
  =========
  0000 0010 [2]  

       111  [carry] 
  0000 0101 [5]
+ 1000 0011 [-3]
  =========
  1000 1000 [-8]  This is clearly the wrong answer.

  1         [carry] 
  0100 0000 [64]
+ 0100 0000 [64]
  =========
  1000 0000 [-0]  This is clearly the wrong answer.

The two representations of zeros and the special treatment of the sign bit make that arithmetic algorithms and digital circuitry become relatively complex, and therefore this representation is not the most common way of representing signed binary numbers.

Floating-point numbers use the sign-magnitude representation for the significand.

Ones' complement representation

In the ones' complement representation negative binary numbers are represented as the ones' complement of their positive counterpart. To get the ones' complement, a bitwise NOT operation can be applied to the positive counterpart. The bit sign also flips from 0 to 1 or vice versa.

Like sign-and-magnitude representation, this representation has two ways to represent zero.

Now we can use addition and subtraction algorithms without a prior evaluation of the bit sign. Because negative numbers are represented as the diminished radix complement (ones complement) we can use the earlier discussed implementation involving the diminished radix complement of the method of complements.

If, for instance, we add a positive and a negative number, we add the positive number and the ones complement of the positive counterpart of the negative number. If a left-most carry out or borrow out appears, an "end-around carry" or an "end-around borrow" needs to be performed. If no left-most carry or borrow out appears, the result is the ones' complement of the correct answer (a negative number).

In an end-around borrow the left-most borrow out needs to be subtracted from the right-most bit.

1 11     1   [carry]
  0110 0100  [100]
+ 1110 1001  [−22]
+         1  [end-around carry]
  =========
  0100 1110  [78]

     1 1    [carry]
  0000 0110 [  6]
+ 1110 1100 [−19]
=========== 
  1111 0010 [−13]   The correct result

1 111   11  [borrow]
  0000 0110 [  6]
− 0001 0011 [ 19]
=========== 
1 1111 0011 [−12]   A borrow 'overflowed' to the left.
− 0000 0001 [  1]   Subtract this left-most borrow out from the result: the end-around borrow.
=========== 
  1111 0010 [−13]   The correct result (6 − 19 = -13)

Although ones' complement representation makes things a little less complex than sign-and-magnitude representation, ones' complement representation still has the nasty property of allowing two representations of zeros. Also end-around carries and end-around borrows still need extra functionality to be built in algorithms or binary circuits.

Two's complement representation

In the two's complement representation negative binary numbers are represented as the two's complement of their positive counterpart. To get the two's complement, add 1 to the ones' complement.

With the ones' complement representation it is obvious that the ones' complement of a positive number is the corresponding negative number, and reversed, the ones' complement of a negative number is the corresponding positive number. But this also holds for the two's complement representation ^[2].

0000 0101 [5]
1111 1010 [ones' complement]
1111 1011 [-5]

1111 1011 [-5]
0000 0100 [ones' complement]
0000 0101 [5]

Again, the left-most bit can be interpreted as a sign bit (actually, it could also be interpreted as a bit with its regular place value, but then negated).

In practice the number of available bits (n) to represent a number is restricted to a maximum. In the examples here an eight-bit byte to store a number is assumed. Numbers that need more bits overflow to the left. The overflow is ignored (canceled).

Two's complement representation has only one way to represent zero, since the two's complement of zero is zero when the overflow is ignored:

 0000 0000 [0]
 1111 1111 [ones' complement]
10000 0000 [ones' complement + 1]
 0000 0000 [0]

Now there is only one way to represent zero, so an "extra" number must pop up somewhere else. The largest integer that can be represented is 2⁷ − 1 = 127. The most negative number representable is −128. The two's complement of this most negative number equals itself. Hence, there is one "extra" negative number for which the two's complement does not provide its positive counterpart.

0111 1111 [127]

1000 0000 [-128]
0111 1111 [ones' complement]
1000 0000 [ones' complement + 1 = -128]

With the two's complement representation the implementation involving the radix complement of the method of complements can be used. A left-most bit 1 carry or borrow out is automatically canceled because the overflow is ignored. Addition of positive and/or negative numbers all use the same algorithm. A negative result is actually the negated two's complement.

So, with two's complement representation only one zero representation exists, and end-around carries or end-around borrows do not occur. This means a simple implementation of algorithms or digital circuits, which is the reason for its widespread popularity.

For some examples:

     1 111  [carry]
  0000 1111 [15]
+ 0000 0101 [5]
  =========
  0001 0100 [20]

            [borrow]
  0000 1111 [15]
− 0000 0101 [5]
  =========
  0000 1010 [10]

1 1111 111  [carry] The left-most overflow carry is ignored
  0000 1111 [15]
+ 1111 1011 [−5] Two's complement of [5]
  =========
  0000 1010 [10]

1 1111 11   [borrow] The left-most overflow borrow is ignored
  0000 0101 [5]
− 0000 1111 [15]
  =========
  1111 0110 [−10] Two's complement of [−10] is 0000 1010

         1  [carry]
  0000 0101 [5]
+ 1111 0001 [−15]
  =========
  1111 0110 [−10]

1 111   11  [carry]
  1111 0001 [−15] 
+ 1111 1011 [−5]
  =========
  1110 1100 [-20]

1 1110 000  [borrow]
  0000 1111 [15]
− 1111 1011 [−5]
  =========
  0001 0100 [20]

When using two's complement representation for binary numbers, the subtracting algorithm also works for subtracting a larger number from a smaller number.

1 1111 11   [borrow]
  0000 0101 [5]
− 0000 1111 [15]
  =========
  1111 0110 [−10]

Overflow

The result of adding or subtracting two operands with n bits may be outside the range of −(2^n − 1) to 2^n − 1 − 1. When this occurs, we speak of overflow. The obtained result is invalid! This means that an addition or subtraction algorithm or digital circuit needs to test for possible overflow. This functionality is called an overflow indicator or overflow flag.

For adding there are 3 possible situations:

• If both sign bits are 0 (addition of two positive numbers), a carry 1 into the sign bits position propagates to the sign bit of the result, making it negative, which is false. The correct sum is outside the range, and so the outcome of the addition (a negative number) is invalid.
• If both sign bits are 1 (addition of two negative numbers), the opposite of both sign bits 0 (addition of two positive numbers) occurs. A carry 0 into the sign bits position changes the sign of the result. The correct result is outside the range, and so the outcome of the addition is invalid. A carry 1 does not change the sign of the result and is simply propagated to the left in the carry row where it is ignored.
• If the sign bits of both operands differ (addition of a positive and a negative number), the result can never be outside the range and therefore will always be valid. The maximum possible result is within the range (for an 8 bit number: −1 + 127 = 126) and the minimum possible result is within range (for an 8 bit number: 0 + −128 = −128).

Given these three possible situations for addition we can extract two criteria, each to detect overflow for addition:

• With addition overflow occurs if and only if both operands have the same sign and the result has an opposite sign.
• With addition overflow occurs if and only if the left-most two bits of the carry row are not equal. This can be tested by applying an XOR operation on both carry bits.

0 1111 111  [carry] the left-most two bits are not equal
  0111 1111 [127]
+ 0011 1111 [ 63]
  =========
  1011 1110 [−66] invalid!

  190 is outside the permitted range of −128 to 127.  

1 0  1 111  [carry] the left-most two bits are not equal
  1000 1111 [−113]
+ 1000 1111 [−113]
  =========
  0001 1110 [30] invalid!
  
  −226 is outside the permitted range of −128 to 127.

Two criteria, each to detect overflow for subtraction:

• With subtraction overflow occurs if and only if both operands have different signs and the result has the same sign as the subtrahend.
• The same way as for addition, with subtraction overflow occurs if and only if the left-most two bits of the borrow row are different.

Two's complement in JavaScript

In JavaScript, values of the number data type are 64 bits Floating-point numbers. They do not use two's complement representation. Sign-magnitude representation is used for the significand, the exponent is represented as a biased exponent. Not even binary numbers use the two's complement.

console.log(0b1111); // logs: 15 // and not -1

However, bitwise operations in JavaScript are performed on 32 bits binary numbers using the two's complement representation. JavaScript converts floating points to 32 bits two's complement signed integers, performs the bitwise operation, and then converts the result back to 64 bits floating points.

/*
*  ~5 =
*  00000000000000000000000000000101 = 5 →
*  11111111111111111111111111111010 = ~5 →
* -00000000000000000000000000000110 = -6.
*/
console.log(~5);  // logs: -6
console.log(~0b0101);  // logs: -6
console.log((~5).toString(2));  // logs: "-110"

To prevent the engine from using the two's complement representation when converting back to a 64 bits floating point, you can use a zero fill right shift of zero (>>>0).

console.log((~5)>>>0); // logs: 4294967290
console.log(((~5)>>>0).toString(2));       // logs: "11111111111111111111111111111010" // (the ones' complement of 5)
console.log((((~5)>>>0) + 1).toString(2)); // logs: "11111111111111111111111111111011" // (the two's complement of 5)

console.log((-5).toString(2)); // logs: "-101" // 
console.log(((-5)>>>0).toString(2));  // logs: "11111111111111111111111111111011" // (the two's complement of 5)

The next example shows a function that adds two numbers without using any arithmetic operations. Only bitwise logic operations are used to perform the addition. The used algorithm adds bitwise, bit by bit, as displayed in all previous examples. It uses only bits, possible minus signs do not take part in the algorithm. Yet, this algorithm handles negative operands just fine. This is because in the background the JavaScript bitwise operators convert negative operands to two's complement numbers.

function add(a, b) {
  while (b != 0) { // Iterate until carry is 0
    let carry = a & b; // bitwise AND to get the carry (common set bits, i.e. set 1 where both bits are set 1)  
    a = a ^ b; // bitwise XOR to get the sum (set 1 where only one bit is set 1). This is also the new operand a for the next iteration.
    b = carry << 1; // shift the carry-row one to the left to get the new operand b for the next iteration.
  }
  return a;
}

console.log(add(5,15)); // logs: 20
console.log(add(15,-5)); // logs: 10
console.log(add(-5,-15)); // logs: -20
console.log(add(-5,7)); // logs: 2

                    1 1110 [carry]
                      1011 [-5]
                     +0111 [ 7]
                      ====
                      0010 [ 2]
					  

                   a: 1011
                   b: 0111
                      ====
 
carry = a & b:        0011
sum = a = a ^ b:      1100
      b = carry << 1: 0110
	  
carry = a & b:        0100
sum = a = a ^ b:      1010
      b = carry << 1: 1000

carry = a & b:        1000
sum = a = a ^ b:      0010  <=
      b = carry << 1: 0000	  

JavaScripts to convert numbers

function twosComplementDec2Bin(decNum, bitCount = 8) {
   if (bitCount > 32) { return "too many bits"; } 
   if (decNum >= Math.pow(2,bitCount-1)) { return "number outside range"; }
   let binNum = (decNum >>> 0).toString(2);	
   return binNum.padStart(bitCount, '0').slice(-bitCount);
}

console.log(twosComplementDec2Bin(-128,12)); // logs: "111110000000"
console.log(twosComplementDec2Bin(-127)); // logs: "10000001"
console.log(twosComplementDec2Bin(-1,3)); // logs: "111"
console.log(twosComplementDec2Bin(0)); // logs: "00000000"
console.log(twosComplementDec2Bin(127)); // logs: "01111111"
console.log(twosComplementDec2Bin(128,8)); // logs: undefined

function twosComplementBin2Dec(binNum) {
   if (binNum[0] === "1") {
      let twosComplementBinNum = ((~Number(`0b${binNum}`)>>>0) + 1).toString(2).slice(-binNum.length);
      return -Number(`0b${twosComplementBinNum}`);
   }
   else { return Number(`0b${binNum}`); }	
}

console.log(twosComplementBin2Dec("111")); // -1
console.log(twosComplementBin2Dec("10000000")); // -128
console.log(twosComplementBin2Dec("01111111")); // 127

function bin2dec(binNum){
   return Number(`0b${binNum}`);
}

console.log(bin2dec("111")); // 7