Java中二进制算术的算法

以下代码实现二进制加法,而不实际执行任何算术、二进制或其他操作。实际的“添加”是由 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;
}

要整型的二进制字符串:

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

然后你可以用这两个整数做任何你想做的事,例如:

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

要将它们恢复为二进制字符串:

String s = Integer.toBinaryString(i);

算法,来自维基百科:

添加:

中最简单的算术运算 二进制是加法。加二 一位数二进制数是 相对简单,使用 运送:

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

使用二进制算法与更熟悉的基数10没有什么不同。以加法为例

                 (1)     (1)
182      182      182      182      182
845      845      845      845      845
--- +    --- +    --- +    --- +    --- +
           7       27      027     1027

你做了什么?您右对齐要添加的数字,然后从右向左进行,一次添加一个数字,根据需要向左携带+1。

在二进制中,过程是完全相同的。事实上,它甚至更简单,因为你现在只有2个“数字”,0和1!

             (1)                           (1)       (1)
11101      11101      11101      11101      11101      11101      11101
 1001       1001       1001       1001       1001       1001       1001 
----- +    ----- +    ----- +    ----- +    ----- +    ----- +    ----- +
               0         10        110       0110      00110     100110

其余的操作也同样工作:用于基10的同一进程用于基2。再说一遍,它实际上更简单,因为只有2个“数字”,0和1。这就是硬件喜欢二进制系统的原因。

将二进制字符串转换为整数,然后对整数进行操作,例如

String add(String s1, String s2) {
    int i1 = Integer.parseInt(s1);
    int i2 = Integer.parseInt(s2);
    return Integer.toBinaryString(i1 + i2);
}

内置的 BitSet 类直接用于位级操作。