0

問題 : 非負の整数が2^j - 2^k where j>=k>=02 のべき乗の差などの形式であるかどうかを確認するn (say)にはfor eg. 00011110。連続する 1 のシーケンス (右端) をオフにし、 でゼロ チェックを行いnます。ここで私がすることは、steps for solution 00011110 00011111(turn on trailing 0's) 00000000(then turn off trailing 1's). この式を使用し(x | (x - 1)) & ((x | (x - 1)) + 1)ます。しかし、リテラルを使用しないより効率的な式 (おそらく操作の数が少ないため) の((x & -x) + x) & x後にゼロチェックが続きます。そして、私はこれを理解できませんが、同じことを行うと書かれていますが、私の結果から式を導き出すことはできません. 誰かが私にこれを説明できますか？

EDIT : 32 ビット ワード、2 の補数

4

2 に答える 2

2

が である-xとすると~x + 1、数値が 2^j - 2^k の形式の場合:

  • -x=2^kプラスすべての 1 >= 2^j。キャリーは 2^k に到達するまで波及し、その後停止します。
  • したがってx & -x= 2^k;
  • したがって(x & -x) + x= 2^k; と
  • したがって((x & -x) + x) & x= 0 です。

そして、そのロジックに沿って逆方向に作業できます。

  • ((x & -x) + x) & x = 0 => ((x & -x) + x) と x の間に共通ビットなし;
  • x と ((x & -x) + x) の間に共通のビットがないということは、x の連続する 1 のグループについて、(x & -x) にはこれらのビットの最小値が設定されていて、他のビットは設定されていないことを意味します。
  • ...そして、波紋を運ぶ方法を考えると、それを達成する唯一の方法は、連続した 1 のグループが 1 つしかない場合です。
于 2020-06-14T04:44:04.503 に答える