Это только одна из многих возможных реализаций.Он не должен быть самым быстрым и ярким.Он также может быть сильно укорочен, но для того, чтобы показать промежуточные шаги, я оставил его довольно развернутым.
Шаг 1: подготовить все шаги (строки)
Вместо этогонеобходимости управлять добавлением нулей здесь или там, в зависимости от длины каждого входа, я считаю более простым просто определить матрицу, достаточно большую, чтобы вместить все наши значения и циклические сдвиги, которые мы должны будем выполнить:
%% Input values
a = [ 1 1 0 0 1 1 ] ;
b = [ 1 0 1 1 ] ;
%% create all the steps
nstep = numel(b) ;
steps = bsxfun( @times , flipud(b.') , a) ;
На этом этапе ваша матрица steps выглядит следующим образом:
>> steps
steps =
1 1 0 0 1 1
1 1 0 0 1 1
0 0 0 0 0 0
1 1 0 0 1 1
Каждая строка представляет полный вектор a, умноженный на каждый элемент b Прежде чем мы сможем суммировать эти строки, нам нужносдвинуть каждую строку так, чтобы она выровнялась с правильной степенью 2. Для этого мы сначала дополним матрицу необходимыми нулями слева, а затем будем использовать circshift:
%% pad the matrix to prepare for the shifts
pad = zeros( nstep , nstep ) ;
mat = [pad steps] ;
%% shift the step lines
for k=2:nstep
mat(k,:) = circshift(mat(k,:),[0,-(k-1)]) ; % shift each line to the left by [k-1]
end
К настоящему времени ваша матрица mat выглядит следующим образом:
>> mat
mat =
0 0 0 0 1 1 0 0 1 1
0 0 0 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 0 0 0
Почти там, теперь нам просто нужно сложить строки, чтобы получить наш результат.К сожалению, MATLAB не имеет суммирования бинарного , построенного таким образом, поэтому нам придется реализовать его самостоятельно.Я дам 2 метода: loop версия (более читабельная) и векторизованная версия (более критично).
Шаг 2: Суммирование
%% [LOOP method] Do the summation
ncol = size(mat,2) ;
res = zeros( 1 , ncol ) ; % pre-allocate result line
sumline = sum(mat) ; % put sum of each column in a buffer
c = 0 ; % carry
for k=ncol:-1:2 % we process the column from right to left
s = sumline(k)+c ; % sum of the column [k] plus the carry
res(k) = mod( s , 2 ) ; % result for this column
c = floor(s/2) ; % carry value for the next column
end
% now we are almost finished but there may be value left in the carry
res(1) = c % set the (MSb) on the left
Обратите внимание, что цикл останавливается на столбце 2 вместо столбца 1. Это потому, что я уже добавил еще один столбец слева, который будет содержать только нули.Это сделано для того, чтобы в переменной res было достаточно столбцов для размещения carry на случай, если оно не равно нулю.
Ниже приведена более компактная версия (из шага 2), но она будетдают точно такие же результаты:
%% [Vectorised method] ... just as good but more cryptic
sumline = sum(mat) ; % put sum of each column in a buffer
carrytmp = floor(sumline/2) ; % calculate all the "carry" values (1/2)
carry = carrytmp + circshift( carrytmp, [0,-1] ) ; % calculate all the "carry" values (2/2)
tsum = sumline + circshift( carry , [0,-1] ) ; % total sum
res = mod( tsum , 2 ) ; % final result
Ну вот, извините за длинный пост, но я хотел подробно описать шаги.Если вы берете только код, вы можете сжать его в короткую функцию:
function res = binary_multiplication(a,b)
nstep = numel(b) ;
mat = [zeros( nstep , nstep ) , bsxfun( @times , flipud(b.') , a) ] ;
for k=2:nstep
mat(k,:) = circshift(mat(k,:),[0,-(k-1)]) ;
end
sumline = sum(mat) ;
res = mod(sumline+circshift(floor(sumline/2)+circshift(floor(sumline/2),[0,-1]),[0,-1]),2) ;