Это правильная реализация оператора << / >>? - PullRequest
Новая
       58

Это правильная реализация оператора << / >>?

0 голосов
/ 27 июня 2011

это правильные реализации операторов << и >> для битового сдвига? по какой-то причине в моем операторе /, где задействованы только эти 2 оператора, что-то допускает глупый прыжок, который вызывает неправильное деление. 

    // the value is stored msb in a list of uint8_t
    // so 0x123456 will be stored in the list as {0x12, 0x34, 0x56}
    integer operator<<(size_t shift){
        std::list <uint8_t> out = value;
        for(unsigned int i = 0; i < (shift >> 3); i++)
            out.push_back(0);
        shift &= 7;
        if (shift){
            out.push_front(0);
            std::list <uint8_t>::iterator i = out.begin(), j = out.end();
            i++; j--;
            for(; i != j; i++){
                uint8_t temp = *i >> (8 - shift);
                --i;
                *i += temp;
                i++;
                *i = (uint8_t) (*i << shift);
            }
            uint8_t temp = *i >> (8 - shift);
            i--;
            *i += temp;
            i++;
            *i <<= shift;
        }
        return integer(out);
    }

    integer operator>>(size_t shift){
        std::list <uint8_t> out = value;
        for(unsigned int i = 0; i < (shift >> 3); i++)
            out.pop_back();
        shift &= 7;
        if (shift){
            std::list <uint8_t>::reverse_iterator i = out.rbegin(), j = out.rend();
            j--;
            for(; i != j; i++){
                *i >>= shift;
                i++;
                uint8_t temp = *i << (8 - shift);
                i--;
                *i += temp;
            }
            *j >>= shift;
        }
        return integer(out);
    }

вот что я делаю: 

integer(1234567) / integer(6)

inside division algorithm (long division):

numerator       largest multiple of denomiator < numeator

12d687          0c0000
06d687          060000
d687            c000
1687            0c00
0a87            0600
0487            0300
0187            0c        <-- where did this come from??
017b            0180

ошибка в одном из показанных операторов или в каком-то другом операторе?

Вот мой весь код: http://ideone.com/ncq9S

1 Ответ

1 голос
/ 27 июня 2011 
template <typename T>

Это действительно нужно параметризовать?Казалось бы, любая величина сдвига может быть сохранена в size_t, и преобразование в size_t неявно или явно было бы хорошей идеей перед началом остальной части процесса. 

integer operator<<(T shift){

Обычно двоичный operator функции лучше всего реализованы как не-члены friend s.Например, при создании указателя this учитывается меньше преобразований, чем для общих операндов.Я бы написал friend integer operator<< ( integer lhs, size_t shift ). 

    std::list <uint8_t> out = value;

Если вы используете friend и передачу по значению, то эта копия создается неявно.Компилятору также легче избавиться от него, если вы на самом деле просто изменяете один объект, например q = q << 3. 

    for(unsigned int i = 0; i < (shift >> 3); i++)// get rid of bytes if shift > 8

Будьте осторожны в условиях цикла.Вы применяете оператор к высокоуровневому типу, который может вызвать дорогостоящие вычисления (или даже бесконечную рекурсию, если T равен integer! 

    shift &= 7;                                   // shift by less than a byte

На данный момент, если shift == 0все готово. Лучше всего вставить условное return здесь. Кроме того, теперь диапазон ограничен действительно , поэтому присвойте более узкий тип, чем T. 

    out.push_front(0);                            // extra byte for overflow

Этонеобходим только в том случае, если байт будет отличен от нуля. Вероятно, лучше всего выполнить специальный случай для первой операции и сделать условным push_front вместо специального случая для последнего.

... Хм, он выглядит как operator>> выполняется больше… переход к этому… 

    for(; i != j; i++){
        i++;
        uint8_t temp = *i << (8 - shift);
        i--;
        *i += temp;
    }
    *j >>= shift;

Очевидно, что оператор >> отсутствует в цикле. Попробуйте *i = *i >> shift + temp. Кроме того, я не вижу, как список становится короче.Это сделано в integer::integer( list<…> )?

Однако я не могу реально увидеть, что вызывает поведение в опубликованном выводе. Ведущий ноль, вероятно, является результатом безусловного push_front в operator<<, нообразец, который я ожидал бы, является c, 6, 3, 18, c,….Кажется, вы не повторяете какую-либо последовательность, но вместо этого переходите случайным образом.

Может быть, код деления или конструктор класса могли бы дать подсказки.

...