は、与えられた数

Question

次のコードは、与えられた数に1ビットの位置を見つけることで私たちを助け

中の1の位置を見つけるために、このコードを理解するのに役立つ必要はn = 5の場合そのバイナリ表現は101で、1は0番目と2番目の位置にあるので、出力は2 0になります。

いくつかのより多くの例：

n << ~d < 0. 

私は右シフトと賛辞の概念を知っているが、どのようにこの特異的な発現を知りたい：私はこのコードの意味を理解することができません

n  Output 
8  3 
149  7 4 2 0 

nのビットがdに設定されている場合は負の数になります。

Answer 1

このコードは見た目より複雑ですし、単純な算術演算はビットが明確であるかもしれない場所でビット演算を使用するように設計されているように見えます。

Javaで整数は、数値のビット単位の補数を取って、それを否定し、いずれかを追加することと同じであり、符号付き2の補数表現で表現されるからです。

〜X = -x + 1

これはコード

n << ~d 

そのため、今では、奇妙な

n << (-d + 1). 

と同等であることを意味します。数学的に修正再表示あなたが負の量で左シフトしていることを意味するでしょう...それはあまり意味がありません。我々は左シフトについては、次の言うJava Language Specification on the subject、に行く必要が場所です：

左側のオペランドの昇格された型がintである場合は、右の唯一の5最下位ビットシフト距離として使用されます。右側のオペランドがマスク値0x1f（0b11111）のビット論理AND演算子&（15.22.1）の影響を受けているかのようです。したがって実際に使用されるシフト距離は常に0〜31の範囲です。

つまり、シフト演算は数値の下位5ビットを除くすべてを完全に無視します。我々は正量だけシフトしている、と具体的な金額は、数量~dの最下位5ビットに依存します - これは、私たちが実際に負の量だけシフトしていないことを意味します。 （この時点では、すべてのことに有用ではないかもしれません~dの算術解釈のように思えるので、私は、むしろ負の値よりも補数を使うように切り替えています。）

我々は数dは、すべてのビットを反転取る場合は、それからちょうど最低の5ビットに焦点を当てれば、それは31 - dを評価することと等価になります。そして、すべてのゼロのビットを1に反転されます - 私たちは11111で始まり、数dを引く場合、すべての1ビットが0（1 = 0 1）に反転されますので、これを確認するために、通知31は、バイナリ表現11111を有していること（1-0 = 1）。dはこれが今私たちに手掛かりの多くを与え、0〜31

の間で常にあるので

n << (31 - d) 

へ - このコンテキストで - つまり、表現

n << ~d 

は完全に同等です何が起きてる。整数の符号付き32ビット表現では、整数の最初のビットが符号ビットであることに注意してください。 1の場合は負の値、0の場合は負ではない値です。だから私がnをとり、それを31-dの位置にシフトすると、最初のビット位置に番号のd番目のビットをプッシュしています（理由がわからない場合はこれでちょっと動きます）。 d番目のビットが1の場合、これは符号ビットを設定して番号を負にし、d番目のビットが0である場合、符号ビットをゼロに設定し、番号を非負にします。これは、なぜビットがセットされているかどうか

(n << ~d) < 0 

テスト - 元の位置にある1ビットは、得られる数の符号ビットをトリガーするかどうかをチェックしています。

これまで述べてきたように、私はこれが必要以上に複雑であるように感じます。それは何の左場合は他のすべてをオフにマスキングして見て直接ビットをテストするために、おそらく明確です：

if ((n & (1 << d)) != 0) 

読み（たぶん）少し簡単です。