2

X = 712360810625491574981234007851998リンクされたリストを使用して表され、各ノードはunsigned int

712360-810625491-574981234-007851998 のリンクリスト

以外にすばやく行う方法はありますか?X << 8 X << 591X * 2^8 X * 2^591

4

2 に答える 2

2

ビットシフトは、任意のビット数で非常に簡単です。オーバーフローしたビットを次の要素にシフトすることを忘れないでください。それで全部です

以下は、3 例による左シフトです。

uint64_t i1, i2, i3, o1, o2, o3; // {o3, o2, o1} = {i3, i2, i1} << 3;

o3 = i3 << 3 | i2 >> (32 - 3);
o2 = i2 << 3 | i1 >> (32 - 3);
o1 = i1 << 3;

右にシフトする場合と同様に、逆方向に繰り返します。

編集：

大きな数に基数 10 9を使用しているように見えるため、バイナリシフトはここでは適用されません。基数 B で N 桁を左/右に「シフト」することは、数値にそれぞれ B Nと B -Nを掛けることと同じです。10進数でバイナリシフトを行うことはできません。

基数を変更しない場合、解決策は 1 つしかありません。それは、数値に 2 591を掛けることです。バイナリのようにシフトしたい場合は、基数 2 32または基数 2 64のような2 の累乗である基数に変更する必要があります。

一般的な解決策は次のようになります。四肢はリトル エンディアンで格納され、各桁は基数 2 CHAR_BIT*sizeof(T) です。

template<typename T>
void rshift(std::vector<T>& x, std::size_t shf_amount) // x >>= shf_amount
{
    constexpr std::size_t width = CHAR_BIT*sizeof(T);
    if (shf_amount > width)
        throw;

    const std::size_t shift     = shf_amount % width;
    const std::size_t limbshift = shf_amount / width;
    
    std::size_t i = 0;
    for (; i < x.size() - limbshift - 1; ++i)
        x[i] = (x[i + limbshift] >> shift) | (x[i + 1 + limbshift] << (width - shift));
    x[i++] = x[i + limbshift] >> shift;
    for (; i < x.size() ; ++i)
        x[i] = 0;
}

さらに、タグから、要素がメモリ空間全体に散らばっているため、キャッシュに適していないリムを格納するためにリンクされたリストを使用している可能性が高く、次のポインタのために多くのメモリを浪費します。実際、ほとんどの現実の問題でリンクリストを使用するべきではありません

于 2013-08-03T12:40:22.463 に答える