将64位整数除，好像被除数为64位，而没有128位类型

Question

为这个令人困惑的标题道歉。我不确定如何更好地描述我想要完成的事情。我基本上试图在C中为getting the high half of a 64-bit multiplication做反向

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

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

Answer 1

这可以在没有多字分割的情况下完成

假设我们想做⌊264×x /y⌋然后我们可以像这样转换表达式

根据这个问题((-y)/y + 1)*x，第一个术语按照How to compute 2⁶⁴/n in C?进行

第二项相当于（264％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?
• (a * b) / c MulDiv and dealing with overflow from intermediate multiplication
• How can I multiply and divide 64-bit ints accurately?

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

如果它具有64位或更高的精度，那么使用long double似乎是最简单的方法。所以现在可以通过（264％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，但是您使用的是没有__int128的MSVC，那么now it has a 64-bit divide intrinsic可以在没有128位整数类型的情况下显着简化作业。你仍然需要处理溢出，因为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位除法的详尽测试表明我的解决方案适用于所有情况。但是你确实需要double，即使float具有超过16位的精度，否则偶尔会返回少于一个的结果。它可以通过在截断之前添加epsilon值来修复：(uint64_t)((mod_y/(long double)y)*x + epsilon)。这意味着如果你不用epsilon校正结果，你需要gcc中的__float128（或-m128bit-long-double option）来获得精确的64/64位输出。然而that type is available on 32-bit targets，不像__int128只支持64位目标，所以生活会更容易一些。当然，如果只需要非常接近的结果，您可以按原样使用该功能

下面是我用于验证的代码

#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";
}