Java中二进制算法的算法

Question

在纸面上,二进制算法很简单,但作为一个初级程序员,我发现有点难以提出二进制数的加法,减法,乘法和除法算法.

我有两个二进制数存储为字符串,假设已删除任何前导零.我将如何对这两个数字执行这些操作？

编辑:我需要避免将它们转换为int或long.

Answer 1

二进制字符串到int:

int i = Integer.parseInt("10101011", 2);
int j = Integer.parseInt("00010", 2);

那么你可以用两个整数做任何你喜欢的事,例如:

i = i + j;
i = i - j;

并让他们回到二进制字符串:

String s = Integer.toBinaryString(i);

Answer 2

这些算法来自维基百科:

加成:

二进制中最简单的算术运算是加法.添加两个一位二进制数字相对简单,使用一种携带形式:

0 + 0 ? 0
0 + 1 ? 1
1 + 0 ? 1
1 + 1 ? 0, carry 1 (since 1 + 1 = 0 + 1 × 10 in binary)

添加两个"1"数字会产生一个数字"0",而1则必须添加到下一列.

减法:

减法的工作方式大致相同:

0 ? 0 ? 0
0 ? 1 ? 1, borrow 1
1 ? 0 ? 1
1 ? 1 ? 0

从"0"数字减去"1"数字产生数字"1",而必须从下一列中减去1.这被称为借贷.原则与携带相同.当减法的结果小于0时,数字的最小可能值,程序是从左边"借"赤字除以基数(即10/10),从下一个位置减去它值.

乘法:

二进制中的乘法与其十进制对应类似.两个数字A和B可乘以部分乘积:对于B中的每个数字,计算A中该数字的乘积并将其写在新线上,向左移动,使其最右边的数字与B中的数字对齐.用过的.所有这些部分产品的总和给出了最终结果.

由于二进制只有两位数,因此每个部分乘法只有两种可能的结果:

* If the digit in B is 0, the partial product is also 0
* If the digit in B is 1, the partial product is equal to A

例如,二进制数1011和1010乘以如下:

            1 0 1 1   (A)
          × 1 0 1 0   (B)
          ---------
            0 0 0 0   ? Corresponds to a zero in B
    +     1 0 1 1     ? Corresponds to a one in B
    +   0 0 0 0
    + 1 0 1 1      
    --------------- 
    = 1 1 0 1 1 1 0

Answer 3

以下代码实现了二进制加法，而不实际执行任何算术、二进制或其他算术。实际的“加法”是由 完成的lookupTable，其他一切都是直接的字符串操作。我写这篇文章的目的是让它尽可能具有启发性，强调过程而不是效率。希望能帮助到你。

public class BinaryArithmetic {
    static String[] lookupTable = {
        "0+0+0=00",
        "0+0+1=01",
        "0+1+0=01", 
        "0+1+1=10",
        "1+0+0=01",
        "1+0+1=10",
        "1+1+0=10",
        "1+1+1=11",
    };
    static String lookup(char b1, char b2, char c) {
        String formula = String.format("%c+%c+%c=", b1, b2, c);
        for (String s : lookupTable) {
            if (s.startsWith(formula)) {
                return s.substring(s.indexOf("=") + 1);
            }
        }
        throw new IllegalArgumentException();
    }
    static String zeroPad(String s, int length) {
        while (s.length() < length) {
            s = "0" + s;
        }
        return s;
    }   
    static String add(String s1, String s2) {
        int length = Math.max(s1.length(), s2.length());
        s1 = zeroPad(s1, length);
        s2 = zeroPad(s2, length);
        String result = "";
        char carry = '0';
        for (int i = length - 1; i >= 0; i--) {
            String columnResult = lookup(s1.charAt(i), s2.charAt(i), carry);
            result = columnResult.charAt(1) + result;
            carry = columnResult.charAt(0);
        }
        if (carry == '1') {
            result = carry + result;
        }
        return result;
    }
    public static void main(String args[]) {
        System.out.println(add("11101", "1001"));
    }
}

当我们这样做的时候，我也不妨multiply这样做。

static String multiply(String s1, String s2) {
    String result = "";
    String zeroSuffix = "";
    for (int i = s2.length() - 1; i >= 0; i--) {
        if (s2.charAt(i) == '1') {
            result = add(result, s1 + zeroSuffix);
        }
        zeroSuffix += "0";
    }
    return result;
}