Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Сложение битиков. Помогите оптимизировать

6.8K
21 июля 2008 года
Аццкий программер
91 / / 27.11.2006
Камрады, глянтье код, если не трудно.
Функция установки бита:
Код:
void BigInt::setBitField(int p,bool v)
{
    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
Код:
// метод сложения двух long (32 бита) в BigInt (512 бит)
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. Подскажите как можно его оптимизировать?
551
21 июля 2008 года
Pavia
357 / / 22.04.2004
power(2,x) замени на сдвиги.
сложение не оптимально. Для сложения работай с байтами, а еще лучши с word или dword'ами.
87
21 июля 2008 года
Kogrom
2.7K / / 02.02.2008
Аццкий программер, любите ребусы составлять? :)

Не указано, что такое part. Вероятно, это массив странных 5-битных чисел.

Не ясно зачем передавать в функцию setBitField номер нужного бита и номер нужного элемента массива part в одной переменной. Наверно, понятнее и проще будет, если вы его передадите в двух.

Зачем нужна строка
part[word]^=part[word]; ?
Вы хотите обнулить part[word] ?
14
21 июля 2008 года
Phodopus
3.3K / / 19.06.2008

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-битных?

38K
21 июля 2008 года
sneg
13 / / 16.07.2008
 
Код:
int word = p>>5;
  int pos = p - (word<<5);

  unsigned int mask = 1<<pos;
  if (v)
    part[pos] |= mask;
  else
    part[pos] &= ~0 ^ mask;
38K
21 июля 2008 года
sneg
13 / / 16.07.2008
т.е. =)
 
Код:
part[pos] &=  ~ mask;
87
21 июля 2008 года
Kogrom
2.7K / / 02.02.2008
Цитата: Phodopus
4-1: вроде так: if (v) part[p>>5] |= 1 << (p & 31) else part[p>>5] &= !(1 << (p & 31))


Красиво. Только "магические" числа немного портят картинку. Хотя это не ваша вина, а автора темы. Ну и это: вы тоже делаете не понятно что, если v == 0 )))

Цитата: Phodopus
4-2. а long long или к-нить __in64 не всеми компиляторами поддерживается?


Вроде бы не обязаны поддерживаться (хотя могут) - не помню, чтобы такие типы были в стандарте.

Цитата: Phodopus
3. Ужасен :) Зачем 512-битное число для сложения 2х 32-битных?


Вообще, интереснее было бы, если бы длинна BigInt была переменной и зависела бы от значений операндов и результата. Это можно было бы реализовать например с помощью vector.

14
21 июля 2008 года
Phodopus
3.3K / / 19.06.2008
Цитата: Kogrom
Ну и это: вы тоже делаете не понятно что, если v == 0 )))



Почему? Нужно привести правую часть к (long)?
Упс, еще ; перед else забыл - на си-то пишу от случая к случаю :)
Ааааааааааааааа! Битовое-то отрицание тильда :) ~

Цитата: Kogrom
Вообще, интереснее было бы, если бы длинна BigInt была переменной и зависела бы от значений операндов и результата. Это можно было бы реализовать например с помощью vector.



Вот-вот :) И я о том же

Цитата: Kogrom
Не ясно зачем передавать в функцию setBitField номер нужного бита и номер нужного элемента массива part в одной переменной. Наверно, понятнее и проще будет, если вы его передадите в двух.



Так он ж только номер бита передает, а номер элемента вычисляется

В итоге:

 
Код:
if (v)
    part[p >> 5] |= 1 << (p & 31);
else
    part[p >> 5] &= ~(1 << (p & 31));
87
21 июля 2008 года
Kogrom
2.7K / / 02.02.2008
Цитата: Phodopus
Так он ж только номер бита передает, а номер элемента вычисляется


Торможу немного. Действительно, пользователь не должен знать, что BigInt состоит из частей.

Ну и для порядка лучше заменить
void BigInt::setBitField(int p, bool v);
на
void BigInt::setBitField(unsigned int p, bool v);

6.8K
21 июля 2008 года
Аццкий программер
91 / / 27.11.2006
[QUOTE="Pavia"]power(2,x) замени на сдвиги.[/QUOTE]
мда, я видать был сильно обглюканый када такое написал. спс
[QUOTE="Pavia"]Для сложения работай с байтами, а еще лучши с word или dword'ами[/QUOTE]
наверное так и сделаю, спасибо.
6.8K
21 июля 2008 года
Аццкий программер
91 / / 27.11.2006
[QUOTE="Kogrom"]Не указано, что такое part. Вероятно, это массив странных 5-битных чисел.[/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). Функцию сложения лонгов использую для отладки с провркой ответа "ручками"(а точнее калькулятором :)
350
26 июля 2008 года
cheburator
589 / / 01.06.2006
Автор, а не проще ли воспользоваться vector<bool>,
или на крайний случай битовыми полями, типа того:
struct BitField
{
int b0:1;
int b1:1;
int b2:1;
int b3:1;
// и т. д.
}
14K
26 июля 2008 года
stimpi
100 / / 04.09.2007
Цитата: cheburator
Автор, а не проще ли воспользоваться vector<bool>,
или на крайний случай битовыми полями, типа того:
struct BitField
{
int b0:1;
int b1:1;
int b2:1;
int b3:1;
// и т. д.
}



Скотт Мейерс в своей книге "Эффективное использование STL" не рекомендует использовать vector<bool>, и приводит довольно веские аргументы

350
27 июля 2008 года
cheburator
589 / / 01.06.2006
Цитата: stimpi
Скотт Мейерс в своей книге "Эффективное использование STL" не рекомендует использовать vector<bool>, и приводит довольно веские аргументы


Хватит молиться богам, пора включать свои мозги.
vector<bool> неприменим во многих ситуациях, но судя по первоначальной постановке задачи - это именно та ситуация, когда он применим. Человеку, насколько я понял, нужен именно bool, упакованный в один бит. Что и есть vector<bool>.
Хотя я бы всё-таки применил битовые поля. Компилятор сам соптимизирует обращение к ним - сделает всё как надо, и побитовый сдвиг, и логическое И.

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог