Как вычесть два unsigned ints с обтеканием или переполнением

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

Возможно,

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

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

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

Ответы

Ответ 1

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

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

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

Ответ 2

Вот немного более подробная информация о том, почему он "просто работает", когда вы вычитаете "меньше" из "большего".

Несколько вещей, идущих в этом...
1. В аппаратном обеспечении вычитание использует добавление: соответствующий операнд просто отменяется перед добавлением.
2. В дополнении twos (которое почти все использует), целое число сбрасывается инвертированием всех битов, а затем добавлением 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

Ответ 3

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

unsigned r = x - y;

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

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

Решение:

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

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

Ответ 7

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

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

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

Ответ 8

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

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

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