Сложение битиков. Помогите оптимизировать
Функция установки бита:
{
int word = p/32;
int pos = p-word*32;
long mask=0;
mask=pow(2,pos);
if(v)
part[word]|=mask;
else
part[word]^=part[word];
}
Функция сложения двух long'ов в один BigInt
void BigInt::add(BigInt* rec, long add0, long add1)
{
bool carry=0; // перенос
for(int i=0;i<33;i++) // от 0 до 33 т.к. 0xFFFFFFFF + 0xFFFFFFFF = 0x1FFFFFFFE
{
if(!(add0 & 0x01) && !(add1 & 0x01) && !carry) // если 0+0+0
{
add0>>=1;
add1>>=1;
continue;
}
//////////////////////////////////////////////////////////////////////
if(!carry) // сложение БЕЗ переноса из пред. разряда
{
if((add0 & 0x01) == (add1 & 0x01)) // если 1+1 или 0+0
{
rec->setBitField(i,0); // i-ый бит ответа устанавливаем в 0
if(add0&0x01==1) // если 1+1
carry=1; // то появляется перенос
}
else // если 1+0 или 0+1
{
rec->setBitField(i,1); // i-ый бит ответа устанавливаем в 1
carry=0; // переноса не будет
}
}
/////////////////////////////////////////////////////////////////////
else // сложение С переносом из пред. разряда
{
if((add0 & 0x01) == (add1 & 0x01)) // если 1+1 или 0+0
{
rec->setBitField(i,1); // i-ый бит ответа устанавливаем в 1
if(add0&0x01==1) // если 1+1
carry=1; // то появляется перенос
else // иначе надо сбросить перенос который
carry=0; // сейчас == 1, а то зациклимся
}
else // если 1+1 или 0+0
{
rec->setBitField(i,0); // i-ый бит ответа устанавливаем в 0
carry=0; // переноса не будет
}
}
//////////////////////////////////////////////////////////////////////
add0>>=1; // сдвигаем операнды на 1 бит
add1>>=1;
}
}
Два вопроса:
1. Насколько ужасен этот код?
2. Подскажите как можно его оптимизировать?
сложение не оптимально. Для сложения работай с байтами, а еще лучши с word или dword'ами.
Не указано, что такое part. Вероятно, это массив странных 5-битных чисел.
Не ясно зачем передавать в функцию setBitField номер нужного бита и номер нужного элемента массива part в одной переменной. Наверно, понятнее и проще будет, если вы его передадите в двух.
Зачем нужна строка
part[word]^=part[word]; ?
Вы хотите обнулить part[word] ?
1. Функция установки бита:
2. Функция сложения двух long'ов в один BigInt
Два вопроса:
3. Насколько ужасен этот код?
4. Подскажите как можно его оптимизировать?
4-1: вроде так: if (v) part[p>>5] |= 1 << (p & 31) else part[p>>5] &= !(1 << (p & 31))
4-2. а long long или к-нить __int64 не всеми компиляторами поддерживается?
3. Ужасен :) Зачем 512-битное число для сложения 2х 32-битных?
int pos = p - (word<<5);
unsigned int mask = 1<<pos;
if (v)
part[pos] |= mask;
else
part[pos] &= ~0 ^ mask;
Красиво. Только "магические" числа немного портят картинку. Хотя это не ваша вина, а автора темы. Ну и это: вы тоже делаете не понятно что, если v == 0 )))
Вроде бы не обязаны поддерживаться (хотя могут) - не помню, чтобы такие типы были в стандарте.
Вообще, интереснее было бы, если бы длинна BigInt была переменной и зависела бы от значений операндов и результата. Это можно было бы реализовать например с помощью vector.
Почему? Нужно привести правую часть к (long)?
Упс, еще ; перед else забыл - на си-то пишу от случая к случаю :)
Ааааааааааааааа! Битовое-то отрицание тильда :) ~
Вот-вот :) И я о том же
Так он ж только номер бита передает, а номер элемента вычисляется
В итоге:
part[p >> 5] |= 1 << (p & 31);
else
part[p >> 5] &= ~(1 << (p & 31));
Торможу немного. Действительно, пользователь не должен знать, что BigInt состоит из частей.
Ну и для порядка лучше заменить
void BigInt::setBitField(int p, bool v);
на
void BigInt::setBitField(unsigned int p, bool v);
мда, я видать был сильно обглюканый када такое написал. спс
[QUOTE="Pavia"]Для сложения работай с байтами, а еще лучши с word или dword'ами[/QUOTE]
наверное так и сделаю, спасибо.
пятибитные числа мне тоже кажутся странными :)
[QUOTE="Kogrom"]Зачем нужна строка
part[word]^=part[word]; ?[/QUOTE]
это глюк. имелось ввиду part[pos] &= ~ mask;, как правильно заметил товарищ sneg :)
[QUOTE="Phodopus"]3. Ужасен Зачем 512-битное число для сложения 2х 32-битных?[/QUOTE]
я прощу прощения, похоже, действительно, необходимо было влкючить описание класа BigInt. Но мне показалось такое говорящее название лучше всяких объяснений :)
Класс BigInt содержит в себе 16 DWORDов 0...15. За счет этого хранит числа в диапазоне 0...2^512. Я его собираюсь использовать при реализации алгоритма RSA для вычисления простых чисел (експоненты закрытого и открытого ключа ~2^256 модуль ~2^512). Функцию сложения лонгов использую для отладки с провркой ответа "ручками"(а точнее калькулятором :)
или на крайний случай битовыми полями, типа того:
struct BitField
{
int b0:1;
int b1:1;
int b2:1;
int b3:1;
// и т. д.
}
или на крайний случай битовыми полями, типа того:
struct BitField
{
int b0:1;
int b1:1;
int b2:1;
int b3:1;
// и т. д.
}
Скотт Мейерс в своей книге "Эффективное использование STL" не рекомендует использовать vector<bool>, и приводит довольно веские аргументы
Хватит молиться богам, пора включать свои мозги.
vector<bool> неприменим во многих ситуациях, но судя по первоначальной постановке задачи - это именно та ситуация, когда он применим. Человеку, насколько я понял, нужен именно bool, упакованный в один бит. Что и есть vector<bool>.
Хотя я бы всё-таки применил битовые поля. Компилятор сам соптимизирует обращение к ним - сделает всё как надо, и побитовый сдвиг, и логическое И.