7

同じページに表示するために、sizeof（int）= 4およびsizeof（long）=8と仮定します。

整数の配列が与えられた場合、配列を論理的に左または右にビットシフトするための効率的な方法は何でしょうか？

私は、要素の最初のペア（インデックス0と1）のビットシフトを計算し、最初の要素（0）を設定するlongなどの補助変数を検討しています。このように続けると、要素（インデックス1と2）のビットシフトがコンピューターになり、次にインデックス1が設定されます。

これは実際にはかなり効率的な方法だと思いますが、欠点があります。32ビットを超えるビットシフトはできません。複数の補助変数を使用することは機能すると思いますが、私はどこかで再帰を想定しています。

4

3 に答える 3

9

long仲介者としてa を使用する必要はありません。左にシフトする場合は最上位の int から開始し、右にシフトする場合は最下位から開始します。変更する前に、隣接する要素からキャリーを追加します。

void ShiftLeftByOne(int * arr, int len)
{
    int i;
    for (i = 0;  i < len - 1;  ++i)
    {
        arr[i] = (arr[i] << 1) | ((arr[i+1] >> 31) & 1);
    }
    arr[len-1] = arr[len-1] << 1;
}

この手法を拡張して、1 ビットを超えるシフトを行うことができます。32 ビットを超える場合は、ビット カウント mod 32 を取り、それによってシフトしながら、結果を配列内でさらに移動します。たとえば、33 ビット左にシフトする場合、コードはほぼ同じになります。

void ShiftLeftBy33(int * arr, int len)
{
    int i;
    for (i = 0;  i < len - 2;  ++i)
    {
        arr[i] = (arr[i+1] << 1) | ((arr[i+2] >> 31) & 1);
    }
    arr[len-2] = arr[len-1] << 1;
    arr[len-1] = 0;
}
于 2010-05-05T14:36:48.200 に答える
1

Java の BigInteger 実装を見てみましょう。これはデータをバイト配列として内部的に保存します。具体的には、関数 leftShift() を確認できます。構文は C と同じなので、このような関数のペアを作成することはそれほど難しくありません。また、ビットシフトに関しては、C では unsinged 型を利用できることも考慮してください。これは、Java で符号をいじらずにデータを安全にシフトするには、通常、データを保持するためにより大きな型 (つまり、シフトする int) が必要であることを意味します。 short、int をシフトする long、...)

于 2010-05-05T14:35:00.830 に答える