いくつかの独自の研究とそのためのツールを開発する必要性の結果として、私はいくつかの新しい方法を思いつきました. Atm 私は、すでに尋ねられた質問に応じてサイトに投稿するための疑似コードに取り組んでいます。
ただし、その前に可能な限り最適化したいので、時間の複雑さの観点からビット操作がどのように機能するかを明確にする必要があります。
たとえば、2 つの 8 ビット整数のどちらが大きいかを評価したいとします。例として 8 ビットを使用していますが、実際にはもっと大きくなる可能性があります。
10000100
10100000
現状では、関係演算子は 6 つの MSB を比較して評価できます。概念的には、不等式に影響を与えることなく、両方から 10000000 を引くことができました。
00100000
00000100
- Q1. 読み取りがMSBから始まる場合、これは関係演算子の評価を高速化しますが、とにかく評価する必要がありますか、それとも先頭の0を評価する必要がありますか? 10000000 を減算すること自体が 8 ビット操作であるため、明らかな減算は行う価値がありませんが、代わりに、1 ビットまたは 2 ビット演算を使用して MSB または特定のビットを設定できれば、価値があると言えます。
- Q2. 法案に適合する可能性があると私が考えることができる2つの方法は、左にビットシフトしてから右にビットシフトして、先頭の1を破棄するか、マスクを使用することですが、他の方法はありますか? 先頭のビットだけでなく、任意のビットを設定できるものに特に興味があります。特定の言語に固有の場合は、お知らせください。
- Q3. マスクは N ビットであるため、N ビット操作自体ではなくマスクを使用していますか?
- Q4. 特定のビットの評価、存在するメソッド、操作の時間の複雑さについてはどうですか? Nビット操作になるように、先行するすべてのビットを最初に読み込む必要がありますか、それとも特定のビットに「ジャンプ」できますか?
- Q5 時間計算量の観点から、2 つの文字列が共役しています。これは、2 つのメモリ アドレスを関連付けることによって発生しますか? それとも、一方の文字列が読み取られて、もう一方の文字列にコピーされ、String.length 操作になりますか?
ありがとう。
さらなる解明。私はいくつかの場所から引き出したメモを読み直しており、Dukeling は私がそうあるべきだと思っていたことを確認しましたが、トリプルチェックする必要があります. たとえば、単純な乗算アルゴリズムを考えてみましょう。多くの場所で、これは Log^2(N) 操作であり、Log^2(N) 操作である理由は、Log(N) の Log(N) 加算で構成されているためであるという主張を目にします。番号。これに関して私が抱えている問題は、それは事実ですが、これらの Log(N) 数値のそれぞれがビット シフトの結果であり、最終的には少なくとも Log(N) 回ビットシフトされるという事実を無視していることです。1 によるビットシフトは Log(N) 操作であるため、ビットシフトのみを考慮すると、Log^2(N) 操作が得られます。したがって、実際には乗算はそうではないとさらに主張されているのを見ると、私には意味がありません。実際には、さまざまな方法で必要な追加の数を減らすことができるため、Log^2(N) 操作を使用します。ビットシフトだけで Log^2(N) が得られるため、その主張がどのように真実であるかについて、私は混乱しています。