将 64 位整数相除，就像被除数左移 64 位一样，没有 128 位类型

Question

对于令人困惑的标题深表歉意。我不确定如何更好地描述我想要完成的事情。我基本上是想做相反的事情在 C 中用于

的平台

int64_t divHi64(int64_t dividend, int64_t divisor) {
    return ((__int128)dividend << 64) / (__int128)divisor;
}

由于缺少对 __int128 的支持而无法实现。

Answer 1

这可以在没有 multi-word 除法的情况下完成

假设我们想要做 ⌊2⁶⁴ × ^x⁄_y⌋ 然后我们可以这样变换表达式

根据这个问题

，第一个术语很简单地完成 ((-y)/y + 1)*x

第二项相当于 (2⁶⁴ % y)/y*x 并且有点棘手。我尝试了各种方法，但如果只使用整数运算，都需要 128 位乘法和 128/64 位除法。这可以使用算法来计算以下问题中的 MulDiv64(a, b, c) = a*b/c

Most accurate way to do a combined multiply-and-divide operation in 64-bit?
How to multiply a 64 bit integer by a fraction in C++ while minimizing error?
How can I multiply and divide 64-bit ints accurately?

但是它们可能很慢，如果你有这些函数，你可以像 MulDiv64(x, UINT64_MAX, y) + x/y + something 一样更容易地计算整个表达式，而不会搞乱上面的转换

如果精度为 64 位或更高，使用 long double 似乎是最简单的方法。所以现在可以通过 (2⁶⁴ % y)/(long double)y*x

uint64_t divHi64(uint64_t x, uint64_t y) {
    uint64_t mod_y = UINT64_MAX % y + 1;
    uint64_t result = ((-y)/y + 1)*x;
    if (mod_y != y)
        result += (uint64_t)((mod_y/(long double)y)*x);
    return result;
}

为简化起见，省略了溢出检查。如果您需要签名除法，则需要稍作修改

如果您的目标是 64 位 Windows 但您使用的 MSVC 没有 __int128 那么 now it has a 128-bit/64-bit divide intrinsic which simplifies the job significantly without a 128-bit integer type. You still need to handle overflow though because the div instruction将在这种情况下抛出异常

uint64_t divHi64(uint64_t x, uint64_t y) {
    uint64_t high, remainder;
    uint64_t low = _umul128(UINT64_MAX, y, &high);
    if (x <= high /* && 0 <= low */)
        return _udiv128(x, 0, y, &remainder);
    // overflow case
    errno = EOVERFLOW;
    return 0;
}

上面的溢出检查可以简化为检查是否x < y，因为如果x >= y 那么结果会溢出

另见

Efficient Multiply/Divide of two 128-bit Integers on x86 (no 64-bit)
Efficient computation of 2**64 / divisor via fast floating-point reciprocal

对 16/16 位除法的详尽测试表明我的解决方案适用于所有情况。但是，即使 float 的精度超过 16 位，您也确实需要 double，否则偶尔会返回 less-than-one 结果。它可以通过在截断之前添加一个 epsilon 值来修复：(uint64_t)((mod_y/(long double)y)*x + epsilon)。这意味着您将需要 __float128（或 -m128bit-long-double option) in gcc for precise 64/64-bit output if you don't correct the result with epsilon. However that type is available on 32-bit targets，这与仅在 64 位目标上受支持的 __int128 不同，因此生活会更轻松一些。当然您可以使用function as-is 如果只需要一个非常接近的结果

下面是我用来验证的代码

#include <thread>
#include <iostream>
#include <limits>
#include <climits>
#include <mutex>

std::mutex print_mutex;

#define MAX_THREAD 8
#define NUM_BITS   27
#define CHUNK_SIZE (1ULL << NUM_BITS)

// typedef uint32_t T;
// typedef uint64_t T2;
// typedef double D;
typedef uint64_t T;
typedef unsigned __int128 T2;   // the type twice as wide as T
typedef long double D;
// typedef __float128 D;
const D epsilon = 1e-14;
T divHi(T x, T y) {
    T mod_y = std::numeric_limits<T>::max() % y + 1;
    T result = ((-y)/y + 1)*x;
    if (mod_y != y)
        result += (T)((mod_y/(D)y)*x + epsilon);
    return result;
}

void testdiv(T midpoint)
{
    T begin = midpoint - CHUNK_SIZE/2;
    T end   = midpoint + CHUNK_SIZE/2;
    for (T i = begin; i != end; i++)
    {
        T x = i & ((1 << NUM_BITS/2) - 1);
        T y = CHUNK_SIZE/2 - (i >> NUM_BITS/2);
        // if (y == 0)
            // continue;
        auto q1 = divHi(x, y);
        T2 q2 = ((T2)x << sizeof(T)*CHAR_BIT)/y;
        if (q2 != (T)q2)
        {
            // std::lock_guard<std::mutex> guard(print_mutex);
            // std::cout << "Overflowed: " << x << '&' << y << '\n';
            continue;
        }
        else if (q1 != q2)
        {
            std::lock_guard<std::mutex> guard(print_mutex);
            std::cout << x << '/' << y << ": " << q1 << " != " << (T)q2 << '\n';
        }
    }
    std::lock_guard<std::mutex> guard(print_mutex);
        std::cout << "Done testing [" << begin << ", " << end << "]\n";
}


uint16_t divHi16(uint32_t x, uint32_t y) {
    uint32_t mod_y = std::numeric_limits<uint16_t>::max() % y + 1;
    int result = ((((1U << 16) - y)/y) + 1)*x;
    if (mod_y != y)
        result += (mod_y/(double)y)*x;
    return result;
}

void testdiv16(uint32_t begin, uint32_t end)
{
    for (uint32_t i = begin; i != end; i++)
    {
        uint32_t y = i & 0xFFFF;
        if (y == 0)
            continue;
        uint32_t x = i & 0xFFFF0000;
        uint32_t q2 = x/y;
        if (q2 > 0xFFFF) // overflowed
            continue;
        
        uint16_t q1 = divHi16(x >> 16, y);
        if (q1 != q2)
        {
            std::lock_guard<std::mutex> guard(print_mutex);
            std::cout << x << '/' << y << ": " << q1 << " != " << q2 << '\n';
        }
    }
}

int main()
{
    std::thread t[MAX_THREAD];
    for (int i = 0; i < MAX_THREAD; i++)
        t[i] = std::thread(testdiv, std::numeric_limits<T>::max()/MAX_THREAD*i);
    for (int i = 0; i < MAX_THREAD; i++)
        t[i].join();
    
    std::thread t2[MAX_THREAD];
    constexpr uint32_t length = std::numeric_limits<uint32_t>::max()/MAX_THREAD;
    uint32_t begin, end = length;
    
    for (int i = 0; i < MAX_THREAD - 1; i++)
    {
        begin = end;
        end  += length;
        t2[i] = std::thread(testdiv16, begin, end);
    }
    t2[MAX_THREAD - 1] = std::thread(testdiv, end, UINT32_MAX);
    for (int i = 0; i < MAX_THREAD; i++)
        t2[i].join();
    std::cout << "Done\n";
}

将 64 位整数相除，就像被除数左移 64 位一样，没有 128 位类型

Divide 64-bit integers as though the dividend is shifted left 64 bits, without having 128-bit types

c

integer-division

128-bit

int128