対unsigned int型、私はいくつかの簡単なビット単位の演算と算術演算の速度は私の64ビットPC上int、unsigned、long longとunsigned long longの間で大きく異なることに気づきました。C++は今日署名し、長い長いスピード
特に、次のループは、の場合の約2倍の速さです（予想外でした）。ここで
int k = 15;
int N = 30;
int mask = (1 << k) - 1;
while (!(mask & 1 << N)) {
int lo = mask & ~(mask - 1);
int lz = (mask + lo) & ~mask;
mask |= lz;
mask &= ~(lz - 1);
mask |= (lz/lo/2) - 1;
}
（フルコードhere）
は（g++ -O、-O2と-O3用）（秒）のタイミングです：
1.834207723 (int)
3.054731598 (long long)
1.584846237 (unsigned)
2.201142018 (unsigned long long)
これらの時間は非常に一貫している（つまり、1％マージン）。 -Oフラグがない場合、それぞれの速度は約1秒遅くなりますが、相対速度は同じです。
明確な理由はありますか？ 32ビット型ではベクトル化があるかもしれませんが、 の差がlong longとunsigned long longのどこにあるのかわかりません。 いくつかのタイプのオペレーションは、他のタイプのオペレーションよりもかなり遅いでしょうか（たとえば、 ）、または64ビットタイプの方が一般的です（64ビットアーキテクチャでさえ）。
このループは、正確に15要素の{1,2,...,30}のすべてのサブセットにループします。これは、正確に15ビットが設定された1<<30未満のすべての整数に対して（順番に）ループすることによって行われます。 現在のケースでは、それは155117520の繰り返しです。 このスニペットのソースはもうわかりませんが、this投稿で詳しく説明しています。
編集
それはタイプが符号なしの場合に除算を高速化することができますアセンブリコードかららしいです。サインビットを考慮する必要がないので、意味があると思います。 64ビット動作がmovqとxxxqを使用しながら
また、32ビット演算はmovlおよび他xxxl命令、 を使用します。
編集2
Iがリンクポストを読んだ後、私は上の式を使用することを決めた：
T k = 15;
T N = 30;
T mask = (1 << k) - 1;
while (!(mask & 1 << N)) {
T t = mask | (mask - 1);
mask = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(mask) + 1));
}
これは上記の投稿コードの時間の約3分の1で実行され、そして4つのタイプすべてで同じ時間を使用します。
は、あなたが生成されたアセンブリを見たことがありますか？ –
さて、アセンブリは本当に優れたものではありませんが、試してみる価値があるかもしれません。 – Ragnar
バイナリをx64で再確認しますか？ – jmnben