| 45 | } |
| 46 | |
| 47 | QCircuit QAdd_V2(QVec &a, QVec &b, QVec &aux, ADDER type /* = ADDER::CDKM_RIPPLE*/) |
| 48 | { |
| 49 | if ((a.size() == 0) || (a.size() != b.size())) |
| 50 | { |
| 51 | QCERR_AND_THROW(std::invalid_argument, "a and b must be equal, but not equal to 0!"); |
| 52 | } |
| 53 | |
| 54 | auto adder = AdderFactory::getInstance().createAdder(type); |
| 55 | |
| 56 | /* use two's complement for negative addition */ |
| 57 | /* |
| 58 | overflow rule is(in complement representation): |
| 59 | 1.if a, b is negative, sum is positive, overflow |
| 60 | 2.if a, b is positive, sum is negative, overflow |
| 61 | 3.if a, b have different sign, won't overflow |
| 62 | note sum only take fixed bit size same as a or b, did not take account carry bit |
| 63 | |
| 64 | overflow = a.b.s' ⊕ a'.b'.s (short for sign) |
| 65 | |
| 66 | we save a.b and a'.b' to ancil bit, but from the truth table, we found it's hard to restore ancil bits |
| 67 | b a.b a'.b' sum o a |
| 68 | 1 1 0 1 0 1 * |
| 69 | 1 1 0 0 1 1 |
| 70 | 0 0 0 0 0 1 |
| 71 | 0 0 0 1 0 1 * |
| 72 | 1 0 0 0 0 0 + |
| 73 | 1 0 0 1 0 0 |
| 74 | 0 0 1 0 0 0 + |
| 75 | 0 0 1 1 1 0 |
| 76 | as sum is saved in b after addition, so we can only use a, s, o to restore ancil a.b and a'.b' |
| 77 | but found two undistinguishable pairs marked with '*' and '+', it is unreversible goal, can not restore ancil |
| 78 | this may overkill |
| 79 | |
| 80 | so we used another rule: |
| 81 | overflow = unsign_carry_out ⊕ full_carry_out |
| 82 | |
| 83 | this way can only implemented inside adder for get unsigned num carry |
| 84 | but this will miss one situation: sum is negative 0 |
| 85 | take 3 bit complement binary for example: |
| 86 | -3 101 |
| 87 | + -1 111 |
| 88 | ----------- |
| 89 | -4 1100 |
| 90 | cut fix size result(3 bits), it'is 100, which is negative 0 |
| 91 | unsign_carry = 1 |
| 92 | full_carry = 1 |
| 93 | so overflow = 0, missed |
| 94 | but negative 0 will give other trace, see QComplement_V2 |
| 95 | */ |
| 96 | QPANDA_ASSERT(aux.size()==0, "aux at least have size 1"); |
| 97 | QCircuit qc; |
| 98 | qc << QComplement_V2(a, aux.front()) |
| 99 | << QComplement_V2(b, aux.front()) |
| 100 | << adder->QAdd(b, a, aux, ADDER_MODE::OF) |
| 101 | << QComplement_V2(a, aux.front()) |
| 102 | << QComplement_V2(b, aux.front()); |
| 103 | return qc; |
| 104 | } |