5

私はこの質問に取り組んでおり、解決策を考え出しています（1つまたは2つの条件を追加する必要があるかもしれません）が、これが正しい方法であるかどうかはわかりません.2つのループを使用するのは面倒で、これが効率的な方法です。誰かがそれを行うための素晴らしいトリックを持っているか、より良いアプローチがあればそれは素晴らしいことです:)。（言語は障壁ではありません）

私のアルゴリズム:

  • まず、数値の最初の「0」の lsb ビットを見つけます
  • 次に、この「0」ビットの隣にある次のセットビットを見つけます
  • 「0」ビットを1に、「1」ビットを「0」に変更します
  • あなたが得る数は次に小さいです
  • すべてのビットが設定されている場合、同じ数の「1」ビットで次に小さい数はありません。
void nextSmaller(int number) {
    int firstZeroBitHelper = 1, nextOneBitHelper;
    while (firstZeroBitHelper < number) {
        // when we find first lsb zero bit we'll stop
        bool bit = number & firstZeroBitHelper;
        if (bit == false)
            break;
        firstZeroBitHelper = firstZeroBitHelper << 1;
    }

    if (firstZeroBitHelper >= number) {
        cout << "No minimum number exists" << endl;
        return;
    }

    nextOneBitHelper = firstZeroBitHelper;
    nextOneBitHelper = nextOneBitHelper << 1;

    while (nextOneBitHelper < number) {
        // when we get '1' after the previous zero we stop
        bool bit = number & nextOneBitHelper;
        if (bit == true)
            break;
        nextOneBitHelper = nextOneBitHelper << 1;
    }

    // change the first zero to 1
    number = number | firstZeroBitHelper;
    // change the next set bit to zero
    number = number & ~nextOneBitHelper;

    cout << number << endl;
}
4

5 に答える 5

5

コメントの続きです..

ええと、私はそれを見つけました。The Art of Computer Programming の章 7.1.3 (ボリューム 4A) の質問 21 への回答: 「Gosper のハックの逆」を参照してください。

次のようになります。

t = y + 1;
u = t ^ y;
v = t & y;
x = v - (v & -v) / (u + 1);

y入力と結果はどこにありますかx。Gosper のハックと同じ最適化がその分割に適用されます。

于 2013-09-21T08:18:59.920 に答える
4

上に行く：

  • 数字の右端にある「01」を見つけて「10」にします。
  • 後続のすべての 1 ビットをできるだけ右に揃えます。

下に行く：

  • 数字の右端にある「10」を見つけて「01」にします。
  • 後続のすべての1 ビットを左揃えにします (つまり、設定したビットの後に既に 1 が続いている場合は何もしません)。

下向きのケースを明確にする例：

  • 225 = 0b11 10 0001
  • スワップ: 0b11 01 000 1
  • 左詰め: 0b1101 1 000 = 216

最初に上に行く場合について説明します。1 ビットを 1 桁左に移動できる最下位の位置 (つまり、右側に 1 がある右端の 0) を見つけたいと考えています。設定したビットごとに別の場所でビットをクリアする必要があり、設定したビットの右側のどこかでビットをクリアする必要があるため、これが設定可能な最も右のビットであることは明らかです。数値は大きくなるどころか小さくなります。

このビットを設定したので、1 つのビットをクリアし (設定されたビットの総数を復元するため)、残りのビットを再シャッフルして、数値ができるだけ小さくなるようにします (これにより、次の最大数になります)。設定ビット数と同じ)。設定したビットの右側のビットをクリアし、元の数を下回ることを恐れずに残りの 1 ビットを可能な限り右にプッシュできます。設定した単一ビットよりも小さい。

次に大きい数値ではなく、次に小さい数値を見つけることは基本的に同じですが、設定されたビットを 1 つ右に移動できる最も右の位置を探していることと、それを行った後、すべての下位ビットを次のように移動したいことを除きます。できるだけ左に。

他の人がこれのビットいじりバージョンをうまく手に入れているようですが、アルゴリズムの論理的/数学的側面について適切な説明ができるかどうかを確認したかったのです.

于 2013-09-21T09:03:24.080 に答える
3

anatolyg はアルゴリズムをかなりうまくカバーしましたが、より効率的な解決策があります。

