VPF::Задачки для новичков! - Форум программистов

Чoо

Дата 16.12.2010, 16:21 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

глянул. что-то вообще ни чего не понял. В функции вычитания увидел ссылку на книгу Кнута, в трех томах. Глянул что там написано. Вопщем вычитание сделано на основе алгоритма, в котором не предусмотрены операции с отрицательными значениями. Далее Кнут пишет по поводу обратного и добавочного кода, которые можно использовать при работе с отрицательными числами. Может я что-то не понял?

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

Чoо

Дата 16.12.2010, 20:42 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

во.. сделал почти.. Пока еще с обратными кодами. Все работает, за исключением:
1. Есть положительные нули и отрицательные smile

2. в строке 169 я рассчитываю, что два раза вызовится конструктор копирования (для tmp1 и tmp2). Он так и вызвается, в отладчике если смотреть, в нем происходит копирование данных при двух вызовах. Однако содержимое tmp1 совсем не меняется, что приводит к краху программы. Что я не правильно написал?

Код


/*
    Класс "Длинное целое двоичное число".
    Объявите класс "длинное целое двоичное число", объект которого можно
    сконструировать из массива символов. Перегрузите все арифметические операции,
    операции сравнения, извлечение из потока и помещение в поток.
 */

#include <iostream>
#include <cstring>
#include <cstdlib>



class longvalue{
private:
    int *value; //массив-образ числа
    int size; //количество элементов в образе (что бы не выйти за границы массива)
    static const char *values; //хранит элементы, допустимые в данной системе счисления

    void get_image(const char* p); //получает образ числа (с конца)
    int char_to_int(const char c) const;
    char int_to_char(const int i) const;
    int* valuecpy() const; //копирует образ числа во вновь выделенную память


    void inverse(); //инвертирует значение value и возвращает указатель на новый массив
    void neg(); //дополняет до двух value и возвращает указатель на новый массив

    void allign(longvalue &p, const int new_size);
    void lv_inc(); //инкрементирует value

    /*конструктор, который используется только в neg => надо подумать как от него избавиться,
      так как он вызывает лишнюю путаницу*/
    longvalue(int* _value, int _size)
    {
        value = _value;
        size = _size;
    }

public:
    longvalue(){get_image("0");}
    longvalue(const char *v);
    /*нужно определить конструктор копирования, так как если использовать конструктор копирования
      по умолчанию, то он будет копировать только указатель на значение value, что не приемлимо
    */
    longvalue(const longvalue &p);
    ~longvalue()
    {
        free(value);
    }
    /*оператор присвоения
      при приравнивании объектов важно копировать область памяти, на которую указывает value
    */
    longvalue& operator =(const longvalue &p); //изменяет состояние объекта
    /*оператор помещения в поток*/
    friend std::ostream& operator <<(std::ostream& strm, const longvalue &p);
    /*оператор извлечения из потока*/
    friend std::istream& operator >>(std::istream& strm, longvalue &p);
    /*сложение*/
    longvalue operator +(const longvalue &p);
    void add(longvalue &p);
    /*вычитание*/
    longvalue operator -(const longvalue &p);
    /*сравнение. < -1, == 0, > 1 */
    int valuecmp(const longvalue &p1, const longvalue &p2) const;
    bool operator <(const longvalue &p);
    bool operator >(const longvalue &p);
    bool operator ==(const longvalue &p);



};
void longvalue::get_image(const char *p)
{    
    size = strlen(p);
    int char_count = size;
    int first_el = 0;
    if(p[0]=='-')
    {
        ++first_el;
        ++size; //что бы случайно не переполнить "разрядную сетку" добавляем нулевой элемент
        value = (int*)malloc(size*4);
        value[size-2] = 0;
        value[size-1] = 1; //знак отрицательного числа
    }
    else
    {
        ++size; ++size;
        value = (int*)malloc(size*4);
        value[size-2] = 0;
        value[size-1] = 0;
    }
    //образ числа будем харинть в прямом коде (понадобится для умножения и деления)
    for(int i = char_count-1, j = 0; i >= first_el; --i, ++j)
        value[j] = char_to_int(p[i]);
}

int longvalue::char_to_int(const char c) const
{
    int i;
    for(i = 0; i<=2; ++i) //работаем в двоичной системе счисления
        if(c == values[i])
            return i;
    return 0; //на всякий случай
}
char longvalue::int_to_char(const int i) const
{
    return values[i];
}
int* longvalue::valuecpy() const
{
    int* result =(int*) malloc(size*4);
    for(int i = 0; i < size; ++i)
        result[i] = value[i];
    return result;
}

