Сумма двоичных чисел JAVA

[Лучик искренности]

Задание:
Посчитайте A + B в двоичной системе счисления.

Входные данные

В отдельных строках задано два неотрицательных целых числа A и B в двоичной системе счисления, количество цифр в каждом из которых не превышает 1000.

Выходные данные

Выведите сумму A + B также в двоичной системе счисления.

Мой вариант решения:

import java.util.Scanner;

public class Main {
   
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);

       int a = Integer.parseInt(sc.next(), 2);
       int b = Integer.parseInt(sc.next(), 2);
       
       System.out.println(Integer.toBinaryString(a + b));

       sc.close();
   }
}

Вроде бы все считает, но решение проходит только 14 тестов из 20 (это тренировочная олимпиадная задача). Я предполагаю, что дело в Integer, в диапазон которого, видимо, не входит 1000-значное двоичное число.
Помогите найти решение проблемы, пожалуйста. Может, я не права и проблема в другом?

@темы: Java

Comments

[Trotil]

видимо, не входит 1000-значное двоичное число.

В Int входит 32 или 64 бита только.

Помогите найти решение проблемы, пожалуйста.

Очевидно, не использовать встроенный тип Int, а реализовать свой.
(или использовать библиотеку "длинной" арифметики)

[Лучик искренности]

Trotil, я проставила long везде, но количество пройденных тестов не изменилось. Значит, не в этом дело(
Не знаете, в чем может еще быть проблема?(

[Trotil]

Вопрос на засыпку - сколько бит занимает тип long?

[Лучик искренности]

Trotil, я поняла, туплю. 64 бита. Все равно мало(

или использовать библиотеку "длинной" арифметики

это BigInteger и подобное? но у него же нету таких методов, как у Integer

[Trotil]

но у него же нету таких методов, как у Integer

Вот об этом я не в курсе - есть или нету.
Но странно, если нету - тип "большое целое" есть, а арифметические операции над ними не определены. Странно.
Но если нет - ничего страшного - реализуйте свой. Он несложный. Число можно представить в виде строки и анализировать посимвольно.

[Ri]

это BigInteger и подобное? но у него же нету таких методов, как у Integer

Зачем вам методы Integer? Тех, что есть в BigInteger, вполне достаточно. Будет примерно так (не тестировал):

BigInteger value = new BigInteger("010101", 2);
BigInteger value2 = new BigInteger("1010", 2);
value = value.add(value2);
System.out.println(value.toString(2));

[Лучик искренности]

Trotil

Но если нет - ничего страшного - реализуйте свой. Он несложный. Число можно представить в виде строки и анализировать посимвольно.

я пыталась так, но запуталась немного

Ri, спасибо большое, переделала в BigInteger, все тесты прошли. Я просто раньше с ним не сталкивалась, теперь буду знать, еще раз спасибо)

[[revolver]]

дымчатая.реальность, эта задача как раз чтобы разобраться как писать длинную арифметику, а не то, как подключить BigInt в Java

[Ri]

эта задача как раз чтобы разобраться как писать длинную арифметику, а не то, как подключить BigInt в Java

Не факт. Может, эта задача на проверку, умеете ли вы пользоваться стандартной библиотекой. Зависит от контекста, в общем.

[[revolver]]

Ri, это _олимпиадная задача_.
Спорить и доказывать никому ничего не буду. Просто поверь.
Я 4 года в школе, 5 лет в универе и 2 года сейчас занимаюсь и готовлю к олимпиадам.

[Лучик искренности]

[revolver], да, олимпиадная. Но нас никто не готовит, поэтому я понятия не имею, как это должно быть и какова цель задачи
Я не очень понимаю, что из себя представляет понятие "длинная арифметика". Если можно, дайте ссылочку, где об этом можно почитать в целом? А то гугл только конкретные проблемы показывает.

[Ri]

Обычные типы данных имеют ограничения на максимальное и минимальное значения. Для Java, например, табличку можно посмотреть здесь. Сделано это потому, что арифметику с числами конечной точности проще реализовать на аппаратном уровне, да и в подавляющем большинстве случаев этой точности хватает. В случае, если нужны точные операции с большими числами (например, факториал тысячи посчитать), необходимо реализовывать всё по-другому. Каждое число в длинной арифметике может быть любой длины (или, по крайней мере, максимальная длина числа становится больше). Значение числа при этом хранится в нескольких переменных. Например, двоичное целое число можно представить в виде массива boolean значений, по одному на каждую цифру. Или можно прямо в виде строки хранить. Проблема заключается в том, что все арифметические операции (сложение, умножение и т.п.) необходимо реализовывать вручную. Вам, например, нужно реализовать сложение. Простейший способ это сделать — поразрядно. То есть берете оба слагаемых и начинаете справа налево их складывать столбиком, не забывая о переносе единицы в старший разряд при необходимости. Класс BigInteger в Java умеет делать нечто подобное.

Ссылка на википедию