Message Boards

WOLFRAM COMMUNITY

4288 Views

9 Replies

8 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Add two numbers in Binary?

Aryan Deshpande

Posted 5 years ago

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?

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?

POSTED BY: Aryan Deshpande

9 Replies

Sort By:

Rohit Namjoshi

Posted 5 years ago

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`.

POSTED BY: Rohit Namjoshi

Daniel Lichtblau

Daniel Lichtblau, Wolfram Research

Posted 5 years ago

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.

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.

POSTED BY: Daniel Lichtblau

Hans Dolhaine

Hans Dolhaine, retired

Posted 5 years ago

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"]]

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"]]

POSTED BY: Hans Dolhaine

Hans Dolhaine

Hans Dolhaine, retired

Posted 5 years ago

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

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

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

POSTED BY: Hans Dolhaine

Hans Dolhaine

Hans Dolhaine, retired

Posted 5 years ago

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" .

POSTED BY: Hans Dolhaine

Hans Dolhaine

Hans Dolhaine, retired

Posted 5 years ago

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.

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.

POSTED BY: Hans Dolhaine

Aryan Deshpande

Posted 5 years ago

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.

POSTED BY: Aryan Deshpande

Aryan Deshpande

Posted 5 years ago

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

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

POSTED BY: Aryan Deshpande

Aryan Deshpande

Posted 5 years ago

Thanks for the suggestion, it works now.

POSTED BY: Aryan Deshpande

Reply to this discussion

Reply Preview

Attachments

Remove Add a file to this post

Follow this discussion

or Discard

Group Abstract

Feedback