longvalue::longvalue(const char *v)
{
    //работаем с двоичной системой счисления и предполагаем, что данные введены корректно
    get_image(v);
}
longvalue::longvalue(const longvalue &p)
{
    size = p.size;
    /*под значение надо выделить новую область памяти*/
    value = p.valuecpy();
}
longvalue& longvalue::operator =(const longvalue &p)
{
    size = p.size;
    free(value); //освобождаем память, так какследующая инструкция выделяет новую
    value = p.valuecpy();
    return *this;
}
std::ostream& operator <<(std::ostream& strm, const longvalue& p)
{
    bool out = false; //установится как только состоится вывод хотя бы одного элемента
    if(!p.value[p.size-1])
        strm << "+";
    else
        strm << "-";
    for(int i = p.size-2; i>=0; --i)
        if((i>0 && p.value[i]) || out)
        {
            strm << p.int_to_char(p.value[i]); //дружественный функции имеют доступ к полям и методам только через объект
            out = true;
        }
        else
            if(i==0)
                strm << p.int_to_char(p.value[i]);
    return strm;
}
/*операция извлечения из потока*/
std::istream& operator >>(std::istream& strm, longvalue &p)
{
    char *result = (char*)malloc(255); //пока что так :(
    std::cin >> result;
    int size = strlen(result);
    result = (char*)realloc(result,size+1);
    result[size] = '\0'; //realloc не оконечивает выделенную память нулем
    free(p.value);
    p.get_image(result);
    return strm;
}
/*нахождение суммы*/
longvalue longvalue::operator +(const longvalue &p)
{
    longvalue tmp1 = *this, tmp2 = p; //2 слагаемых
    if(tmp1.value[tmp1.size-1])
    {
        //первое слагаемое надо дополнить до двух, предварительно обратив знаковый разряд в ноль
        tmp1.value[tmp1.size-1] = !tmp1.value[tmp1.size-1];
        tmp1.inverse();
    }
    if(tmp2.value[tmp2.size-1])
    {
        tmp2.value[tmp2.size-1] = !tmp2.value[tmp2.size-1];
        tmp2.inverse();
    }

    tmp1.add(tmp2);
    if(tmp1.value[tmp1.size-1])
    {
        //получили отрицательное число. Его нужно преобразовать из обратного кода в прямой
        tmp1.value[tmp1.size-1] = !tmp1.value[tmp1.size-1];
        tmp1.inverse();
    }
    return tmp1;
}

void longvalue::allign(longvalue &p, const int new_size)
{
    int sign = p.value[p.size-1];
    p.value = (int*)realloc(value,new_size*4);
    for(int i = p.size-1; i<new_size-1; ++i)
        p.value[i] = 0;
    p.value[new_size-1] = sign;
    p.size = new_size;
}

void longvalue::add(longvalue &p)
{
    //если слагаемые имеют разное количество элементов, дополняем более маленькое
    if(this->size < p.size)
        allign(*this,p.size);
    else
        if(p.size < this->size)
            allign(p,size);
    //оба слагаемых имеют одинаковое количество элементов, что упрощает их сложение
    int* result=0; //накопитель для суммы
    int s; //сумма двух чисел из массивов
    int carry = 0; //перенос в старший разряд
    int i = 0; //индекс массива

    while(i<size)
    {
        s = value[i] + p.value[i] + carry;
        result = (int*)realloc(result,(i+1)*4);
        result[i] = s%2; //2 - двоичная система счисления
        carry = s/2;
        ++i;
    }       
    free(this->value);
    this->value = result;

    if(carry)
    {
        //остался перенос в старший разряд. Его нужно прибавить к результату
        this->lv_inc();
    }
}
void longvalue::lv_inc()
{
    int* value_tmp = (int*)malloc(size*4);
    value_tmp[0] = 1;
    for(int i = 1; i < size; ++i)
        value_tmp[i] = 0;
    longvalue tmp(value_tmp,size);
    this->add(tmp);
}

longvalue longvalue::operator -(const longvalue &p)
{
    longvalue tmp1(p), tmp2(*this);
    if(tmp1.value[tmp1.size-1])
        tmp1.value[tmp1.size-1] = !tmp1.value[tmp1.size-1];
    else
        tmp1.inverse();

    if(tmp2.value[tmp2.size-1])
    {
        tmp2.value[tmp2.size-1] = !tmp2.value[tmp2.size-1];
        tmp2.inverse();
    }
    tmp2.add(tmp1);
    if(tmp2.value[tmp2.size-1])
    {
        //получили отрицательное число. Его нужно преобразовать из обратного кода в прямой
        tmp2.value[tmp2.size-1] = !tmp2.value[tmp2.size-1];
        tmp2.inverse();
    }
    return tmp2;
}

