Editing Binary number (section)

==Binary arithmetic==
[[Arithmetic]] in binary is much like arithmetic in other [[positional notation]] [[numeral system]]s. Addition, subtraction, multiplication, and division can be performed on binary numerals.

===Addition===
{{main | Adder (electronics)}}
[[Image:Half Adder.svg|thumbnail|200px|right|The [[circuit diagram]] for a binary [[Adder (electronics)|half adder]], which adds two bits together, producing sum and carry bits]]

The simplest arithmetic operation in binary is addition. Adding two single-digit binary numbers is relatively simple, using a form of carrying:

:0 + 0 → 0
:0 + 1 → 1
:1 + 0 → 1
:1 + 1 → 0, carry 1 (since 1 + 1 = 2 = 0 + (1 × 2<sup>1</sup>)  )
Adding two "1" digits produces a digit "0", while 1 will have to be added to the next column. This is similar to what happens in decimal when certain single-digit numbers are added together; if the result equals or exceeds the value of the radix (10), the digit to the left is incremented:

:5 + 5 → 0, carry 1 (since 5 + 5 = 10 = 0 + (1 × 10<sup>1</sup>)  )
:7 + 9 → 6, carry 1 (since 7 + 9 = 16 = 6 + (1 × 10<sup>1</sup>)  )

This is known as ''carrying''. When the result of an addition exceeds the value of a digit, the procedure is to "carry" the excess amount divided by the radix (that is, 10/10) to the left, adding it to the next positional value. This is correct since the next position has a weight that is higher by a factor equal to the radix. Carrying works the same way in binary:

   {{brown|1 1 1 1 1    (carried digits)}}
     0 1 1 0 1
 +   1 0 1 1 1
 -------------
 = 1 0 0 1 0 0 = 36

In this example, two numerals are being added together: 01101<sub>2</sub> (13<sub>10</sub>) and 10111<sub>2</sub> (23<sub>10</sub>). The top row shows the carry bits used. Starting in the rightmost column, 1 + 1 = 10<sub>2</sub>. The 1 is carried to the left, and the 0 is written at the bottom of the rightmost column. The second column from the right is added: 1 + 0 + 1 = 10<sub>2</sub> again; the 1 is carried, and 0 is written at the bottom. The third column: 1 + 1 + 1 = 11<sub>2</sub>. This time, a 1 is carried, and a 1 is written in the bottom row. Proceeding like this gives the final answer 100100<sub>2</sub> (36<sub>10</sub>).

When computers must add two numbers, the rule that:
x [[Exclusive or|xor]] y = (x + y) [[Modulo operation|mod]] 2
for any two bits x and y allows for very fast calculation, as well.

====Long carry method====
A simplification for many binary addition problems is the "long carry method" or "Brookhouse Method of Binary Addition". This method is particularly useful when one of the numbers contains a long stretch of ones. It is based on the simple premise that under the binary system, when given a stretch of digits composed entirely of {{varserif|n}} ones (where {{varserif|n}} is any integer length), adding 1 will result in the number 1 followed by a string of {{varserif|n}} zeros. That concept follows, logically, just as in the decimal system, where adding 1 to a string of {{varserif|n}} 9s will result in the number 1 followed by a string of {{varserif|n}} 0s:

      Binary                        Decimal
     1 1 1 1 1     likewise        9 9 9 9 9
  +          1                  +          1
   ———————————                   ———————————
   1 0 0 0 0 0                   1 0 0 0 0 0

Such long strings are quite common in the binary system.  From that one finds that large binary numbers can be added using two simple steps, without excessive carry operations. In the following example, two numerals are being added together: 1 1 1 0 1 1 1 1 1 0<sub>2</sub> (958<sub>10</sub>) and 1 0 1 0 1 1 0 0 1 1<sub>2</sub> (691<sub>10</sub>), using the traditional carry method on the left, and the long carry method on the right:

 Traditional Carry Method                       Long Carry Method
                                 vs.
   {{brown|1 1 1   1 1 1 1 1      (carried digits)   1 ←     1 ←}}            carry the 1 until it is one digit past the "string" below
     1 1 1 0 1 1 1 1 1 0                       <s>1 1 1</s> 0 <s>1 1 1 1 1</s> 0  cross out the "string",
 +   1 0 1 0 1 1 0 0 1 1                   +   1 0 <s>1</s> 0 1 1 0 0 <s>1</s> 1  and cross out the digit that was added to it
 ———————————————————————                    ——————————————————————
 = 1 1 0 0 1 1 1 0 0 0 1                     1 1 0 0 1 1 1 0 0 0 1

