Задача: сложить двоичные числа, представленные в виде строк

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня складываем двоичные числа.

Иллюстрация: Polina Vari для Skillbox Media

Дмитрий Зверев

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Сергей Голицын

Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.

Условие. Даны два двоичных числа в виде строк a и b. Нужно вернуть их суммы в виде строки.

Ввод и вывод. Пример 1

Ввод: a = "11", b = "1"
Вывод: "100"

Ввод и вывод. Пример 2

Ввод: a = "1010", b = "1011"
Вывод: "10101"

Задача и решения взяты из Telegram-канала Сергея Cracking code interview.

Решение

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

Главная проблема здесь — не забыть о числах, которые переносятся в следующий разряд. А ещё нужно помнить, что одна строка может быть длиннее другой. В этом случае придётся добавить оставшиеся символы из более длинной строки к результату.

Чтобы работать со строками было удобно, я использовал StringBuilder. В Java это самый эффективный способ для операций на изменение строк.

Вот как алгоритм будет реализован на Java:

public String addBinary(String aa, String bb) {
    char[] aChars = aa.toCharArray();
    char[] bChars = bb.toCharArray();
     
    int rest = 0;
    int readerA = aChars.length - 1;
    int readerB = bChars.length - 1;
     
    StringBuilder sb = new StringBuilder();
     
    while (readerA >= 0 && readerB >= 0){
      int a = aChars[readerA] - '0';
      int b = bChars[readerB] - '0';
      int sum = a + b + rest;
      rest = sum/2;
      sb.append(sum % 2);
       
      readerA--;
      readerB--;
    }
     
    while(readerA >= 0){
      int a = aChars[readerA] - '0';
      int sum = a + rest;
      rest = sum/2;
      sb.append(sum % 2);
      readerA--;
    }
    while(readerB >= 0){
      int b = bChars[readerB] - '0';
      int sum = b + rest;
      rest = sum/2;
      sb.append(sum % 2);
      readerB--;
    }
    if (rest != 0){
      sb.append(rest);
    }
    return sb.reverse().toString();
  }