Addition of two integer in binary representation

Question

I would like to implement code which will add two integers by their binary representation.

For instance:

a = [1 1 1 0];

and

b = [1 0 1 1];

So I implemented the following algorithm:

function s=add_binary(a,b)
  m=length(a);
  s=zeros(m+1,0);
  n=length(a);
  c=0;
  for ii=n:-1:1
    d=floor((a(ii)+b(ii)+c)/2);
    s(ii)=a(ii)+b(ii)+c-2*d;
    c=d;          
  end
  s(1)=c; 
end

However, it returns this as a result:

s=add_binary(a,b)

s =

     1     0     0     1

Here, there should be an additional 1 on the left, such that it would read:

1 1 0 0 1

Where am I making a mistake?

Answer 1

This problem was discussed in a 2011 question on MATLAB Answers. I'd like to mention 2 more solutions:

• If you have the Communications System Toolbox, you can use bi2de and de2bi:

  de2bi(bi2de(a,'left-msb') + bi2de(b,'left-msb'),'left-msb')
  

• If the amount of "digits" in the input is known (and reasonable), one solution could be to store all possible input combinations in some data-structure, which would facilitate rapid access. One such example is the MapN class (though it can just as easily be done with regular numeric arrays). I will provide a small example to show this idea (including a benchmark):

  function allResults = q43095156(allResults)
    if nargin == 0 
    % Let's store all combinations of 8 binary digits:
    in = uint8(0:255);
    out = uint16(in)+uint16(in.');
    outB = logical(de2bi(out(:),'left-msb'));
    [in1,in2] = meshgrid(in,in);
    allResults = MapN(...
       num2cell([num2cell(in1(:),2),num2cell(in2(:),2)],2),...
       num2cell(outB,2));
    end
    benchmark(allResults);
  end
  
  function benchmark(allResults)
    rng(43095156);
    a = logical(randi([0 1],10,8,'uint8'));
    b = logical(randi([0 1],10,8,'uint8'));
    % Test:
    R{5} = de2bi(bi2de(a,'left-msb') + bi2de(b,'left-msb'),'left-msb');
    R{4} = add_a_bunch_gnovice(a,b);
    R{3} = add_a_bunch_Sardar(a,b);
    R{2} = add_a_bunch_dato(a,b);
    R{1} = getFromMap(a, b, allResults);
    assert(isequal(R{:}));
    % Benchmark:
    a = logical(randi([0 1],1000,8,'uint8'));
    b = logical(randi([0 1],1000,8,'uint8'));
    fprintf(1,'\nSardar''s method:\t%f',timeit(@() add_a_bunch_Sardar(a, b) ));
    fprintf(1,'\nDev-iL''s method:\t%f',timeit(@() getFromMap(a, b, allResults) ));
    fprintf(1,'\ngnovice''s method:\t%f',timeit(@() add_a_bunch_gnovice(a, b) ));
    fprintf(1,'\ndato''s method:\t\t%f',timeit(@() add_a_bunch_dato(a, b) ));
    fprintf(1,'\nbi2de method:\t\t%f',timeit(@() de2bi(bi2de(a,'left-msb') + bi2de(b,'left-msb'),'left-msb')));
  end
  
  function out = getFromMap(a,b,map)
  out = cell2mat(values(map, num2cell([ num2cell(bi2de(a,'left-msb'),2),...
                                        num2cell(bi2de(b,'left-msb'),2)],2)));
  end
  
  function out = add_a_bunch_gnovice(a,b)
    out = zeros(size(a)+[0,1],'logical');
    for ind1 = 1:size(a,1)
      out(ind1,:) = add_binary_gnovice(a(ind1,:), b(ind1,:));
    end
  end
  
  
  function out = add_a_bunch_Sardar(a,b)
    out = zeros(size(a)+[0,1],'logical');
    for ind1 = 1:size(a,1)
      out(ind1,:) = add_binary_Sardar(a(ind1,:), b(ind1,:));
    end
  end
  
  function out = add_a_bunch_dato(a,b)
    out = zeros(size(a)+[0,1],'logical');
    for ind1 = 1:size(a,1)
      out(ind1,:) = add_binary_dato(a(ind1,:), b(ind1,:));
    end
  end
  
  function s = add_binary_gnovice(a, b)
    a = [0 a];
    b = [0 b];
    c = a&b;
    while any(c)
      b = xor(a, b);
      a = circshift(c, -1);
      c = a&b;
    end
    s = a+b;
  end
  
  function s = add_binary_Sardar(a,b)
    s = logical(str2double(num2cell(dec2bin(bin2dec(num2str(a)) +...
                                            bin2dec(num2str(b)), numel(a)+1))));
  end
  
  function s = add_binary_dato(a,b)
    m = length(a);
    s = zeros(m+1,1);
    n = length(a);
    c = 0;
    for ii = n:-1:1
      d = floor((a(ii)+b(ii)+c)/2);
      s(ii+1) = a(ii)+b(ii)+c-2*d;
      c = d;
    end
    s(1) = c;
    s = logical(s.');
  end
  

  And the results with my x64 MATLAB R2017a @ Win10 are:

  Sardar's method:    0.336414
  Dev-iL's method:    0.061656
  gnovice's method:   0.022031
  dato's method:      0.002123
  bi2de method:       0.000356
  

  So this should give us an idea which methods are faster (unless I messed the wrapper functions up greatly)...
  

  The advantage of the MapN method would be noticeable if the computation of the sum was some other, costlier operation.

Answer 2

Since you're dealing with binary numbers, why not use logical operators?

function s = add_binary(a, b)
  a = [0 a];
  b = [0 b];
  c = a&b;
  while any(c)
    b = xor(a, b);
    a = circshift(c, -1);
    c = a&b;
  end
  s = a+b;
end

And a test:

>> a = randi([0 1], [1 6])
a =
     0     1     0     1     0     1
>> b = randi([0 1], [1 6])
b =
     1     1     0     0     0     1
>> s = add_binary(a, b)
s =
     1     0     0     0     1     1     0

Answer 3

Use num2str to convert a and b to strings and use bin2dec to convert them to decimal. Then add them and convert the sum back to binary using dec2bin. Use num2cell to split the string and finally use str2double to get the desired result.

s=str2double(num2cell(dec2bin(bin2dec(num2str(a))+bin2dec(num2‌​str(b)))))

% Output for given a and b
%---------------------------
% s = 
%   1     1     0     0     1

Answer 4

here is my solution

function s=add_binary(a,b)
m=length(a);
s=zeros(m+1,1);
n=length(a);
c=0;
for ii=n:-1:1
    d=floor((a(ii)+b(ii)+c)/2);
   s(ii+1)=a(ii)+b(ii)+c-2*d;
   c=d;
 end
s(1)=c;
s=s';


end

>> s=add_binary(a,b)

s =

     1     1     0     0     1