32 비트 부호없는 정수를 사용하여 64 비트 수를 곱하는 알고리즘

부호없는 32 비트 정수 2 개로 저장된 64 비트 숫자 (63 비트 + 부호 비트)를 2의 보수 숫자로 나타냅니다. 난 그냥 32 비트 숫자를 사용하여 곱셈 알고리즘을 구현하고, 결과가 63 비트에 맞는지 확인할 수있는 방법32 비트 부호없는 정수를 사용하여 64 비트 수를 곱하는 알고리즘

struct Long 
{ 
    uint32 high; 
    uint32 low; 
}

, 난 결과가 맞지 않는 경우 오버 플로우를 나타내는 오류 코드를 반환하고자합니다.

출처

2011-09-27 José

대부분의 컴파일러는 64 비트 길이의 긴 long 타입을 가지며 곱셈과 함께 사용해야합니다. – Pubby

64 비트 지원이 없다고 가정하고 알고리즘이 필요합니다. –

Wikipedia는 컴퓨터에서 사용하는 알고리즘을 설명합니다. http://en.wikipedia.org/wiki/Multiplication_algorithm –

일반적으로 두 개의 n 비트 숫자의 결과를 저장하려면 2 * n 비트가 필요합니다 (최대 결과는 (2^n)^2 = 2^(2 * n) 임). 따라서 가장 좋은 아이디어는 숫자를 4 개의 16 비트 파트로 나누고, 하나씩 곱해서 더합니다. 16 개의 곱셈이 모두 있지만 오류 검사는 간단합니다.

출처

2011-09-27 13:35:31 thiton

오류 검사는 사소한 일일 수 있지만 운반을 유지하는 것이 좀 더 복잡 할 것으로 생각됩니다. –

할 수 있어야합니다. 곱셈의 낮은 부분은 오버플로를 검사하여 높은 부분으로 전달해야하지만 어쨌든이를 피할 수는 없습니다. – thiton

변수를 양수로 변경하고 부호없는 곱셈을 수행 한 다음 완료되면 서명으로 변경하십시오. – Pubby

GNU MP library의 'longlong.h'헤더 파일을 살펴보십시오. 나는이 헤더의 버전이 GNU C 소스에도 있다고 생각한다. 매크로 : smul_ppmm은 부호없는 더블 워드 제품으로 정의됩니다. umul_ppmm. 이렇게하면 32x32 => 64 비트 곱셈을 얻을 수 있습니다.이 곱셈을 사용하면 64x64 => 128 비트 곱셈을 구현할 수 있습니다.

출처

2011-09-28 12:39:25

32 비트 부호없는 정수를 사용하여 64 비트 수를 곱하는 알고리즘

답변

관련 문제