JavaScript无位运算符实现全减器结果异常修复问询

我尝试在JavaScript中不使用位运算符实现位操作，全加器做起来挺简单，但全减器出问题了。调用BitSubtractor(8, '100', '10')计算100减10时，预期结果是[0,0,0,0,0,0,1,0]，但实际得到[0,0,0,0,1,0,1,0]，明显多了个借位，求修复方案。

相关实现代码如下：

function BitSubtractor(bits, A, B){
    try{
        A = getBinaryArray(A);
        B = getBinaryArray(B);
        if(A.length > bits || B.length > bits)
            throw new SyntaxError(
                'Number of bits must be less than or equal to ' + bits + ' bits\n' + 
                'A: ' + A.length + ' bits\n' +
                'B: ' + B.length + ' bits'
            );
    }catch(e){
        throw e;
    }

    if(A.length < bits || B.length < bits){
        while(A.length < bits)
            A.unshift(0);
        while(B.length < bits)
            B.unshift(0);
    }

    console.log(A, B)

    let result = [];
    let borrow = 0;

    for(let i = bits - 1; i >= 0; i--){
        let a = Number(A[i]);
        let b = Number(B[i]);
        let FS = new Subtractor(a, b, borrow);
        result.unshift(FS.DIFF);
        borrow = FS.BORROW;
        // console.log(a, b, FS)
    }

    let overflow = [];
        overflow.unshift(borrow);
        while(overflow.length < bits)
            overflow.unshift(0);

    // let negative = borrow ? true : false;
    return {diff: result, overflow, borrow/* , negative */};
};

function Subtractor(A, B, Bin = 0){
    if(!checkValue(A) || !checkValue(B) || !checkValue(Bin))
        throw new Error('A, B, and Bin must be boolean');
    
    // DIFF = A XOR B XOR Bin
    // this.DIFF = (A ^ B ^ Bin) ? 1 : 0;
    let AB_XOR     = Gate.XOR(A, B);
    let AB_Bin_XOR = Gate.XOR(AB_XOR, Bin);

    // BORROW = (!A AND B) OR (B AND Bin) OR (A AND Bin)
    // this.BORROW = (!A & B) | (B & Bin) | (A & Bin) ? 1 : 0;
    let A_NOT     = Gate.NOT(A);
    let B_NOT     = Gate.NOT(B);
    let Bin_NOT   = Gate.NOT(Bin);
    let A_NOT_AND = Gate.AND(A_NOT, B);
    let B_AND_Bin = Gate.AND(B, Bin);
    let A_AND_Bin = Gate.AND(A, Bin);
    let OR_1      = Gate.OR(A_NOT_AND, B_AND_Bin);
    let OR_2      = Gate.OR(OR_1, A_AND_Bin);

    this.DIFF   = AB_Bin_XOR;
    this.BORROW = OR_2;
    return this;
};

function Transistor(input, type){
    if(!checkValue(input))
        throw new Error('IN must be boolean');

    if(input === '0') input = Number(input);

    this.IN = toBoolean(input);
    this.OUT = this.IN;

    if(type === 'NOT')
        this.OUT = !this.OUT;

    return this.OUT;
};

function Gate(A, B, type){
    const inputA = new Transistor(A);
    const inputB = new Transistor(B);
    this.IN1 = inputA.OUT;
    this.IN2 = inputB.OUT;
    this.OUT = null;

    if(type === 'AND'){
        this.OUT = this.IN1 && this.IN2;
    }
    if(type === 'OR'){
        this.OUT = this.IN1 || this.IN2;
    }
    if(type === 'XOR'){
        this.OUT = (this.IN1 || this.IN2) && !(this.IN1 && this.IN2);
        // this.OUT = (!this.IN1 && this.IN2) || (this.IN1 && !this.IN2);
    }

    if(this.OUT !== null)
        return toBinary(this.OUT);
};

// Bitwise Operators
Gate.BitAND = (A, B) => A & B;
Gate.BitOR  = (A, B) => A | B;
Gate.BitXOR = (A, B) => A ^ B;
Gate.BitNOT = A => ~A;

Gate.AND = (A, B) => Gate(A, B, 'AND');
// Gate.NAND = (A, B) => Gate(A, B, 'AND') ? 0 : 1;
Gate.OR  = (A, B) => Gate(A, B, 'OR');
// Gate.NOR = (A, B) => Gate(A, B, 'OR') ? 0 : 1;
Gate.XOR = (A, B) => Gate(A, B, 'XOR');
Gate.NOT = A => Transistor(A, 'NOT');

问题根源 #

错误出在Subtractor函数的借位计算公式上。你当前使用的公式：

BORROW = (!A AND B) OR (B AND Bin) OR (A AND Bin)

逻辑错误，其中A AND Bin的分支会导致不该产生借位的场景误生成借位。

全减器的正确借位逻辑是：当被减数A小于B + Bin时，向高位借位，对应的正确公式为：

BORROW = (!A AND B) OR (!A AND Bin) OR (B AND Bin)

修复后的Subtractor函数 #

function Subtractor(A, B, Bin = 0){
    if(!checkValue(A) || !checkValue(B) || !checkValue(Bin))
        throw new Error('A, B, and Bin must be boolean');
    
    // DIFF = A XOR B XOR Bin 这部分逻辑是对的，无需修改
    let AB_XOR     = Gate.XOR(A, B);
    let AB_Bin_XOR = Gate.XOR(AB_XOR, Bin);

    // 修正后的借位计算公式
    let A_NOT          = Gate.NOT(A);
    let A_NOT_AND_B    = Gate.AND(A_NOT, B);
    let A_NOT_AND_Bin  = Gate.AND(A_NOT, Bin);
    let B_AND_Bin      = Gate.AND(B, Bin);
    let OR_1           = Gate.OR(A_NOT_AND_B, A_NOT_AND_Bin);
    let OR_2           = Gate.OR(OR_1, B_AND_Bin);

    this.DIFF   = AB_Bin_XOR;
    this.BORROW = OR_2;
    return this;
};

验证修复效果 #

修复后调用BitSubtractor(8, '100', '10')：

• A补全8位为[0,0,0,0,0,1,0,0]，B补全为[0,0,0,0,0,0,1,0]
• 逐位计算时，第三位（从右数第3位）的借位会被正确计算为0，最终结果就是预期的[0,0,0,0,0,0,1,0]

内容的提问来源于stack exchange，提问作者nitroflox