本当にビット演算ができますか?Android SDKプログラマーがどう書いたか見てみましょう!

ビット演算はみんな習ったことがありますが、工程実践では応用が少ないはずです.しかし、この2、3日、HashMapの内部実装を見てみると、シフト、および、またはの使用が非常に多く、素晴らしいことがわかりました.HashMapの核心はもちろんhash方法で、HashMapの中でどのように新しい挿入Objectのindexを計算するかを見てみましょう:

int index = hash & (tab.length - 1);

皆さんが理解できるかどうか分かりませんが、ここにはコンテキストが必要です.HashMapの長さは2のべき乗です.一方,2のべき乗については,さらに−1をした後,バイナリビット上はすべて1であるが,このときhと操作を行い,hの後ビットを切り取った(lengthが2のn次方であると仮定する)に相当する.例えば、h=69、バイナリに変換すると:1000101;length=16であると、length−1=15はバイナリ:111に変換される.従って、h&(lenght−1)のバイナリ結果は101、すなわち5である.この方法は実際には最も一般的な余剰ハッシュ法であり,ここでは長さが2のべき乗であるという特徴を利用して,除算に基づく余剰法を迂回し,効率を大幅に向上させることが分かった.もう1つの例を挙げると、HashMapではCollectionsの静的方法が使用されています.

/**
 * Returns the smallest power of two >= its argument, with several caveats:
 * If the argument is negative but not Integer.MIN_VALUE, the method returns
 * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method
 * returns Integer.MIN_VALUE. If the argument is zero, the method returns
 * zero.
 * @hide
 */
public static int roundUpToPowerOfTwo(int i) {
    i--; // If input is a power of two, shift its high-order bit right.

    // "Smear" the high-order bit all the way to the right.
    i |= i >>>  1;
    i |= i >>>  2;
    i |= i >>>  4;
    i |= i >>>  8;
    i |= i >>> 16;

    return i + 1;
}

この方法は,現在の数字の最小2以上のべき乗を返すために用いられるが,原理は簡単で,1つのバイナリ数の先頭にある後,すべてのビットを1にし,この中間値に1を加えると,我々の所望の値が得られる.ここで彼が使っているのは、2位、4位、8位......徐々に各数位を1に変える方法です.intは最大2^32なので、i|=i>>16までしかできません.入力が2のべき乗である場合を考慮すると,まず一歩自減する操作が必要である.私が列挙したこれ以外にも、HashMapや他のファイルのソースコードには多くのビット演算の例があります.ここではレンガを投げて玉を引くだけです.もっと検討してほしいです.