массивы — умножение длинных рук в переполнении стека
Я пытаюсь реализовать метод умножения длинных рук для 8-битных двоичных чисел, хранящихся в двух массивах BeforeDecimal1 and BeforeDecimal2, Проблема в том, что я всегда получаю неправильный результат. Я пытался выяснить проблему, но не смог этого сделать. Вот код:
Это гораздо более тонкий код, чем предыдущий. Это дает мне результат, но результат не является правильным.
int i = 0, carry = 0;
while(true)
{
if(BeforeDecimal2[i]!=0)
for(int j=7;j>=0;j--)
{
if(s[j]==1 && BeforeDecimal1[j]==1 && carry==0)
{
cout<<"Inside first, j= "<<j<<endl;
carry=1;
s[j]=0;
}
else
if(s[j]==1 && BeforeDecimal1[j]==0 && carry==1)
{
cout<<"Inside second, j= "<<j<<endl;
carry=1;
s[j]=0;
}
else
if(s[j]==0 && BeforeDecimal1[j]==0 && carry==1)
{
cout<<"Inside third, j= "<<j<<endl;
carry=0;
s[j]=1;
}
else
if(s[j]==0 && BeforeDecimal1[j]==0 && carry==0)
{
cout<<"Inside fourth, j= "<<j<<endl;
carry=0;
s[j]=0;
}
else
if(s[j]==0 && BeforeDecimal1[j]==1 && carry==0)
{
cout<<"Inside fifth, j= "<<j<<endl;
carry=0;
s[j]=1;
}
else
if(s[j]==1 && BeforeDecimal1[j]==1 && carry==1)
{
//cout<<"Inside fifth, j= "<<j<<endl;
carry=1;
s[j]=1;
}
else
if(s[j]==1 && BeforeDecimal1[j]==0 && carry==0)
{
//cout<<"Inside fifth, j= "<<j<<endl;
carry=0;
s[j]=1;
}
else
if(s[j]==0 && BeforeDecimal1[j]==1 && carry==1)
{
//cout<<"Inside fifth, j= "<<j<<endl;
carry=1;
s[j]=0;
}
}
for(int h=7;h>=0;h--)
{
if(h==0)
{
BeforeDecimal1[0]=0; // that is inserting zeros from the right
}
else
{
BeforeDecimal1[h]=BeforeDecimal1[h-1];
BeforeDecimal1[h-1]=0;
}
}
if(i==3)
break;
i++;
}
С уважением
Решение
Возможно, было бы проще создать резервную копию и начать с 8-разрядных двоичных чисел, хранящихся в виде 8-разрядных двоичных чисел. Как и в случае десятичного умножения, мы начинаем с нескольких цифр. Мы берем значения умножения на эти отдельные цифры и складываем их вместе, чтобы получить окончательный результат. Разница (или одно очевидное отличие) заключается в том, что мы работаем в двоичном формате, все наши цифры представляют степени двойки, поэтому мы можем получить каждый промежуточный результат, просто сдвинув входное значение.
Поскольку он двоичный, у нас есть только две возможности для каждой цифры: если это 0, то нам нужно добавить 0 раз, когда другое число сдвинуто влево на соответствующее количество мест. Очевидно, 0 раз все равно 0, поэтому мы просто ничего не делаем в этом случае. Другая возможность состоит в том, что у нас есть 1, и в этом случае мы добавляем 1 раз другое число, сдвинутое влево на соответствующее количество мест.
Например, давайте рассмотрим что-то вроде 17 x 5 или (в двоичном виде) 10001 x 101.
10001
101
------
10001
+ 1000100
--------
= 1010101
Преобразовав это в нечто более узнаваемое, мы получаем 0x55 или 85d.
В коде этот процесс получается довольно коротким и простым. Начните с результата 0. Проверьте, установлен ли младший значащий бит в одном операнде. Если так, добавьте другой операнд к результату. Сдвиньте один операнд немного вправо, а другой немного влево и повторяйте, пока операнд, который вы сдвигаете вправо, не станет равным 0:
unsigned short mul(unsigned char input1, unsigned char input2) {
unsigned short result = 0;
while (input2 != 0) {
if (input2 & 1)
result += input1;
input1 <<= 1;
input2 >>= 1;
}
return result;
}
Если вы хотите работать со знаковыми числами, как правило, проще всего определить знак результата отдельно и выполнить умножение на абсолютные значения.
Другие решения
У вас проблема в следующих строках кода
if(reverse==0)
{
totalReverse=totalReverse-1;
reverse=totalReverse;
}
после некоторых итераций внутреннего цикла for (на основе индекса j) значения обратного хода должны переходить в отрицательное значение, а при обратном ходе менее 3 следует генерировать исключение.
Вы используете этот код без обработки исключений?
для меня это пахнет сдвинуть и добавить. есть ли требование, что вы можете использовать только операции, имитирующие логические элементы?
для тебя полный сумматор у вас есть 3 входа s (s [j]), b (BeforeDecimal1 [j]), c (перенос) и два выхода ns (новый s [j]), nc (новый перенос)
стол выглядит так
s b c ns nc
0 0 0 0 0 handled in v5 clause 4
0 0 1 1 0 handled in v5 clause 3
0 1 0 1 0 handled in v6 clause 5
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1 handled in v5 clause 2
1 1 0 0 1 handled in v5 clause 1
1 1 1 1 1
Ваш код охватывает только 4 (теперь 5) из этих 8 пунктов
чтобы избежать уродливых граблей if-else-if, я рекомендую использовать временные переменные результата (carry и s по-прежнему действительны в следующем предложении if)
когда вы анализируете таблицу, вы также можете сделать это (псевдобулевая запись)
nc = s && b || s && c || b && c;
ns = s XOR b XOR c; // there is no XOR in C++: axb = a&&!b || !a&&b
арифметическая запись
nc = (s + b + c) / 2;
ns = (s + b + c) % 2;// [...]
for(int j=7;j>=0;j--)
{
// start changed code
const int sum = s[j] + BeforeDecimal1[j] + carry;
s[j]=sum % 2;
carry=sum / 2;
// end changed code
}
// [...]
вот хорошая симуляция вашей проблемы Последовательное Умножение
Если в вашем требовании не указано иное, что пока не ясно из вашего вопроса или любых ваших комментариев, нет необходимости обрабатывать массивы битов. Массивы байтов гораздо более эффективны как в пространстве, так и во времени.
Вам не нужен этот исчерпывающий взрыв дел тоже. Единственный особый случай, когда любой операнд равен нулю, т.е. a[i]|b[i] == 0, когда
result[i] = carry;
carry = 0;
Все остальные случаи могут быть обработаны:
result[i] = a[i]*b[i]+carry;
carry = (result[i] >>> 8) & 1;
result[i] &= 0xff;
Я не вижу особого смысла в именах BeforeDecimal1 а также BeforeDecimal2 или.