But yes, i didn't think its safe to swap two numbers numbers represented in fixed bits without using a temporary variable
We have this famous trick from college days, 
      $a = a + b$
    
    
      $b = a - b$ # a + b - b = a
    
    
      $a = a - b$ # a + b -a = b
    
    
      Which i practically never needed to use, up until in a recent hobby
          project where the number of registers available are only two.
    
     
      well my college days happened some 20 years back, so maybe i
          understood it at that time but not any more... use it or lose it you
          see..  
    
    
      When i wanted to use this trick now, what really concerned me was the
          overflow, and turns out the overflow would not matter. i just try to
          explain in simple terms as below.. 
    
    
      For an $n$ bit width field, the largest unsigned number that can be
          represented is $2^n - 1$.
    
    
      So for an overflow to occur on adding numbers $a$ and $b$, we would
          need $a$ as:
    
    
      $a = 2^{n-1} + x$
    
    
      and $b$ such that $x + b = 2^{n-1} + y$ where $y \ge 0$ 
    
    
      From above, we can re-express $b$ as $b = 2^{n-1} + y - x$ Lets remember this as $eq(1)$ 
    
    
    
    
      When we do
    
    
      $a := a + b$, we have
    
    
      $a := 2^{n-1} + x + b = 2^{n-1} + 2^{n-1} + y = 2^n + y$
    
    
      But because we only have $n$ bits, the value stored at a would
          be:
    
    
      $a = y$
    
    
      And then we set out to do 
    
    
      $b : = a - b = y - b$, so how would we do '$a - b$'?
    
    
      We would first take 2's compliment of $b$ and then add it to
          $a$
    
    
      2's compliment of $b$ is $2^n - b$
          
    
    
      Let's now substiture $b$ from $eq(1)$, then we have,
          
    
    
    
      $b := a - b = y - b = y + 2^n - b = y + 2^n - (2^{n-1} + y - x)$
          
    
        
    
      Thus we get
    
    
      $b := \cancel{y} + 2^n - 2^{n-1} - \cancel{y} + x = 2^{n-1} + x$
    
    
      Now this last expression is exactly the same as the value originally
          at $a$.
    
    
      Similary, we can convince ourselves for the step $a = a - b$ that
          follows 
    
    
      But does it mean i understand the elegance of the modular arithmetic
          involved here?? No way :-)
    
    
No comments:
Post a Comment