Разделение числа, представленного двумя словами, числом, представленным одним?

Question

У меня есть два числа, X и Y.

Y - одно целое число без знака, например. long unsigned int. (В этом случае перед выполнением операции нет более простого примитива для повышения.)

X представлен двумя примитивами: X0 является тем же самым типом, что и Y, и представляет собой младшие бит X, а X1 - то же самое тип и представляет собой старшие разряды X.

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

Что такое эффективный способ определения результата этого разделения?

Answer 1

gcc имеет __int128 и unsigned __int128 для архитектуры x86. Я успешно использовал его в прошлом, чтобы выполнить описанные вами операции. Я уверен, что все основные компиляторы имеют эквиваленты.

Answer 2

«Разделить двузначное число на 1 цифру, давая 1-значный коэффициент и остаток» - это основной примитив, который необходимо синтезировать большие подразделения. Если у вас его нет (с цифрой == unsigned long int), доступной на вашем оборудовании, вам нужно использовать меньшие цифры.

В вашем случае разделите Y на 2 полуразмерных целых числа и X на 4 полуразмерных целых числа и выполните разделение таким образом.

Answer 3

Вы не указали платформу, которая имеет решающее значение для ответа.

X/Y всегда будет представим, используя тот же тип, что и Y, то есть операция можно предположить, чтобы не переполнить. (Поскольку Х представляет собой кстати произведение двух значений одного и того же типа, как Y, один из которых меньше или равна Y.)

На архитектуре x86-64, можно воспользоваться этим фактом , делением пары RDX:RAX, так что на самом деле это то же самое, что и у вас будет один «склеенный» 128-разрядный регистр для дивиденда. Остерегайтесь, однако, что если выше инвариант не всегда выполняется, то вы получите исключение разделения от CPU.

Тем не менее, одна реализация использовать ассемблерные, например:

/* divides x1:x0 pair by y, assumes that quotient <= UINT64_MAX */ 
uint64_t udiv128_64_unsafe(uint64_t x0, uint64_t x1, uint64_t y) 
{ 
    __asm__ (
     "divq\t%3" 
     : "=a" (x0) 
     : "0" (x0), "d" (x1), "rm" (y) 
    ); 
    return x0; 
} 

который GCC 6.3.0 переводит красиво (в -O1):

udiv128_64_unsafe: 
     mov  rcx, rdx   ; place the y (divisor) in RCX 
     mov  rax, rdi   ; low part of the dividend (x0) 
     mov  rdx, rsi   ; high part of the divided (x1) 
     divq rcx     ; RAX = RDX:RAX/RCX 
     ret       ; RAX is return value 

Например, для X = 65454567423355465643444545, Y = 86439334393432232 :

#include <stdio.h> 
#include <inttypes.h> 

uint64_t udiv128_64_unsafe(uint64_t x0, uint64_t x1, uint64_t y) { ... } 

int main(void) 
{ 
    printf("%" PRIu64 "\n", udiv128_64_unsafe(0x35c0ecb3fea1c941ULL, 0x36248bULL, 
     86439334393432232ULL)); 
    return 0; 
} 

данный испытательный драйвер программных выходов:

757231275