Блог

Я создал простую функцию, которую я вызвал symmetricDelta() , которая вычисляет дельту между value и previous «симметрично». Что я имею в виду под этим: рассмотрим числовую строку, например 0 , до ULLONG_MAX , где вы соединили левый и правый концы числовой строки… Чтобы определить «симметричную» дельту, предположим, что изменение положительное, если value - previous оно меньше половины диапазона, в противном случае предположим, что изменение отрицательное, и мы обернули числовую строку.

Смотрите простую версию этого для uint64_t s ниже:

 int64_t symmetricDelta(uint64_t value, uint64_t previous) {
    if (value-previous < (1ULL << 63)) {
        uint64_t result = value - previous;
        return resu<
    } else {
        uint64_t negativeResult = previous - value;
        return -1 * negativeResu<
    }
}
  

Использование:

     uint64_t value = ULLONG_MAX;
    uint64_t previous = 0;

    // Result: -1, not UULONG_MAX
    cout << symmetricDelta(value, previous) << endl;
  

Демонстрация: https://onlinegdb.com/BJ8FFZgrP

Другие примеры значений, uint8_t для простоты предположим версию:

 symmetricalDifference(1, 0) == 1
symmetricalDifference(0, 1) == -1
symmetricalDifference(0, 255) == 1
symmetricalDifference(255, 0) == -1
symmetricalDifference(227, 100) == 127
symmetricalDifference(228, 100) == -128
  

Мой вопрос: существует ли «официальное» название для того, что я называю «симметричным вычитанием»? Это похоже на то, что уже может быть реализовано в C STL, но я бы даже не знал, что искать…

ДА. Имя — вычитание по модулю 2^64 . И это идентично тому, что ваша машина делает с инструкцией

 int64_t symmetricDelta(uint64_t value, uint64_t previous) {
    return (int64_t)(value-previous);
}
  

В C и C арифметика без знака определена для обтекания, эффективно соединяя концы представимого диапазона чисел в круг. Это основа для представления целых чисел со знаком с двумя дополнениями: ваш процессор просто объявляет, что половина числового круга интерпретируется как отрицательная. Эта часть является верхней частью в unsigned, где -1 соответствует максимально представимому целому числу без знака. Просто потому, что 0 следующий по кругу.

Примечание:
Это позволяет процессору использовать одну и ту же схему для арифметики со знаком и без знака. Процессор предоставляет только add инструкцию, которая используется независимо от того, следует ли интерпретировать числа как подписанные или беззнаковые. Это верно для сложения, вычитания и умножения, все они существуют как инструкции без учета знака. Только разделение реализовано в подписанном и неподписанном вариантах, как и инструкции сравнения / биты флага, которые предоставляет центральный процессор.

Примечание 2:
Приведенное выше не совсем верно, поскольку современные процессоры реализуют насыщающую арифметику как часть своих векторных единиц (AVX и т. Д.). Поскольку насыщающая арифметика означает обрезку результата до концов представимого диапазона вместо обтекания, это обрезание зависит от того, где предполагается круг чиселбыть нарушенным. Таким образом, насыщающие арифметические инструкции обычно существуют в вариантах со знаком и без знака.

Конец ненужного фонового перебора…

Итак, когда вы вычитаете два числа в представлении без знака, результатом является количество шагов без знака, которое вам нужно предпринять, чтобы достичь минимума из вычитания. И, переосмысливая результат как целое число со знаком, вы интерпретируете длинный маршрут (который проходит более половины круга) как соответствующий короткий маршрут в противоположном направлении.

Есть одна ошибка: 1 << 63 не представляется. Он находится точно на противоположной стороне числового круга от нуля, и поскольку его знаковый бит установлен, он интерпретируется как -(1 << 63) . Если вы попытаетесь отрицать это, битовый шаблон не изменится ни на один бит (точно так же, как -0 == 0 ), поэтому ваш компьютер с радостью заявляет об этом - -(1 << 63) == -(1 << 63) . Вероятно, для вас это не проблема, но лучше знать об этом, потому что это может вас укусить.