1

N 番目のビットが設定されたビット マスクを作成するとします。私は整数として N を持っています。

どちらが良いですか？1 << Nまたはルックアップテーブル（ポインター算術加算）？

私の推測では、シングル ビット シフト操作はメモリ ルックアップよりも高速であり、キャッシュがホットになった場合にのみ LUT に戦いのチャンスがあるということです。しかし、これが事実である場合、なぜ LUT がビット操作の問題の最速の解決策であることが多いのでしょうか? 最近の CPU の巨大なキャッシュのせいでしょうか?

x86-64 での現時点でのこの操作について、私が最も関心を持っているという事実で質問を修飾させてください。

4

2 に答える 2

6

ビット シフトは常に、ルックアップ テーブルや計算よりもはるかに高速です。

于 2012-12-16T22:12:53.930 に答える
-3

本気ですか？この VB プログラムを実行したところ、結果は少し変わりましたが、通常、ルックアップはビット シフトよりも速く、ヌル時間よりもそれほど長くはありませんでした。これはおそらくキャッシングが原因であるため、一般化することは困難です。

ランダムなシフト値からも同様の結果が得られましたが、もちろん、乱数の生成に何よりも時間がかかりました。

Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim SW As New Stopwatch()
Dim TimeShift As Long
Dim TimeLookUp As Long
Dim Timenull As Long
Dim i As Integer
Dim j As Integer
Dim Bit As UInteger
Dim R As New Random()
Dim total As UInteger
Dim S = New System.Text.StringBuilder()

total = 0
SW.Start()
j = 0
For i = 1 To RepCount
  Bit = CUInt(1) << (j And 31)
  j += 1
  'Bit = 1 << (R.Next(31))
  total = total Or Bit
Next
SW.Stop()
TimeShift = SW.ElapsedMilliseconds

SW.Reset()
SW.Start()
For i = 1 To RepCount
  Bit = Bits(j And 31)
  j += 1
  'Bit = Bits(R.Next(31))
  total = total Or Bit
Next
SW.Stop()
TimeLookUp = SW.ElapsedMilliseconds

SW.Reset()
SW.Start()
For i = 1 To RepCount
  total = total Or (j And 31)
  j += 1
Next
SW.Stop()
Timenull = SW.ElapsedMilliseconds

If Stopwatch.IsHighResolution Then
  S.Append("High")
Else
  S.Append("Low")

End If
S.Append(" frequency clock")
S.AppendLine()
S.Append("Shift time= " & TimeShift & " ms")
S.AppendLine()
S.Append("Lookup time= " & TimeLookUp & " ms")
S.AppendLine()
S.Append("Null time=" & Timenull & " ms")
S.AppendLine()
S.Append("Total= " & total.ToString)

MsgBox(S.ToString)
End Sub
End Class
于 2014-06-30T11:58:36.427 に答える