C++: разница двух 64-битных целых чисел без знака в 64-битном целом числе со знаком

Я пытаюсь написать функцию на С++, которая принимает два 64-битных целых числа без знака и возвращает их разницу в 64-битном целом со знаком. Это кажется немного сложным из-за ситуации с переполнением. Поскольку входные данные представляют собой два положительных целых числа без знака, и если абсолютная разница между ними больше, чем максимальное значение со знаком (INT64_MAX), то разница не может быть передана через целое число со знаком. Итак, я написал следующую реализацию, и мне было интересно, во-первых, правильно ли это функционально, а во-вторых, есть ли более простая реализация. Любые предложения будут ценны. Спасибо! (Я собираюсь заменить assert на исключение, пока оно есть!)

int64_t GetDifference(uint64_t first, uint64_t second) {
  uint64_t abs_diff = (first > second) ? (first - second): (second - first);    
  uint64_t msb_abs_diff = (abs_diff >> (sizeof(abs_diff)*8 - 1)) & 1;
  assert(msb_abs_diff == 0);
  int64_t diff = first - second;
  return diff;
}

c++ unsigned-integer
person Abhi    schedule 16.01.2012    source источник
comment
Хорошо, спасибо всем за ответы! Меня больше беспокоила функциональная правильность, что, я думаю, нормально. Все улучшения действительны, хотя и не отличаются принципиально, и я бы их включил.   -  person Abhi    schedule 17.01.2012
comment
любой приличный компилятор должен быть в состоянии оптимизировать такой код, но убедиться, что он правильный.   -  person Luka Rahne    schedule 17.01.2012

Ответы (4)


arrow_upward
6
arrow_downward

Мне это кажется более простой и читаемой реализацией.

int64_t GetDifference(uint64_t first, uint64_t second) {
    uint64_t abs_diff = (first > second) ? (first - second): (second - first);
    assert(abs_diff<=INT64_MAX);
    return (first > second) ? (int64_t)abs_diff : -(int64_t)abs_diff;
}
person bames53    schedule 16.01.2012

arrow_upward
4
arrow_downward

Три придирки:

  • sizeof(abs_diff)*8 - 1 можно заменить литералом 63 без потери переносимости (на самом деле он будет более переносим из-за платформ, где char не имеет ширины 8 бит).
  • & 1 не нужен, так как результат сдвига всегда один бит
  • Вы можете получить diff из abs_diff, не повторяя вычитание.

В противном случае, это кажется мне совершенно правильным.

person Fred Foo    schedule 16.01.2012
comment
sizeof(abs_diff)*CHAR_BIT - 1 будет более портативным - person phuclv; 06.08.2015

arrow_upward
4
arrow_downward

Это короче и, вероятно, быстрее.

int64_t GetDifference(uint64_t first, uint64_t second)
{
  int64_t diff = first - second;
  bool overflowed = (diff < 0) ^ (first < second);
  assert(!overflowed);
  return diff;
}

Хороший оптимизирующий компилятор должен заметить, что diff < 0 — отрицательный флаг, а first < second — флаг переноса из предыдущего выражения. Сравнение этих двух флагов — классический тест на переполнение.

Даже если он этого не обнаруживает, требуется меньше операций.

Но главная причина, по которой я предпочитаю это, заключается в том, что магических чисел не существует.

person Ben Voigt    schedule 16.01.2012
comment
Спасибо .. Я понимаю вашу точку зрения ... если бы вместо int64_t / uint64_t было int / uint, это было бы то, что сработало бы ... - person Abhi; 17.01.2012
comment
Волшебных чисел нет, но вы полагаетесь на неопределенное поведение, то есть на тот факт, что приведение без знака, которое переполняет целочисленное представление, обертывает - person Triskeldeian; 29.11.2015
comment
@Triskeldeian: это определенная реализация, а не неопределенная. - person Ben Voigt; 29.11.2015

arrow_upward
2
arrow_downward

Как насчет этого:

int64_t GetDifference(uint64_t first, uint64_t second) {
    int64_t diff = (int64_t)(first - second);
    assert first >= second && diff >= 0 || first < second && diff < 0;
    return diff;
}
person MRAB    schedule 16.01.2012