The top row shows the carry bits used. Instead of the standard carry from one column to the next, the lowest-ordered "1" with a "1" in the corresponding place value beneath it may be added and a "1" may be carried to one digit past the end of the series.  The "used" numbers must be crossed off, since they are already added. Other long strings may likewise be cancelled using the same technique. Then, simply add together any remaining digits normally. Proceeding in this manner gives the final answer of 1 1 0 0 1 1 1 0 0 0 1<sub>2</sub> (1649<sub>10</sub>).  In our simple example using small numbers, the traditional carry method required eight carry operations, yet the long carry method required only two, representing a substantial reduction of effort.

====Addition table====

{| class="wikitable" style="text-align:center"
|-
! style="width:1.5em" |
! style="width:1.5em" | 0
! style="width:1.5em" | 1
|-
! 0
| 0
| 1
|-
! 1
| 1
| 10
|}

The binary addition table is similar to, but not the same as, the [[Logical disjunction#Truth table|truth table]] of the [[logical disjunction]] operation <math>\lor</math>. The difference is that <math>1 \lor 1 = 1</math>, while <math>1+1=10</math>.

=== Subtraction ===
{{further|signed number representations|two's complement}}

[[Subtraction]] works in much the same way:

:0 − 0 → 0
:0 − 1 → 1, borrow 1
:1 − 0 → 1
:1 − 1 → 0
Subtracting a "1" digit from a "0" digit produces the digit "1", while 1 will have to be subtracted from the next column. This is known as ''borrowing''. The principle is the same as for carrying. When the result of a subtraction is less than 0, the least possible value of a digit, the procedure is to "borrow" the deficit divided by the radix (that is, 10/10) from the left, subtracting it from the next positional value.

     *   * * *   (starred columns are borrowed from)
   1 1 0 1 1 1 0
 −     1 0 1 1 1
 ----------------
 = 1 0 1 0 1 1 1

   *             (starred columns are borrowed from)
   1 0 1 1 1 1 1
 –   1 0 1 0 1 1
 ----------------
 = 0 1 1 0 1 0 0

Subtracting a positive number is equivalent to ''adding'' a [[negative number]] of equal [[absolute value]]. Computers use [[signed number representations]] to handle negative numbers—most commonly the [[two's complement]] notation. Such representations eliminate the need for a separate "subtract" operation. Using two's complement notation, subtraction can be summarized by the following formula:

: {{math|1=A − B = A + not B + 1}}

===Multiplication===<!-- This section is linked from [[Binary-coded decimal]] -->
[[Multiplication]] in binary is similar to its decimal counterpart. Two numbers {{varserif|A}} and {{varserif|B}} can be multiplied by partial products: for each digit in {{varserif|B}}, the product of that digit in {{varserif|A}} is calculated and written on a new line, shifted leftward so that its rightmost digit lines up with the digit in {{varserif|B}} that was used. The sum of all these partial products gives the final result.

Since there are only two digits in binary, there are only two possible outcomes of each partial multiplication:
* If the digit in {{varserif|B}} is 0, the partial product is also 0
* If the digit in {{varserif|B}} is 1, the partial product is equal to {{varserif|A}}

For example, the binary numbers 1011 and 1010 are multiplied as follows:

            1 0 1 1   ({{varserif|A}})
          × 1 0 1 0   ({{varserif|B}})
          ---------
            0 0 0 0   ← to the rightmost 'zero' in {{varserif|B}}
    +     1 0 1 1     ← to the next 'one' in {{varserif|B}}
    +   0 0 0 0
    + 1 0 1 1
    ---------------
    = 1 1 0 1 1 1 0

Binary numbers can also be multiplied with bits after a [[binary point]]:

                1 0 1 . 1 0 1     {{varserif|A}} (5.625 in decimal)
              × 1 1 0 . 0 1       {{varserif|B}} (6.25 in decimal)
              -------------------
                    1 . 0 1 1 0 1   ← to a 'one' in {{varserif|B}}
      +           0 0 . 0 0 0 0     ← to a 'zero' in {{varserif|B}}
      +         0 0 0 . 0 0 0
      +       1 0 1 1 . 0 1
      +     1 0 1 1 0 . 1
      ---------------------------
      =   1 0 0 0 1 1 . 0 0 1 0 1 (35.15625 in decimal)

See also [[Booth's multiplication algorithm]].

====Multiplication table====
{| class="wikitable" style="text-align:center"
|-
! style="width:1.5em" |
! style="width:1.5em" | 0
! style="width:1.5em" | 1
|-
! 0
| 0
| 0
|-
! 1
| 0
| 1
|}

The binary multiplication table is the same as the [[Logical conjunction#Truth table|truth table]] of the [[logical conjunction]] operation <math>\land</math>.

===Division===
{{See also|Division algorithm#Integer division (unsigned) with remainder}}

[[Long division]] in binary is again similar to its decimal counterpart.

In the example below, the [[divisor]] is 101<sub>2</sub>, or 5 in decimal, while the [[Division (mathematics)|dividend]] is 11011<sub>2</sub>, or 27 in decimal. The procedure is the same as that of decimal [[long division]]; here, the divisor 101<sub>2</sub> goes into the first three digits 110<sub>2</sub> of the dividend one time, so a "1" is written on the top line. This result is multiplied by the divisor, and subtracted from the first three digits of the dividend; the next digit (a "1") is included to obtain a new three-digit sequence:

               1
         ___________
 1 0 1   ) 1 1 0 1 1
         − 1 0 1
           -----
           0 0 1

The procedure is then repeated with the new sequence, continuing until the digits in the dividend have been exhausted:

              1 0 1
        ___________
 1 0 1  ) 1 1 0 1 1
        − 1 0 1
          -----
              1 1 1
          −   1 0 1
              -----
              0 1 0

Thus, the [[quotient]] of 11011<sub>2</sub> divided by 101<sub>2</sub> is 101<sub>2</sub>, as shown on the top line, while the remainder, shown on the bottom line, is 10<sub>2</sub>. In decimal, this corresponds to the fact that 27 divided by 5 is 5, with a remainder of 2.

Aside from long division, one can also devise the procedure so as to allow for over-subtracting from the partial remainder at each iteration, thereby leading to alternative methods which are less systematic, but more flexible as a result.

===Square root===
The process of [[Methods of computing square roots#Binary numeral system (base 2)|taking a binary square root]] digit by digit is essentially the same as for a decimal square root but much simpler, due to the binary nature.  First group the digits in pairs, using a leading 0 if necessary so there are an even number of digits.  Now at each step, consider the answer so far, extended with the digits 01.  If this can be subtracted from the current remainder, do so.  Then extend the remainder with the next pair of digits.  If you subtracted, the next digit of the answer is 1, otherwise it's 0.

                              1                          1  1                       1  1  0                   1  1  0  1
  -------------             -------------              -------------              -------------             -------------
 √ 10 10 10 01             √ 10 10 10 01              √ 10 10 10 01              √ 10 10 10 01             √ 10 10 10 01
                            - 1                        - 1                        - 1                       - 1         
 Answer so far is 0,        ----                       ----                       ----                      ----        
 extended by 01 is 001,       1 10                       1 10                       1 10                      1 10
 this CAN be subtracted                                - 1 01                     - 1 01                    - 1 01
 from first pair 10,       Answer so far is 1,         -------                    -------                   -------
 so first digit of         extended by 01 is 101,           1 10                       1 10 01                   1 10 01
 answer is 1.              this CAN be subtracted                                                              - 1 10 01
                           from remainder 110, so     Answer so far is 11,       Answer so far is 110,         ----------
                           next answer digit is 1.    extended by 01 is 1101,    extended by 01 is 11001,              0
                                                      this is TOO BIG to         this CAN be subtracted
                                                      subtract from remainder    from remainder 11001, so           Done!
                                                      110, so next digit of      next digit of answer is 1.
                                                      answer is 0.