Java中二进制算术的算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2412622/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Algorithm for binary arithmetic in Java
提问by Tyler Treat
On paper, binary arithmetic is simple, but as a beginning programmer, I'm finding it a little difficult to come up with algorithms for the addition, subtraction, multiplication and division of binary numbers.
在纸面上，二进制算术很简单，但作为一个初级程序员，我发现想出二进制数的加法、减法、乘法和除法算法有点困难。
I have two binary numbers stored as strings, assume that any leading zeroes have been dropped. How would I go about performing these operations on the two numbers?
我有两个以字符串形式存储的二进制数，假设任何前导零都已被删除。我将如何对两个数字执行这些操作？
Edit: I need to avoid converting them to an int or long.
编辑：我需要避免将它们转换为 int 或 long。
采纳答案by polygenelubricants
The following code implements binary addition without actually doing any arithmetic, binary or otherwise. The actual "addition" is done by lookupTable, and everything else is straight-up string manipulation. I wrote it with the intention of making it as instructive as possible, emphasizing the process instead of efficiency. Hope it helps.
下面的代码实现了二进制加法，而没有实际进行任何算术、二进制或其他运算。实际的“加法”由 完成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"));
}
}
While we're at it, I might as well do multiplytoo.
当我们这样做时，我也可以这样做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;
}
回答by Paul
Binary string to int:
二进制字符串转int：
int i = Integer.parseInt("10101011", 2);
int j = Integer.parseInt("00010", 2);
Then you can do anything you please with the two ints, eg:
然后你可以对这两个整数做任何你想做的事情，例如：
i = i + j;
i = i - j;
And to get them back to a binary string:
并将它们恢复为二进制字符串：
String s = Integer.toBinaryString(i);
回答by Seun Osewa
Convert the binary strings to Integers and then operate on the Integers, e.g.
将二进制字符串转换为整数，然后对整数进行操作，例如
String add(String s1, String s2) {
int i1 = Integer.parseInt(s1);
int i2 = Integer.parseInt(s2);
return Integer.toBinaryString(i1 + i2);
}
回答by iTayb
The algorithms, from wikipedia:
算法，来自维基百科：
Addition:
添加：
The simplest arithmetic operation in binary is addition. Adding two single-digit binary numbers is relatively simple, using a form of carrying:
0 + 0 → 0 0 + 1 → 1 1 + 0 → 1 1 + 1 → 0, carry 1 (since 1 + 1 = 0 + 1 × 10 in binary)Adding two "1" digits produces a digit "0", while 1 will have to be added to the next column.
二进制中最简单的算术运算是加法。两个个位二进制数相加比较简单，使用一种进位形式：
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 必须添加到下一列。
Subtraction:
减法：
Subtraction works in much the same way:
0 ? 0 → 0 0 ? 1 → 1, borrow 1 1 ? 0 → 1 1 ? 1 → 0Subtracting a "1" digit from a "0" digit produces the digit "1", while 1 will have to be subtracted from the next column. This is known as borrowing. The principle is the same as for carrying. When the result of a subtraction is less than 0, the least possible value of a digit, the procedure is to "borrow" the deficit divided by the radix (that is, 10/10) from the left, subtracting it from the next positional value.
减法的工作方式大致相同：
0 ? 0 → 0 0 ? 1 → 1, borrow 1 1 ? 0 → 1 1 ? 1 → 0从“0”数字中减去“1”数字产生数字“1”，而1必须从下一列中减去。这称为借用。原理与携带相同。当减法的结果小于0，一个数字的最小可能值时，程序是从左边“借”除以基数（即10/10）的赤字，从下一个位置减去它价值。
Multiplication:
乘法：
Multiplication in binary is similar to its decimal counterpart. Two numbers A and B can be multiplied by partial products: for each digit in B, the product of that digit in A is calculated and written on a new line, shifted leftward so that its rightmost digit lines up with the digit in B that was used. The sum of all these partial products gives the final result.
Since there are only two digits in binary, there are only two possible outcomes of each partial multiplication:
* 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 AFor example, the binary numbers 1011 and 1010 are multiplied as follows:
二进制乘法类似于其十进制对应项。两个数字 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
回答by awesomo
回答by polygenelubricants
Working with binary arithmetic is really no different than the more familiar base 10. Let's take addition for example
使用二进制算术实际上与更熟悉的基数 10 没有什么不同。让我们以加法为例
(1) (1)
182 182 182 182 182
845 845 845 845 845
--- + --- + --- + --- + --- +
7 27 027 1027
So what did you do? You right-align the numbers to add, and you proceed right-to-left, adding one digit at a time, carrying over +1 to the left as necessary.
那么你做了些什么？您将要添加的数字右对齐，然后从右向左进行，一次添加一位，必要时将 +1 移至左侧。
In binary, the process is exactly the same. In fact, it's even simpler because you only have 2 "digits" now, 0 and 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
The rest of the operations work similarly too: the same process that you use for base 10, works for base 2. And again, it's actually simpler because there are only 2 "digits", 0 and 1. This simplicity is why hardware likes the binary system.
其余的操作也类似：用于基数 10 的相同过程适用于基数 2。同样，它实际上更简单，因为只有 2 个“数字”，0 和 1。这种简单性就是硬件喜欢二进制系统。
