Bit Manipulation

• add

  def add(a, b):
  s, carry = a, b
  while ( carry != 0 ):
    tmp = s^carry
    carry = s&carry
    carry = carry << 1
    s = tmp
  return tmp
  

  Notes

Why the loop will ever end?

minus

• Negatie number? Two's complement (http://www.ruanyifeng.com/blog/2009/08/twos_complement.html) Deriving two's complement procedure is composed of two steps

  1. take complement (convert 0 to 1; 1 to 0)
  2. +1

• Example: Take 3 as an example:

  original number: 00000011
  take complement: 11111100
  +1:              11111101
  

• Let's see in such a way how numbers from -128 to 127 is represented:

  10000000   -128 (128)
  10000001   -127 (129)
  10000010   -126 (130)
  10000011   -125 (131)
  .
  .
  .
  11111101   -3   (253)
  11111110   -2   (254)
  11111111   -1   (255)
  00000000   0
  00000001   1
  00000010   2
  .
  .
  .
  01111100   124
  01111101   125
  01111110   126
  01111111   127
  

  The number in the parentheses is the corresponding unsigned integer y. Thus the signed integer x is: x = -(256-y), y >= 128. An 8-bit number represents the unsigned integer 0 ~ 255, but the signed integer -128 ~ 127. Anyway, it is just some way of mapping, but why we choose this? What convenience might it bring?

• How the "plus" is converted to "minus"?

  • 5 - 3 = 5 + (256-3) = 256 + 2. (If we ignore the overflowed bit, it becomes 2.)
  • 3 - 5 = 3 + (256-5) = 256 - 2. (-2)
  • The essential idea is converting the calculation of signed number to that of un-signed number via a neat way of mapping.

multiplication

def add(a, b):
  s, carry = a, b
  while ( carry != 0 ):
    tmp = s^carry
    carry = s&carry
    carry = carry << 1
    s = tmp
  return tmp

def multiply(a, b):
  res = 0
  icount = 0
  if ( a < 0 ):
    a = add(~a, 1) # a = -a
    b = add(~b, 1) # b = -b

  while ( a != 0 ):
    if ( a&1 == 1 ):
      res = add(res, (b<<icount))
    a = a >> 1
    icount = add(icount, 1)
  return res