nの次の2に合致するm次の方の数を求めます
1609 ワード
nは2のm次方ではなく,次の2に適合するm次方の数が要求される.
このアルゴリズムは多くの場所にあるが、小さな愚かさを詳しく理解していないだけで、ここに整理しておくと、あなたに役に立つことを忘れないでください.
次は私が他の人に教えてもらったところです.彼らの説明はもっと分かりやすいかもしれません.
http://topic.csdn.net/u/20110926/09/8ac6fb0f-d59a-4506-8536-c6d1bbb4ea79.html
最上位1は後ろのすべてのビットに拡張され、さらに1つ追加されます.
2のm次べき乗と2のm次べき乗−1の関係がこのアルゴリズムの鍵である.例えば100と111は1つ違います.別の角度から見ると、私は100が111に1を加えて100を求めるものだと見ることができます.
101の次の2に適合するm乗の数は100,すなわち4であり,最上位1を後のすべてのビットに拡張することができる.
まずnを右論理に1ビット(以降のシフトはすべて論理シフト)シフトし、nと求めたり操作したりしてnに保存し、最上位と右側の1位が1であることを保証します.
次はこの動作を繰り返しますが、右のすべてのビットを効率的に1にするにはどうすればいいですか?
1回目のシフトを求めて、または、最高位と2回目の高位の2位を1にしました.では、最初のステップに基づいて2位を右にシフトし、最初に得られた最終結果と加算します.
最高4位は1だったのではないでしょうか.
今、私たちはすでに最高4位を獲得してすべて1で、3回目の右シフトは私たちが1回に4位を移動することができて、移動が終わったら、私たちは最高8位を獲得することができます.
4回目に私たちは一度に8位を移動して、それから求めて、最高16位はすべて1を得ることができます.
5回目、私たちはさらに16ビットを移動して、今最高位以下のすべてのビットはすべて1で、形は11...111の形式のようです
最後に,この値に1を加えるとnの次の2に適合するm次べき乗の数が求められる.
ここまで書くと、まったく面倒なことはないと気づき、まずこの数が2のm乗であるかどうかを判断しました.
n & (n-1) == 0
ゼロに等しい場合は条件を満たし、戻る
ゼロに等しくなければ、その数を左に1桁ずらして、最上位以降のすべてのビットをクリアすれば得られるのではないでしょうか.
このアルゴリズムは多くの場所にあるが、小さな愚かさを詳しく理解していないだけで、ここに整理しておくと、あなたに役に立つことを忘れないでください.
次は私が他の人に教えてもらったところです.彼らの説明はもっと分かりやすいかもしれません.
http://topic.csdn.net/u/20110926/09/8ac6fb0f-d59a-4506-8536-c6d1bbb4ea79.html
public static int test(int n){
n -= 1;
n |= n >>> 1;
System.out.println(n);
n |= n >>> 2;
System.out.println(n);
n |= n >>> 4;
System.out.println(n);
n |= n >>> 8;
System.out.println(n);
n |= n >>> 16;
System.out.println(n);
return n + 1;
}
nが1を減らすのは,n自体が2のm次べき乗であることを満たすためである.最上位1は後ろのすべてのビットに拡張され、さらに1つ追加されます.
2のm次べき乗と2のm次べき乗−1の関係がこのアルゴリズムの鍵である.例えば100と111は1つ違います.別の角度から見ると、私は100が111に1を加えて100を求めるものだと見ることができます.
101の次の2に適合するm乗の数は100,すなわち4であり,最上位1を後のすべてのビットに拡張することができる.
まずnを右論理に1ビット(以降のシフトはすべて論理シフト)シフトし、nと求めたり操作したりしてnに保存し、最上位と右側の1位が1であることを保証します.
次はこの動作を繰り返しますが、右のすべてのビットを効率的に1にするにはどうすればいいですか?
1回目のシフトを求めて、または、最高位と2回目の高位の2位を1にしました.では、最初のステップに基づいて2位を右にシフトし、最初に得られた最終結果と加算します.
最高4位は1だったのではないでしょうか.
今、私たちはすでに最高4位を獲得してすべて1で、3回目の右シフトは私たちが1回に4位を移動することができて、移動が終わったら、私たちは最高8位を獲得することができます.
4回目に私たちは一度に8位を移動して、それから求めて、最高16位はすべて1を得ることができます.
5回目、私たちはさらに16ビットを移動して、今最高位以下のすべてのビットはすべて1で、形は11...111の形式のようです
最後に,この値に1を加えるとnの次の2に適合するm次べき乗の数が求められる.
ここまで書くと、まったく面倒なことはないと気づき、まずこの数が2のm乗であるかどうかを判断しました.
n & (n-1) == 0
ゼロに等しい場合は条件を満たし、戻る
ゼロに等しくなければ、その数を左に1桁ずらして、最上位以降のすべてのビットをクリアすれば得られるのではないでしょうか.