Add two numbers in Binary?

Questions
1

Hi! I am trying to rewrite this code in WL from Python. Can anyone help me? I am confused on how to write the “i in Range” function.

a = [1, 0, 1, 1]
b = [0, 1, 1, 0]

c = []
acc = 0
for i in range(len(a) - 1, -1, -1):
    c.append((a[i] + b[i] + acc) % 2)
    acc = int((a[i] + b[i] + acc) / 2)

c.append(acc)
print(c[::-1])

Is it something like this?

While[i , Range[Length[num3]] -1]

But how do you write -1, -1?

2

Hi Aryan,

To get a range that is the same as the Python range

Range[Length[a] - 1, 0, -1]

WL indexing starts at 1, not 0 so

Range[Length[a], 1, -1]

A somewhat literal translation of the Python code

c = {};
acc = 0;
For[i = Length[a], i > 0, i--,
 AppendTo[c, Mod[a[[i]] + b[[i]] + acc, 2]];
 acc = Round[(a[[i]] + b[[i]] + acc)/2];]
AppendTo[c, acc]

There are much better ways to do this in WL without using For and AppendTo.

3

Thank you for this translation! I was stuck at the indexing part and hence, wasn’t able to write the next part. I will check this out, and check for ways to do it without For and AppendTo.

4

AppendTo could be avoided by this

a = {1, 0, 1, 1};
b = {0, 1, 1, 0};
n = Length[a];
res = Table[0, {i, n}];
n1 = n + 1;

ue = 0;
i = 1;
While[
 i <= n,
 r = a[[n1 - i]] + b[[n1 - i]] + ue;
 If[r == 0, ue = 0,
  If[r == 1, ue = 0,
   If[r == 2, r = 0; ue = 1,
    If[r == 3, r = 1; ue = 1]]]];
 res[[n1 - i]] = r;
 i = i + 1
 ]
res
If[ue == 1, Print["Overflow"]]
5

And one could do it like this (without explicit For or While ).

Define

add1[{a_, b_}] := Module[{xx},
  arg = Transpose[Reverse /@ {a, b}] /. {1 -> True, 0 -> False};
  e1 = Reverse /@ 
    Transpose[Map[Boole, ({Xor @@ #, And @@ #} & /@ arg), {2}]];
  If[e1[[2, 1]] == 1, ovflg = 1];
  xx = RotateLeft[Join[e1[[2]], {0}]];
  {e1[[1]], Drop[xx, -1]}
  ]

and

add[a_, b_] := Module[{n, xx},
ovflg = 0;
n = Length[a];
If[n != Length[b], Return["error"]];
xx = Nest[add1, {a, b}, n - 1];
xx[[1]]]

Then

a = {1, 0, 1, 1, 1};
b = {0, 1, 1, 0, 0};
add[a, b]
ovflg

or

add[{0, 1, 1, 1}, {0, 1, 0, 1}]
ovflg
6

But I think the best method is

a = {1, 0, 1, 1, 1};
b = {0, 1, 1, 0, 0};
c= IntegerDigits[FromDigits[a, 2] + FromDigits[b, 2], 2]

Note: Length [ c ] == Length[ a ] +1, so there is an “overflow” .

7

Hi! This somehow isn’t working.

num3 = {1, 1, 1, 1, 0, 0, 0};
num4 = {1, 1, 1, 1, 0, 0, 0};
add = {};
acc = 0;
For[i = Length[num3], i > 0, i--, 
 AppendTo[add, Mod[num3[[i]] + num4[[i]] + acc, 2]];
 acc = Round[(num3[[i]] + num4[[i]] + acc)/2];]
AppendTo[add, acc]

For this two numbers the sum should be 011110000, whereas the code is outputting 00001002

8

The answer should be {1, 1, 1, 1, 0, 0, 0, 0 } ;

num3 = {1, 1, 1, 1, 0, 0, 0};
num4 = {1, 1, 1, 1, 0, 0, 0};
IntegerDigits[FromDigits[num3, 2] + FromDigits[num4, 2], 2]

In your code use Floor instead of Round. And AppendTo puts the first result into Position 1 of your result and so on: use Reverse

num3 = {1, 1, 1, 1, 0, 0, 0};
num4 = {1, 1, 1, 1, 0, 0, 0};
add = {};
acc = 0;
For[i = Length[num3], i > 0, i--, 
 AppendTo[add, Mod[num3[[i]] + num4[[i]] + acc, 2]];
 acc = Floor[(num3[[i]] + num4[[i]] + acc)/2];
 ]
Reverse@AppendTo[add, acc]

By the way: you should avoid AppendTo and use other methods.

9

Thanks for the suggestion, it works now.

10

A reasonable way to emulate the linked list way of prepending is to nest lists. That way prepending is O(1) rather than O(n) is time complexity.

addBinary[l1_, l2_] := Module[
  {len = Max[Length[l1], Length[l2]], n1, n2, acc = 0, bit, res = {}},
  n1 = PadLeft[l1, len];
  n2 = PadLeft[l2, len];
  Do[
   {acc, bit} = QuotientRemainder[n1[[j]] + n2[[j]] + acc, 2];
   res = {bit, res}
   , {j, len, 1, -1}];
  If[acc == 1, res = {1, res}];
  Flatten[res]
  ]

Example:

num3 = {1, 1, 1, 1, 0, 0, 0};
num4 = {1, 1, 1, 1, 0, 0, 0};
addBinary[num3, num4]

(* Out[23]= {1, 1, 1, 1, 0, 0, 0, 0} *)

More efficient would be to use a fixed size array, with Table. But the above variant is reasonably close to the Python approach without sacrificing algorithmic complexity.