Gosper のハックを使用すると、ビットを反転すると、Gosper の値が降順で生成されるという賢明な認識が得られます。

次の疑似コードのようなものが機能します。

let k := number
let n := num bits in k (log base 2)
k = k ^ ((1 << n) - 1)
k = gosper(k)
k = k ^ ((1 << n) - 1)
return k

これにより、優れた O(1) (xor を線形時間と見なす場合は O(log n)) アルゴリズムが得られます。:)

k=2^x-1if一部の のように、考慮しなければならないケースがいくつかありますがx、それは非常に簡単に把握できます。

于 2013-09-21T08:16:02.137 に答える
2

あなたが説明したアルゴリズムは完全に正しくありません。1つの詳細を除いて、すべてを正しく行います。任意の 2 進数は次の形式で、アルゴリズムの途中にあります。

xxxxx...10000...1111...
         ---n---// f //

ここに任意のビットがあり、連続する 0 と 1 の数はと(と)xxx...によって決まります。firstZeroBitHelpernextOneBitHelperfn

ここで、同じ数の設定ビットを残してこの数を減らす必要があります。これにより、必然的に最上位1が になり0ます。

xxxxx...0????...????...
         -----n+f------

ビットの値は新しい数値を元の数値よりも小さくすることに注意して???ください。実際には、結果の数値が最大値になるようにこれらのビットを選択する必要があります。

xxxxx...011111...0000...
         ---f+1--//n-1//

したがって、2 ビットだけでなく、f+2ビットを反転する必要があります (1 ビットを から1に0、f+1他のビットを から0に1)。

それを行う1つの方法は次のとおりです。

まず、関連するすべてのビットをオフにします。

number &= ~nextOneBitHelper;
number &= ~(nextOneBitHelper - 1);

次に、必要なビットを MSB からオンにします。

nextOneBitHelper >>= 1;
while (firstZeroBitHelper != 0)
{
    number |= nextOneBitHelper;
    nextOneBitHelper >>= 1;
    firstZeroBitHelper >>= 1;
}

上記のビット操作は、ループなしで実装できます。そのためには、 と を計算する必要がありnますf。それをした後：

unsigned mask = (1 << (f + 1)) - 1; // has f+1 bits set to 1
mask <<= n - 1; // now has these bits at correct positions
number |= mask; // now the number has these bits set
于 2013-09-21T08:06:17.133 に答える
1 
#include <iostream>

bool AlmostdivBy2(int num) {
    return (-~num & (num)) == 0;
}

void toggleright(int &num) {
    int t;
    for (t = -1; num & 1; t++)
        num >>= 1;
    ++num = (num << t) | ~-(1 << t);
}

void toggleleft(int &num) {
    while (~num & 1)
        num >>= 1; //Simply keep chopping off zeros
    //~num & 1 checks if the number is even
    //Even numbers have a zero at bit at the rightmost spot
}

int main() {

    int value;
    std::cin >> value;
    if (!AlmostdivBy2(value)) {
        (~value & 1) ? toggleleft(value) : toggleright(value);
    }
    std::cout << value << "\n";
    return 0;
}

私はこれを考えすぎたかもしれないと思いますが、ここに私の説明があります：

  • 数値が 2 の累乗に近い場合、つまり 1、3、7、15、31、... のような値の場合、2 進表現で同じ数の 1 を持つことができる、それより小さい値はありません。したがって、これらの数値について心配する必要はありません。

  • 数字が偶数の場合、これも簡単な修正方法です。数字が奇数になるまで、最後からゼロを切り落とし続けます。

  • 奇数は最も難しい問題であり、それが再帰的な理由です。最初に、数値の右側から始まる最初のゼロ ビットを見つける必要がありました。これが見つかったら、その数値に 1 を追加して、最後のビットを 1 にします。再帰が巻き戻されると、ビットを左にシフトして 1 を追加し続けます。これが完了すると、次に小さいサイズになります。

私はあなたを混乱させなかったことを願っています

編集

さらに取り組み、これが非再帰バージョンですtoggleright

void toggleright(int &num) {    
    int t = 1;
    while ( (num >>= 1) & 1 && t++ );
    num = (-~num << ~-t) | ~-(1 << t);    
}
于 2013-09-21T09:30:23.927 に答える