Как вычислить 2⁶⁴/n в C?

Question

Как вычислить целочисленное деление 2⁶⁴/ n? Предполагая, что:

• unsigned long 64-битный
• Мы используем 64-битный процессор
• 1 64

Если мы делаем 18446744073709551616ul / n, мы получаем warning: integer constant is too large for its type во время компиляции. Это потому, что мы не можем выразить 2⁶⁴ в 64-битном процессоре. Другой способ заключается в следующем:

#define IS_POWER_OF_TWO(x) ((x & (x - 1)) == 0)

unsigned long q = 18446744073709551615ul / n;
if (IS_POWER_OF_TWO(n))
    return q + 1;
else
    return q;

Есть ли более быстрая (цикл процессора) или более чистая (кодирование) реализация?

Answer 1

Идея использования phuclv -n это умно, но можно сделать гораздо проще. В качестве беззнаковых длин мы имеем -n = 2⁶⁴-n, тогда (-n) / n = 2⁶⁴/ n - 1, и мы можем просто добавить обратно 1.

unsigned long foo(unsigned long n) {
  return (-n)/n + 1;
}

Сгенерированный код - это то, что вы ожидаете (gcc 8.3 на x86-64 через godbolt):

    mov     rax, rdi
    xor     edx, edx
    neg     rax
    div     rdi
    add     rax, 1
    ret

Answer 2

Я придумал другое решение, которое было вдохновлено этим вопросом. Оттуда мы знаем, что

(a ₁ + a ₂ + a ₃ +... + a _n) / n =

(a ₁ / n + a ₂ / n + a ₃ / n +... + a _n / n) + (a ₁ % n + a ₂ % n + a ₃ % n +... + a _n % n) / п

Выбрав ₁ = a ₂ = a ₃ =... = a _n-1 = 1 и a _n = 2 ⁶⁴ - n, мы получим

(a ₁ + a ₂ + a ₃ +... + a _n) / n = (1 + 1 + 1 +... + (2 ⁶⁴ - n)) / n = 2 ⁶⁴ / n

= [(n - 1) * 1 / n + (2 ⁶⁴ - n) / n] + [(n - 1) * 0 + (2 ⁶⁴ - n)% n] / n

= (2 ⁶⁴ - n) / n + ((2 ⁶⁴ - n)% n) / n

2 ⁶⁴ - n является дополнением 2 к n, которое является -n или мы также можем написать это как ~0 - n + 1, Таким образом, окончательное решение будет

uint64_t twoPow64div(uint64_t n)
{
    return (-n)/n + (n + (-n) % n)/n + (n > 1ULL << 63);
}

Последняя часть должна исправить результат, потому что мы имеем дело с целыми числами без знака, а не со знаком, как в другом вопросе. Проверено на моем ПК на 32- и 64-битной версии, и результат соответствует вашему решению

На MSVC, однако, есть встроенное 128-битное деление, так что вы можете использовать вот так

uint64_t remainder;
return _udiv128(1, 0, n, &remainder);

что приводит к чистому выводу

    mov     edx, 1
    xor     eax, eax
    div     rcx
    ret     0

Вот демо

На большинстве x86-компиляторов long double также имеет 64 бит точности, поэтому вы можете использовать любой из этих

(uint64_t)(powl(2, 64)/n)
(uint64_t)(((long double)~0ULL + 1)/n)
(uint64_t)(18446744073709551616.0L/n)

хотя, вероятно, производительность будет хуже. Это также может быть применено к любым реализациям, где long double имеет более 63 битов значений, таких как PowerPC или Sparc

Есть связанный вопрос о расчете ((UINT_MAX + 1)/x)*x - 1: Целочисленная арифметика: добавьте 1 к UINT_MAX и разделите на n без переполнения, используя также умные решения. Исходя из этого мы имеем

2 ⁶⁴ / n = (2 ⁶⁴ - n + n) / n = (2 ⁶⁴ - n) / n + 1 = (-n) / n + 1

по сути, это просто еще один способ получить ответ Нейта Элдриджа

Вот немного демо для других компиляторов на Godbolt

Смотрите также:

• Трюк, чтобы разделить константу (степень два) на целое число
• Эффективное вычисление 2**64 / делитель с помощью быстрой обратной величины с плавающей точкой

Answer 3

Мы используем 64-битный процессор

Какой 64-битный процессор?

В общем случае, если вы умножите число с N битами на другое число с M битами, результат будет иметь до N+M битов. Для целочисленного деления это аналогично - если число с N битами делится на число с M битами, результат будет иметь N-M+1 бит.

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

Другими словами, некоторые 64-разрядные процессоры поддерживают деление 128-разрядного числа на 64-разрядное число, чтобы получить 64-разрядный результат. Например, на 80x86 это один DIV инструкция.

К сожалению, C не поддерживает "расширяющееся умножение" или "сужающее деление". Он поддерживает только "результат того же размера, что и исходные операнды".

По иронии судьбы (для беззнаковых 64-битных делителей на 64-битных 80x86) другого выбора нет, и компилятор должен использовать DIV инструкция, которая разделит 128-битное число на 64-битное число. Это означает, что язык C вынуждает вас использовать 64-битный числитель, затем код, сгенерированный компилятором, расширяет ваш 64-битный числитель до 128 бит и делит его на 64-битное число, чтобы получить 64-битный результат; а затем вы пишете дополнительный код, чтобы обойти тот факт, что язык не позволил вам использовать 128-битный числитель для начала.

Надеюсь, вы сможете увидеть, как эту ситуацию можно считать "менее чем идеальной".

То, что я хотел бы, - это способ заставить компилятор поддерживать "сужение деления". Например, возможно, злоупотребляя приведениями и надеясь, что оптимизатор достаточно умен, например:

  __uint128_t numerator = (__uint128_t)1 << 64;
  if(n > 1) {
      return (uint64_t)(numerator/n);
  }

Я проверил это для последних версий GCC, CLANG и ICC (используя https://godbolt.org/) и обнаружил, что (для 64-битных 80x86) ни один из компиляторов не достаточно умен, чтобы понять, что один DIV инструкция это все, что нужно (все они сгенерировали код, который делает call __udivti3, что является дорогой функцией для получения 128-битного результата). Компиляторы будут использовать только DIV когда (128-битный) числитель равен 64 битам (и ему будет предшествовать XOR RDX,RDX установить верхнюю половину 128-битного числителя в нули).

Другими словами, вполне вероятно, что единственный способ получить идеальный код (DIV инструкция сама по себе на 64-битной 80х86) должна прибегнуть к встроенной сборке.

Например, лучший код, который вы получите без встроенной сборки (из ответа Нейта Элдриджа), будет:

    mov     rax, rdi
    xor     edx, edx
    neg     rax
    div     rdi
    add     rax, 1
    ret

... и лучший код, который возможен:

    mov     edx, 1
    xor     rax, rax
    div     rdi
    ret

Answer 4

Твой путь довольно хорош. Может быть, лучше написать это так:

return 18446744073709551615ul / n + ((n&(n-1)) ? 0:1);

Мы надеемся, что компилятор заметит, что он может выполнить условное перемещение вместо ветки.

Скомпилируйте и разберите.