Как вычесть два целых числа без знака с переносом или переполнением

Предполагая два целых числа unsigned:

• Если вы знаете, что одно должно быть «больше», чем другое, просто вычтите. Это сработает при условии, что вы не оборачивались более одного раза (очевидно, если вы это сделали, вы не сможете сказать).
• Если вы не знаете, что одно больше другого, вычтите и приведите результат к целому числу со знаком той же ширины. Это будет работать при условии, что разница между ними находится в диапазоне подписанного целого числа (если нет, вы не сможете сказать).

Уточняю: сценарий, описанный автором постера, кажется, сбивает людей с толку, но он типичен для монотонно увеличивающихся счетчиков фиксированной ширины, таких как аппаратные счетчики тиков или порядковые номера в протоколах. Счетчик идет (например, для 8 бит) 0xfc, 0xfd, 0xfe, 0xff, 0x00, 0x01, 0x02, 0x03 и т. д., и вы знаете, что из двух значений x и y, которые у вас есть, x приходит позже. Если x==0x02 и y==0xfe, вычисление xy (как 8-битный результат) даст правильный ответ 4, предполагая, что вычитание двух n-битных значений выполняет перенос по модулю 2< sup>n - что C99 гарантирует для вычитания значений без знака. (Примечание: стандарт C не гарантирует такое поведение для вычитания значений со знаком.)

Вот еще немного подробностей о том, почему это «просто работает», когда вы вычитаете «меньшее» из «большего».

Несколько вещей, связанных с этим…
1. В аппаратном обеспечении вычитание использует сложение: соответствующий операнд просто инвертируется перед добавлением.
2. В дополнении до двух (которое используется почти во всем) целое число инвертируется. инвертируя все биты, а затем добавляя 1.

Аппаратное обеспечение делает это более эффективно, чем кажется из приведенного выше описания, но это основной алгоритм вычитания (даже когда значения беззнаковые).

Итак, давайте рис. 2 — 250, используя 8-битные целые числа без знака. В двоичном виде у нас есть

  0 0 0 0 0 0 1 0  
- 1 1 1 1 1 0 1 0

Мы отрицаем вычитаемый операнд, а затем добавляем. Напомним, что для инвертирования мы инвертируем все биты, а затем добавляем 1. После инвертирования битов второго операнда мы имеем

0 0 0 0 0 1 0 1  

Тогда после прибавления 1 имеем

0 0 0 0 0 1 1 0  

Теперь выполняем сложение...

  0 0 0 0 0 0 1 0   
+ 0 0 0 0 0 1 1 0

= 0 0 0 0 1 0 0 0 = 8, which is the result we wanted from 2 - 250

Может я не понимаю, но что не так с:

unsigned r = x - y;

Вопрос, как уже было сказано, сбивает с толку. Вы сказали, что вычитаете беззнаковые значения. Если x всегда больше, чем y, как вы сказали, то x - y не может обернуться или переполниться. Итак, вы просто делаете x - y (если это то, что вам нужно) и все.

Это эффективный способ определить количество свободного места в кольцевом буфере или выполнить управление потоком в скользящем окне. Используйте unsigned ints для head и tail - увеличьте их и дайте им обернуться! Длина буфера должна быть степенью двойки.

free = ((head - tail) & size_mask), где size_mask — это 2^n-1 размер буфера или окна.

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

Если вы знаете, что x — меньшее значение, следующий расчет просто работает:

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    uint8_t res = y - x;
    printf("Expect 20: %d\n", res); // res is 20

    return 0;
}

Если вы не знаете, какой из них меньше:

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    int8_t res1 = (int8_t)x - y;
    int8_t res2 = (int8_t)y - x;
    printf("Expect -20 and 20: %d and %d\n", res1, res2);

    return 0;
}

Где разница должна быть в пределах диапазона uint8_t в этом случае.

Эксперимент с кодом помог мне лучше понять решение.

Проблема должна быть сформулирована следующим образом:

Предположим, что положение (угол) двух указателей a и b часов задается uint8_t. Вся окружность делится на 256 значений uint8_t. Как можно эффективно рассчитать меньшее расстояние между двумя указателями?

Решение:

uint8_t smaller_distance = abs( (int8_t)( a - b ) );

Я подозреваю, что нет ничего более эффективного, иначе было бы что-то более эффективное, чем abs().

Чтобы повторить ответ всех остальных, если вы просто вычтете два и интерпретируете результат как неподписанный, все будет в порядке.

Если только у вас нет явного контрпримера.

Ваш пример x = 0x2, y= 0x14 не приведет к 0x4, он приведет к 0xEE, если только у вас нет дополнительных ограничений на математику, которые не указаны.