Java >> Java チュートリアル >  >> Java

Javaでは、整数の逆バイナリ形式で1の位置を取得する方法は?

Java

ビットを順番にチェックしてください:

List<Integer> bits(int num) {
  List<Integer> setBits = new ArrayList<>();
  for (int i = 1; num != 0; ++i, num >>>= 1) {
    if ((num & 1) != 0) setBits.add(i);
  }
  return setBits;
}

オンラインデモ

6 [2, 3]
7 [1, 2, 3]
8 [4]

整数を文字列に変換せずに、ビットをテストするだけです:

List<Integer> onePositions(int input) {
  List<Integer> onePositions = new ArrayList<>();
  for (int bit = 0; bit < 32; bit++) {
    if (input & (1 << bit) != 0) {
      onePositions.add(bit + 1); // One-based, for better or worse.
    }
  }
  return onePositions;
}

通常、ビットは右から左にカウントされ、右端のビットがビット 0 です。操作 1 << bit int を返します そのビット番号は bit です 1 に設定されます (残りは 0 に設定されます)。次に & を使用します (バイナリおよび) このビットが input で設定されているかどうかを確認します 、そうであれば、出力配列に位置を記録します。


純粋なビット単位のソリューションを提案してもよろしいですか?

static List<Integer> onesPositions(int input)
{
    List<Integer> result = new ArrayList<Integer>(Integer.bitCount(input));

    while (input != 0)
    {
        int one = Integer.lowestOneBit(input);
        input = input - one;
        result.add(Integer.numberOfTrailingZeros(one));
    }

    return result;
}

このソリューションはアルゴリズム的に最適です:

<オール>
  • Integer.bitCount を使用した単一のメモリ割り当て ArrayList を適切なサイズにする
  • ループ反復の最小回数、セット ビットごとに 1 回 1 .

    • 内側のループはかなり単純です:

    • Integer.lowestOneBit int を返します 入力セットの最下位ビットのみ。
    • input - one 次の反復のために、このビットを入力から「設定解除」します。
    • Integer.numberOfTrailingZeros 末尾の 0 の数を 2 進数で数え、事実上、最下位 1 ビットのインデックスを提供します。

    1 一度コンパイルすると、これが最適な方法ではない可能性があることに注意してください。代わりに、明示的な 0..n bitCount に基づくループ JIT の展開が容易になります。


    Java タグ