Perl Weekly Challenge 140: Add Binary

Input: $a = 11; $b = 1;
Output: 100

Input: $a = 101; $b = 1;
Output: 110

Input: $a = 100; $b = 11;
Output: 111

The challenge description is very confusing. What on earth is a decimal-coded binary number? Google doesn't know, and if you search for it, it gives you results for Binary Coded Decimals — which are well known. But it doesn't look like we are dealing with Binary-coded decimals.

Then we are asked to simulate the addtion of binary numbers. Which is a bit confusing. Virtual every general purpuse computer created in the past 70 years does arithmetic using binary. Are we asked to simulate something which is already done? How so? The examples are of no use, what they're showing has as little to do with simulating anything as it as to do with spinach.

Then it mentions "operator overloading" out of the blue. What should we overload? Overload the + operator to do addition instead of, well, uhm, addition?

Gosh, someone really, really ought to proofread those challenges. It won't take more than a few seconds to give this a thumbs down.

As it is often the case, we'll completely ignore the silly instructions and deduce a challenge from the examples. We'll reframe the challenge as:

• You are given two numbers in binary representation.
• Add them, and show the result in a binary representation.

The challenge now really boils down to mapping numbers back and forth between an integer and decimal representation. Some languages have support for that, some languages have functions which can be used to do this mapping, and in some languages, we have to roll our own.

In each implementation, we assume the input consists of one or more lines, with two non-negative integers in binary representation on each line. For each line of input, we write a line with the sum of the two numbers to standard output.

Perl doesn't have build in function dedicated to mapping numbers from one base to the other, but it does have functions which can be used. To map an integer in binary representation to a regular integer, we prepend the binary number with 0b, and use oct. To get the binary representation of a number, we sprintf with the %b format. This gives us a one-liner:

say sprintf "%b" => eval join " + " => map {oct "0b$_"} split while <>;

Find the full program on GitHub.

Ruby is an example of a language which can build in methods to do the necessary mappings. to_i is a method which can be applied on a string, and which returns the integer value of the string. to_i takes an optional argument to state in which base the number is represented. In the same way to_s is a method which can be applied on integers, and which returns a string with the representation of that integer. It also takes an optional argument: the base in which represent the number.

This leads to the following short program:

ARGF . each_line do
    | line |
    a, b = line . strip() . split (" ")
    puts (a . to_i(2) + b . to_i(2)) . to_s(2)
end

Find the full program on GitHub.

AWK doesn't have any support to convert numbers from one base to another. So, we have to roll our own, which isn't very hard. First, a subroutine which takes a number in binary, and returns a regular integer:

function bin2dec (bin, dec, digits, n) {
    dec = 0
    n = split (bin, digits, "")
    for (i = 1; i <= n; i ++) {
        dec = 2 * dec + digits [i]
    }
    return (dec)
}

and a subroutine which does the reverse:

function dec2bin (dec, bin) {
    while (dec) {
        bin = dec % 2 bin
        dec = int (dec / 2)
    }
    return (bin)
}

Given those, the main program is just a one-liner:

{ print dec2bin(bin2dec($1) + bin2dec($2)) }

Find the full program on GitHub.

bc has a trick up its sleeve. We can just tell it in which base its input is, and which base its output should be written in. So we can just add the numbers, stopping processing input after reading a 0:

obase=2
ibase=2

while (1) {
    a = read(); if (a == 0) {break}
    b = read(); if (b == 0) {break}
    a + b
}

Find the full program on GitHub.

In Scheme, we have to roll our own mapping functions. In Scheme, we prefer recursion over looping, giving use the following functions:

(define (bin2dec bin) 
    (define len (string-length bin))
    (cond ((= len 0) 0)
          (else (+ (string->number (string-take-right bin 1))
                   (* 2 (bin2dec   (string-drop-right bin 1)))))))

and

(define (_dec2bin dec)
    (cond ((= dec 0) "")
          (else (string-concatenate
                   (list (_dec2bin       (floor-quotient dec 2))
                         (number->string (modulo         dec 2)))))))

(define (dec2bin dec)
    (cond ((= dec 0) "0")
          (else (_dec2bin dec))))

Giving us the following main program:

(define (main)
    (define line (read-line))
    (define parts)
    (if (not (eof-object? line))
        (begin
            (display (dec2bin (fold + 0 (map bin2dec (string-split line #\ )))))
            (newline)
            (main)
        )
    )
)

Find the full program on GitHub.