/*сравнивает 2 значения друг с другом*/
int longvalue::valuecmp(const longvalue &p1, const longvalue &p2) const
{
    if(p1.value[p1.size-1] && !p2.value[p2.size-1])
        return -1;
    if(!p1.value[p1.size-1] && p2.value[p2.size-1])
        return 1;

    /*так как в начале числа могут присутствовать начальные нули
      сравнения старших разрядов не достаточно*/
    int i = p1.size - 2;
    int j = p2.size -2;
    while(i>=0 && j>=0)
    {
        if(i < j)
        {
            if(p2.value[j]>0)
            {
                if(!p1.value[p1.size-1]) //положительность второго значения проверять не обязательно
                    return -1;
                else
                    return 1;
            }
            else
                --j;
        }
        else
        if(i==j)
        {
            if(p1.value[i] > p2.value[j])
            {
                if(!p1.value[p1.size-1])
                    return 1;
                else
                    return -1;
            }
            if(p1.value[i] < p2.value[j])
            {
                if(!p1.value[p1.size-1])
                    return -1;
                else
                    return 1;
            }
            --i;
            --j;
        }
        else
        if(i > j)
        {
            if(p1.value[i]>0)
            {
                if(!p1.value[p1.size-1])
                    return 1;
                else
                    return -1;
            }
            else
                --i;
        }
    }
    return 0; //если вышли из цикла, значит i==j==-1, что означает - значения равны.
}
bool longvalue::operator <(const longvalue &p)
{
    if(valuecmp(*this,p)==-1)
        return true;
    return false;
}
bool longvalue::operator >(const longvalue &p)
{
    if(valuecmp(*this,p)==1)
        return true;
    return false;
}
bool longvalue::operator ==(const longvalue &p)
{
    if(valuecmp(*this,p)==0)
        return true;
    return false;
}

void longvalue::inverse()
{
    for(int i = 0; i<size; ++i)
        this->value[i] = !this->value[i];
}
void longvalue::neg()
{
    this->inverse();
    int* value_tmp = (int*)malloc(size*4);
    value_tmp[0] = 1;
    for(int i = 1; i < size - 1; ++i)
        value_tmp[i] = 0;
    longvalue tmp(value_tmp,size);
    this->add(tmp);
}

const char *longvalue::values = "0123456789ABCDEF";

int main()
{
    using std::cout;
    using std::endl;
    using std::cin;

    longvalue a;
    longvalue b;
    cout << "Введите двоичное число a>";
    cin >> a;
    cout << "Введите двоичное число b>";
    cin >> b;


    cout << "сложение:\n";
    longvalue c = a + b;
    cout << "(" << a << ")   +   ("<< b << ")   =   " << c << endl;
    cout << "вычитание:\n";
    c = a - b;
    cout << "(" << a << ")   -   ("<< b << ")   =   " << c << endl;
    cout << "сравнение:\n";
    if(a<b)
        cout << "(" << a << ")   <   ("<< b << ")" << endl;
    else
    if(a>b)
        cout << "(" << a << ")   >   ("<< b << ")" << endl;
    else
        cout << "(" << a << ")   =   ("<< b << ")" << endl;


    return 0;
}

Добавлено через 1 минуту и 36 секунд
да, умножение и деление не делал

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

bsa

Дата 16.12.2010, 23:27 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Чoо, вообще-то обратный код из прямого (и обратно) получается путем инвертирования всех битов и добавления единицы. Таким образом,0b11111111 == -1

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Чoо

Дата 17.12.2010, 00:18 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

bsa, обратный код получается инвертированием всех битов:
0b0000 0011 = 3
0b1111 1100 = -3

При сложении бит переноса (если он есть) добавляется к результату сложения.

Код


0b0000 0011 = 3
+
0b1111 1100 = -3
-----------------------
0b1111 1111

для перехода от обратного кода, если он показывает отрицательное число, к прямому, надо инвертировать все биты, кроме знакового:

Код


0b1000 0000 = -0

Код


0b0000 0011 = 3
+
0b1111 1101 = -2
-------------------------
0b0000 0000 (остался знак переноса)
+
0b0000 0001
------------------------
0b0000 0001 = 1 (3-2 = 1);

