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

Question

Есть два беззнаковых целых (x и y), которые необходимо вычесть. х всегда больше, чем у. Тем не менее, оба х и у можно обернуть вокруг; например, если они были оба байта, после 0xff следует 0x00. Проблема в том, что если x оборачивается, а y - нет. Теперь х кажется меньше, чем у. К счастью, x не будет оборачиваться дважды (гарантируется только один раз). Предполагая, байты, x обернут и теперь 0x2, тогда как у нет и 0xFE. Правильный ответ x - y должен быть 0x4.

Может быть,

( x > y) ? (x-y) : (x+0xff-y);

Но я думаю, что есть другой способ, связанный с комплиментом 2s? И в этой встроенной системе x и y являются самыми большими типами int без знака, поэтому добавление 0xff ... невозможно

Каков наилучший способ написать утверждение (целевой язык - C)?

Answer 1

Предполагая два целых числа без знака :

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

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

Answer 2

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

Пара вещей, входящих в это ...
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

Answer 3

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

unsigned r = x - y;

Answer 4

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

Answer 5

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

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

Answer 6

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

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

Решение:

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

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

Answer 7

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

Если вы знаете, что 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.

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

Answer 8

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

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

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