2つの符号なし整数の積の上位32ビットを得る効率的な方法C++

Question

unsigned int a = 4294967295; // (2^32)-1 
unsigned int b = 2; 

2つの符号なし整数の積の上位32ビットを得る最も効率的な方法を理解しようとしています。 たとえば、CUDAプログラミングを使用して私はちょうどunsigned int first32bits = __umulhi(a,b)になり、上位32ビットを得ることができます。

C++でこのようなことを行う方法はありますか？ここで

は私のアプローチです：

unsigned long c = (((unsigned long)a * (unsigned long)b) >> 32) & 0x00000000FFFFFFFF; 

はより速く私のアプローチを作るために任意の方法はありますか？

Answer 1

__umulhi（）のような組み込み関数は、特定のアーキテクチャー（ここではNvidia GPU）に対して、より少ない/特別な命令を使用するように設計されています。コメントに示唆されているように（例えば、CPUの場合はIntel）、C++のものを期待するのではなく、独自のソリューションを検討する必要があります。

このような状況では、あなたのアプローチを意味のあるパフォーマンスの向上に置き換える組み込み関数を見つけることは非常に疑問です。

Answer 2

imulh32をネイティブ命令にマップするアーキテクチャー依存の回路がないかぎり、それはあなたができる最高のものだと思います。

g++ 6.3で生成されたアセンブリを見ると、shr $0x20のために掛け算を行うだけの機能以上のものは、1アセンブリ操作よりもコストがかかることは明らかです。

unsigned long umulhi32(unsigned int x, unsigned int y) 
{ 
    return (((unsigned long)a * (unsigned long)b) >> 32); 
} 
0000000000000960 <_Z8umulhi32jy>: 
960: 89 f8     mov %edi,%eax 
962: 89 f7     mov %esi,%edi 
964: 48 0f af c7    imul %rdi,%rax 
968: 48 c1 e8 20    shr $0x20,%rax 
96c: c3      retq 
96d: 0f 1f 00    nopl (%rax) 

例えば、それは私がPTXアセンブリはcudaが露出によって使用されるので、その可能性が高いと思い、いくつかの専用PTX命令にマップかどうかを確認するために、cuda umulhiの組み立てを持って興味深いものになるだろう、mul24（quoting）

mul24.hiは24×24ビットの乗算を実行し、 の高い32ビットの48ビットの結果

を返します

私が知る限り、x86アセンブリにはこのような命令はありません。

これが役に立ちます。