Вопрос по – Подпись 64 на 32 целочисленного деления

3

Предполагая, что у вас есть udive инструкции машины, которая делает специальный корпус 64 на 32 без знака деления, взяв (32bit дивиденд & лт; & лт; 32) / 32-битный делитель, мы можем сделать полный 64 по 32 дивизии, используя следующее:

// assume: a / b guaranteed not to overflow
a = 64bit dividend, a.h & a.l are hi & lo 32bits respectively
b = 32bit divisor

q1 = udive(a.h, b)  // (a.h << 32) / b
r1 = -(q1 * b)      // remainder of the above, shortcut since a.h & 0xffffffff == 0
q2 = a.l / b        // a.l / b using regular unsigned division
r2 = a.l - (q2 * b) // remainder of the above
q = q1 + q2
r = r1 + r2

// r < r2, r overflowed and is >32bits, implies r > b since b is 32bits
// r >= b, quotient too small by 1, adjust
if (r < r2) or (r >= b)
    q = q + 1
return q

Однако подписанное дело доставляет мне проблемы. Предполагая эквивалентную инструкцию sdive, которая выполняет подписанную версию udive, я не могу понять, как обращаться с остатками и еще много чего.

Инстинктивно это похоже на проблему с двумя дополнениями. Поскольку я не являюсь экспертом в этом, я не могу дать вам дальнейших советов, но, возможно, это подсказка. Robert Harvey♦

Ваш Ответ

3   ответа
0

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

КнигаHacker's Delight как правило, хорошо для такого рода низкоуровневой арифметики. В настоящий момент у меня нет под рукой копии, но ее код для выполнения 64 / 64-> 64 с 64 / 32-> 32 находится в сети:http://www.hackersdelight.org/HDcode/newCode/divDouble.c

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

0

Спасибо за ответы. Я посмотрел на Восторг Хакера. Если вы посмотрите на функцию divdi3 в HD, то есть вызов DIVS, инструкция 64 / 32-> 32, когда делитель 32-битный, и результат, как известно, не переполняется. Машина, на которой я работаю, не имеет инструкции общего назначения 64/32-32, она имеет особый случай, упомянутый выше. Вышеупомянутая функция для 64 / 32-> 32 является моей реализацией для DIVU в случае без знака, поэтому я пытаюсь разработать нечто подобное для DIVS.

Я мог бы просто забыть о пути DIVS, но это чрезвычайно распространенный случай, и я хочу поразить его как можно чаще, это просто сложная реализация.

Извините за неясный псевдокод, но все без знака и в основном 32-битные.

DIVU(uint64 a, uint32 b) {
// assume: a / b guaranteed not to overflow
// a = 64bit dividend, a.h & a.l are hi & lo 32bits respectively
// b = 32bit divisor

uint32 q1 = udive(a.h, b)      // (a.h << 32) / b
uint32 r1 = -(q1 * b)          // remainder of the above, shortcut for (a.h << 32) - (q1 * b) since (a.h << 32) & 0xffffffff == 0
uint32 q2 = a.l / b            // a.l / b using regular unsigned division
uint32 r2 = a.l - (q2 * b)     // remainder of the above
uint32 q = q1 + q2
uint32 r = r1 + r2

// r < r2, r overflowed and is >32bits, implies r > b since b is 32bits
// r >= b, quotient too small by 1, adjust
if (r < r2) or (r >= b)
        q = q + 1
return q
}
0

Вы можете игнорировать особый случай оптимизации divdi3 при вызове div; На что я хотел обратить внимание, так это в том, что когда divdi3 необходимо выполнить деление в полную силу, он делает это путем вызова udivdi3, а не с помощью деления со знаком, эквивалентного алгоритму udivdi3.

Глядя в Knuth vol 2, я вижу, что он также в основном говорит, что вы делаете знаковое деление в процессе взятия абсолютных значений, деления без знака и последующего исправления знакового бита. Это имеет интуитивный смысл для меня, потому что числа со знаком со знаком 2s не имеют удобного свойства, которое имеют == (ah * 2 ^ 32) + al, что и числа без знака, так что собрать 64-битные операции не так просто. работая на двух половинках отдельно.

До и после возни не должно быть столько дополнительных циклов над беззнаковым делением ...

PS: что это за странный процессор? :-)

Похожие вопросы