Tuesday, August 16, 2011

Binary Arithmetic

My notes on Binary Arithmetic




Binary Addition

  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 0, and carry 1 to the next more significant bit
  • 1 + 1 + 1 = 1, and carry 1 to the next more significant bit


For example,


00011010 + 00001100 = 00100110                1  1carries
  0  0  0  1  1  0  1  0   =   26(base 10)
+ 0  0  0  0  1  1  0  0

   =   12(base 10)
  0  0  1  0  0  1  1  0   =   38(base 10)

00010011 + 00111110 = 01010001         1  1  1  1  1carries
  0  0  0  1  0  0  1  1   =   19(base 10)
+ 0  0  1  1  1  1  1  0

   =   62(base 10)
  0  1  0  1  0  0  0  1   =   81(base 10)




Note:  The rules of binary addition (without carries) are the same as the truths of the XOR gate.


Binary Subtraction

  • 0 - 0 = 0
  • 0 - 1 = 1, and borrow 1 from the next more significant bit
  • 1 - 0 = 1
  • 1 - 1 = 0
For example,


00100101 - 00010001 = 00010100                0borrows
  0  0  1 10  0  1  0  1   =   37(base 10)
- 0  0  0  1  0  0  0  1

   =   17(base 10)
  0  0  0  1  0  1  0  0   =   20(base 10)

00110011 - 00010110 = 00011101            0 10  1borrows
  0  0  1  1  0 10  1  1   =   51(base 10)
- 0  0  0  1  0  1  1  0

   =   22(base 10)
  0  0  0  1  1  1  0  1   =   29(base 10)


When a 0 borrows 1 from say ith left bit, then 1 at ith position becomes 0 and all 0's positioned from the ith to borrowing 0 become 1.




Ones Complement


The one's complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number (swapping 0's for 1's and vice-versa). The one's complement of the number then behaves like the negative of the original number in most arithmetic operations. However, unlike two's complement, these numbers could not have widespread use because of issues like negative zero, end-around borrow, etc.

Addition of signed numbers in one's complement is performed using binary addition with end-around carry. If there is a carry out of the most significant bit of the sum, this bit must be added to the least significant bit of the sum.

To add decimal 17 to decimal -8 in 8-bit one's complement:

 0  0  0  1  0  0  0  1   =   17(base 10)
 1   1   1  1  0  1   1   1

   =   -8(base 10)
  0  0  0  0  1  0  0  0   


                            +   1

   
  0  0  0  0  1  0  0  1   =   9(base 10)



Two's complement


Ones complement + 1


The two's complement of the number then behaves like the negative of the original number in most arithmetic, and it can coexist with positive numbers in a natural way.



To calculate the 2's complement of an integer, invert the binary equivalent of the number by changing all of the ones to zeroes and all of the zeroes to ones (also called 1's complement), and then add one.


For example,
0001 0001(binary 17)   =   1110 1111(two's complement -17)
NOT(0001 0001) = 1110 1110  (Invert bits)
1110 1110 + 0000 0001 = 1110 1111  (Add 1)




2's Complement Addition

Two's complement addition follows the same rules as binary addition.
For example,
5 + (-3)  =  2     0000 0101 = +5
+ 1111 1101

 = -3
  0000 0010 = +2




2's Complement Subtraction

Two's complement subtraction is the binary addition of the minuend to the 2's complement of the subtrahend (adding a negative number is the same as subtracting a positive one).
For example,
7 - 12  =  (-5)     0000 0111 = +7
+ 1111 0100

 = -12
  1111 1011 = -5


Note - in 2's compliment subtraction - if there is a carry over from the MSB, ignore that.

Example :: 1010 - 0001 = 1001


Positive Numbers
Positive 2's complement numbers are represented as the simple binary.
Negative Numbers
Negative 2's complement numbers are represented as the binary number that when added to a positive number of the same magnitude equals zero.
Integer2's Complement
SignedUnsigned
550000 0101
440000 0100
330000 0011
220000 0010
110000 0001
000000 0000
-12551111 1111
-22541111 1110
-32531111 1101
-42521111 1100
-52511111 1011
Note:  The most significant (leftmost) bit indicates the sign of the integer; therefore it is sometimes called the sign bit.
If the sign bit is zero,
then the number is greater than or equal to zero, or positive.
If the sign bit is one,
then the number is less than zero, or negative.

Negative zero

0 = 0000 0000
~0 = 1111 1111



Negative zero is the condition where all bits in a signed word are on (1). This follows the 1's complement rules that a value is negative when the left-most bit is 1, and that a negative number is the bit complement of the number's magnitude. The value also behaves as zero when computing. Adding or subtracting negative zero to/from another value produces the original value.



Adding negative zero:

  0001 0110     22
+ 1111 1111     −0
===========   ====
1 0001 0101     21    An end-around carry is produced.
+ 0000 0001      1
===========   ====
  0001 0110     22    The correct result (22 + (−0) = 22)


Subtracting negative zero:
  0001 0110     22
− 1111 1111     −0
===========   ====
1 0001 0111     23    An end-around borrow is produced.
- 0000 0001      1
===========   ====
  0001 0110     22    The correct result (22 − (−0) = 22)





XOR

bitwise exclusive OR takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 OR only the second bit is 1, but will be 0 if both are 1 or both are 0. This is equivalent to being 1 if the two bits are different, and 0 if they are the same. For example:
    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)



Reference -
http://academic.evergreen.edu/projects/biophysics/technotes/misc/bin_math.htm
http://en.wikipedia.org/wiki/Ones%27_complement
http://en.wikipedia.org/wiki/Two's_complement
http://en.wikipedia.org/wiki/Bitwise_operation

No comments:

Post a Comment