Алгоритм для двоичной арифметики в Java
На бумаге двоичная арифметика проста, но как начинающий программист, я нахожу немного трудным придумать алгоритмы для дополнения, вычитания, умножения и разделения двоичных чисел.
Я имею два двоичных числа, сохраненные как строки, предполагаю, что любое продвижение обнуляет, были отброшены. Как я пошел бы о выполнении этих операций на этих двух числах?
Править: Я должен постараться не преобразовывать их в интервал или долго.
6 ответов
Следующий код реализует двоичное сложение без выполнения каких-либо арифметических, двоичных или иных операций. Фактическое «сложение» выполняется с помощью 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"));
}
}
Пока мы это делаем, я мог бы также сделать умножить тоже.
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;
}
Работа с двоичной арифметикой действительно ничем не отличается от более знакомой основы 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. Эта простота объясняет, почему аппаратное обеспечение любит двоичную систему.
Встроенный класс BitSet очень прост в использовании для операций на битовом уровне.
Преобразуйте двоичные строки в целые числа, а затем обработайте целые числа, например
String add(String s1, String s2) {
int i1 = Integer.parseInt(s1);
int i2 = Integer.parseInt(s2);
return Integer.toBinaryString(i1 + i2);
}
Алгоритмы из википедии:
Дополнение:
Самая простая арифметическая операция в двоичном формате - это сложение. Сложить два однозначных двоичных числа относительно просто, используя форму , несущую:
0 + 0 → 0 0 + 1 → 1 1 + 0 → 1 1 + 1 → 0, переносит 1 (поскольку 1 + 1 = 0 + 1 × 10 в двоичном формате)Добавление двух «1» digits дает цифру "0", а 1 нужно будет добавить в следующий столбец.
Вычитание :
Вычитание работает примерно так же способом:
0 - 0 → 0 0 - 1 → 1, заимствовать 1 1–0 → 1 1–1 → 0Вычитание цифры «1» из цифры «0» дает цифру «1», а 1 { {1}} нужно будет вычесть из следующего столбца . Это известно как заимствование. Принцип тот же , что и для переноски. Когда результат вычитания меньше 0, наименьшего возможного значения цифры, процедура заключается в "заимствовании" дефицита , деленного на система счисления (то есть 10/10) слева, вычитая ее из следующего позиционного значения .
Умножение :
Умножение в двоичном формате аналогично его десятичному аналогу. Два числа A и B можно умножить на частичные произведения: для каждой цифры в B произведение этой цифры в A вычисляется и записывается на новая строка, сдвинута влево, так что ее крайняя правая цифра совпадает с цифрой в B , которая использовалась. Сумма всех этих частичных продуктов дает окончательный результат .
Поскольку в двоичном формате только две цифры, есть только два возможных результата каждого частичного умножения:
* Если цифра в B равна 0, частичное произведение также равно 0 * Если цифра в B равна 1, частичное произведение равно 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
Двоичная строка в int:
int i = Integer.parseInt("10101011", 2);
int j = Integer.parseInt("00010", 2);
Затем вы можете делать все, что угодно, с двумя целыми числами, например:
i = i + j;
i = i - j;
И вернуть их в двоичную строку :
String s = Integer.toBinaryString(i);