1

整数の次の下位 2 進数 (1 の数と同じ) を見つける方法は? 例: 入力番号 n = 10 (1010) が指定された場合、関数は 9 (1001) を返すか、n = 14 (1110) の場合は 13 (1101) を返すか、n = 22 (10110) の場合は 21 (10101) を返します。 、n = 25 (11001) の場合は 22 (10110) を返します... など。

4

3 に答える 3

4

あなたはこれを行うことができます。

static int nextLower(int n) {
   int bc = Integer.bitCount(n);
   for (int i = n - 1; i > 0; i--)
     if (Integer.bitCount(i) == bc)
        return i;
   throw new RuntimeException(n+" is the lowest with a bit count of "+bc);
}

もちろん、これが宿題である場合、これを書いた人を説得するのに苦労するでしょう ;)

于 2013-10-19T00:05:49.427 に答える
2

明確にするために、この回答では、「カーディナリティ」という用語を使用して、数値のバイナリ表現での 1 の数を示します。

1 つの (明らかな) 方法は、下向きのループを実行し、入力と同じカーディナリティを持つ最初の数値を探すことです (Peter Lawrey が提案したように)。

出力数は常に入力数にかなり近いと思うので、これが非効率的だとは思いません。より正確には、一番右の '10' ビット シーケンスを見つけて '01' に変更するだけです。次に、事後条件を壊さずに、左側がすべて 1 の数字で右側の部分をできるだけ多く置き換えます。これは、数値をバイナリ文字列に変換し（user2573153が示したように）、置換を実行し（おそらく正規表現で）、次にintに変換するという別のソリューションにつながります。

ピーターのアルゴリズムのわずかに高速なバージョンは次のようになります。これは、文字列に対して提案した操作を整数で実行します。

static int nextLower(int n) {
    int fixPart = 0;
    int shiftCount = 0;

    while ((n & 3) != 2) {
        if (n == 0) {
            throw new IllegalArgumentException(
                    fixPart + " is the lowest number with its cardinality");
        }

        fixPart |= (n & 1) << shiftCount;
        shiftCount += 1;
        n /= 2;
    }

    int fixZeros = shiftCount - Integer.bitCount(fixPart);
    return ((n ^ 3) << shiftCount) | (((1 << shiftCount) - 1) & ~((1 << fixZeros) - 1));
}

これは O(n) ではなく O(log n) ですが、その複雑さのために理解するのが間違いなく難しく、実際には遅くなる可能性もあります。とにかく、巨大で難しい数で試してみないと、違いに気付くことができませんでした.

編集

ちょっとしたベンチマークを試してみたところ、このコードは2 から 100,000,000 までのすべての数値に連続して適用した場合、Peter Lawrey のコードよりも 67% 高速であることがわかりました。これは、コードの複雑さの増加を正当化するのに十分ではないと思います。

于 2013-10-19T00:40:45.953 に答える