обратный код положительного числа соответствует прямому коду. ни чего менять не надо.

Дополнительный же код получается в 2 этапа:
1. Инверсия всех бит.
2. Дополнение до двух (тот же +1)

При сложении, если получаем перенос в старший разряд, то это просто игнорируется. При сложении чисел в дополнительном коде мы получаем число в прямом коде, если я правильно понял..

а в 169 строке, что может быть не так?

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

bsa

Дата 19.12.2010, 10:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Цитата(Чoо @ 17.12.2010, 01:18

)

bsa, обратный код получается инвертированием всех битов:
0b0000 0011 = 3
0b1111 1100 = -3

Я не понимаю, что ты этим хотел доказать. Проверяется очень просто:
-3 + 3 == 0 - сомнений не вызывает?
0b1111 1100 + 0b0000 0011 = 0b1111 1111, а это уже код -1. Таким образом, -3 == 0b1111 1101.
Ты не путай инверсию битов и инверсию знака. Отрицательное число - это дополнительный код и есть.

Добавлено через 11 минут и 21 секунду

Цитата(Чoо @ 17.12.2010, 01:18

)

При сложении чисел в дополнительном коде мы получаем число в прямом коде, если я правильно понял..

Нет. Ты получаешь число в дополнительном коде, если не происходит переполнения:
0b1111 1101 + 0b1111 1111 = 0b1111 1100 <=> -3 + -1 = -4

Переполнение можно определить через знаки исходных данных и результата, если переполнения нет, то знак результата должен совпадать со знаком одного из слагаемых.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Чoо

Дата 19.12.2010, 16:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

Цитата(bsa @ 19.12.2010, 10:57

)

Таким образом, -3 == 0b1111 1101.

ну.. это -3 в дополнительном коде. Так как есть дополнение до двух.
Тогда, что бы прояснить ситуацию, как будет выглядить число 3 в обратном и дополнительном коде, и как будет выглядеть число -3 (тоже в обратном и дополнительном коде).
Я так думаю, что так(по порядку как перечислял: прямой, обратный, дополнительный):
3:
0000 0011
0000 0011
0000 0011

-3:
1000 0011
1111 1100
1111 1101

тоесть я руководствовался таким представлением об обратном и дополнительном кодах. Правила сложения одинаковые, только по разному обрабатывается выход за пределы "разрядной сетки".

Добавлено через 2 минуты и 38 секунд

Цитата(bsa @ 19.12.2010, 10:57

)

Я не понимаю, что ты этим хотел доказать.

немножко ошибся smile

. Хотел написать обратный код отрицательного числа, соотв. для -3 ки.

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

bsa

Дата 19.12.2010, 19:07 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

почитай пожалуйста про двоичную арифметику.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Чoо

Дата 19.12.2010, 20:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

Ну у меня в конспекте по вычислительной технике написано именно так, как я пишу.
Сейчас погуглил, по поводу обратного кода и сложения в обратном коде (не в дополнительном) и вот что нашел:
http://www.ref.by/refs/67/15151/1.html
пункт 1.4.1. Представление чисел со знаками

ну вроде я всё правильно понял, по поводу сложения..

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

bsa

Дата 19.12.2010, 22:35 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Чoо, ладно. я понял, о чем речь. Мне и в голову не могло придти, что кто-то будет подобные теоретические изыски вдалбливать в головы новичков.
Имхо, "обратный код" вообще смысла не имеет. Лично я не вижу никакого применения для него. Дополнительный код актуален для чисел с фиксированной точностью. А вот прямой код имеет смысл применять для чисел с неограниченной точностью. Вот только знак не следует хранить в старшем бите. Посмотри на BigDigits, там для знака используется переменная, способная иметь три значения: положительно, нуль и отрицательно. Это сильно упрощает работу с числами.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Чoо

Дата 19.12.2010, 23:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

Цитата(bsa @ 19.12.2010, 22:35

)

Посмотри на BigDigits, там для знака используется переменная, способная иметь три значения: положительно, нуль и отрицательно. Это сильно упрощает работу с числами.

оК

.
Трудно разбираться в чужом коде, но что ж делать... попробую осилить

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

bsa

Дата 20.12.2010, 14:35 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Чoо, там код очень хороший. А разбираться в чужом коде полезно - не всегда ты будешь только свой писать. А потом, через пару лет свой же код вызывает возглас негодования: "Кто же так пишет?!?".

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

александра1987

Дата 3.5.2015, 12:16 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 3.5.2015

Репутация: нет
Всего: нет

Модератор: Сообщение скрыто.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »