Solution Simulating Digital Logic Design


  • 2
    A

    Addition at hardware level is implemented using AND/ OR/ XOR gates on each digit.
    So we can implement exact same idea.

    1. for the last digit d1, d2 & c, d1^d2^c is the digit after sum.

    2. carry is the "majority selector"; meaning among 3 digits, if 2 or 3 digit is 1, its value is 1; if 2 or 3 digits is 0, it is 0. this is (d1&d2) | (d1&c) | (d2&c).

      public int getSum(int a, int b) {
      int sum = 0, c = 0;
      for (int i = 0; i < 32; i++) {
          int d1 = a & 1, d2 = b & 1; // last digit of a & b
          sum |= ((d1^d2^c) << i); // update sum digit
          c = (d1&d2) | (d1&c) | (d2&c); // update carrier
          a >>>= 1;
          b >>>= 1;
      }
      return sum;
      

      }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.