Простой оператор + проблема ускользает от меня

Question

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

0x1000 + 0x100 + 0x10 -> 0x1210 ?????

Код выглядит следующим образом:

// values 0x123456 stored as: {12, 34, 56}
integer operator+(integer rhs){
    // internal list called 'value'
    std::list <uint8_t> top = value, bottom = rhs.value;
    if (value.size() < rhs.value.size())
        top.swap(bottom);
    top.push_front(0);                           // extra byte for carrying over
    while (bottom.size() + 1 < top.size())       // match up the byte sizes, other than the carry over
        bottom.push_front(0);
    bool carry = false, next_carry = false;
    for(std::list <uint8_t>::reverse_iterator i = top.rbegin(), j = bottom.rbegin(); j != bottom.rend(); i++, j++){
        next_carry = (((uint8_t) (*i + *j + carry)) <= std::min(*i, *j));
        *i += *j + carry;
        carry = next_carry;
    }
    if (carry)
        *top.begin() = 1;
return integer(top);
}

Может кто-нибудь сказать мне, что я делаю не так?

Answer 1

В вашем примере (0x100 + 0x10) вы начинаете с carry = false, *top.rbegin() = 0 и *bottom.rbegin() = 0.Когда мы погружаемся в цикл, мы видим следующий тест:

next_carry = (((uint8_t) (*i + *j + carry)) <= std::min(*i, *j));
// given *i == 0, *j == 0, and carry == false
// this will evaluate to TRUE

Поскольку next_carry переходит к следующему добавлению, вы получаете carry = true, когда оно должно быть false. Переключить условное на < std::min(*i, *j).

Answer 2

Рассмотрим, что происходит при добавлении двух нулевых цифр и переноса не было. *i + *j + carry == 0, что составляет <= than min(*i, *j). Таким образом, вы создаете вынос воздуха.

Если вы знаете, что работаете только с байтами, вы можете хранить *i + *j + carry в int, а затем переносить это просто sum / 256.

Answer 3

next_carry = ((*i + *j + carry) > 255); - правильный ответ, из-за дополнительного 1, так как *i + *j + carry может равняться минимуму std::min(*i, *j)

Answer 4

Пусть maxval будет максимальным значением uint8_t.Определить наличие next_carry следующим образом:

next_carry = false;
if( *i == maxval && ( *j > 0 || carry ) ) // excluding *i + carry > maxval case in next if
        next_carry = true;
    else
        if( *i + carry > maxval - *j ) ///  equal to *i + *j + carry > maxval
             next_carry = true;