2

私はしばらくこのパズルに取り組んできました。数値 (x) の 4 ビットを左回りに (折り返しを使用して) n だけ回転させる方法を見つけようとしています。ここで 0 <= n <= 31.. コードは次のようになります。

moveNib(int x, int n){
//... some code here
}

秘訣は、これらの演算子のみを使用できることです。

~ & ^ | + << >>

また、If ステートメント、ループ、関数呼び出しも使用できません。また、int型のみを使用できます。

例は moveNib(0x87654321,1) = 0x76543218 です。

私の試み:マスクを使用してビットとすべてを格納する方法を理解しましたが、任意の数値で移動する方法を理解できません。何か助けていただければ幸いです。

4

2 に答える 2

4

どうですか：

uint32_t moveNib(uint32_t x, int n) { return x<<(n<<2) | x>>((8-n)<<2); }

<<2ニブルからビットへの変換に使用し、ビットをそれだけシフトします。ラップアラウンドを処理するために、反対の方向に反対の量だけシフトされた数値のコピーによる論理和をとります。たとえば、x=0x87654321とn=1の場合、左部分は左に 4 ビット シフトされて になり0x76543210、右部分は右に 28 ビット シフトされて になり0x00000008、これらを OR すると、結果は0x76543218要求どおり になります。

編集：-本当に許可されていない場合、これを使用せずに同じ結果が得られます（2の補数の整数を持つアーキテクチャを想定）：

uint32_t moveNib(uint32_t x, int n) { return x<<(n<<2) | x>>((9+~n)<<2); }

編集2：わかりました。以外は使えないのでint、これはどうですか？

int moveNib(int x, int n) { return (x&0xffffffff)<<(n<<2) | (x&0xffffffff)>>((9+~n)<<2); }

ロジックは前と同じですが、 と AND することにより、計算で符号なし整数を使用するように強制します0xffffffff。ただし、これはすべて 32 ビット整数を想定しています。私が今見逃しているものは他にありますか？

Edit3:これはもう1つのバージョンです。これはもう少し移植性が高いはずです:

int moveNib(int x, int n) { return ((x|0u)<<((n&7)<<2) | (x|0u)>>((9+~(n&7))<<2))&0xffffffff; }

nchux で提案されているようにキャップし|0u、符号付き整数で得られる符号ビットの重複を避けるために、符号なしに変換するために使用します。これは（標準から）次の理由で機能します。

それ以外の場合、符号なし整数型のオペランドのランクが他のオペランドの型のランク以上である場合、符号付き整数型のオペランドは符号なし整数型のオペランドの型に変換されます。

intと0uは同じランクですが、符号がないため0u、0 との OR 演算は null 演算になりますが、結果は符号なしになります。

次に、結果を 32 ビットの範囲に切り捨てて、intint がこれよりも多くのビットを持っている場合でも関数が機能するようにします (ただし、その場合でもローテーションは最下位の 32 ビットで実行されます。64 ビット バージョンは7 を 15 に、9 を 17 に置き換え、0xffffffffffffffff を使用して切り捨てます)。

このソリューションでは、12 個の演算子を使用します (切り捨てをスキップする場合は 11 個n&7、変数に格納する場合は 10 個)。

ここで何が起こるかを詳しく見るために、あなたが与えた例について見てみましょう: x=0x87654321, n=1. x|0u符号なしの数値になり0x87654321uます。(n&7)<<2=4は左に 4 ビットシフト((9+~(n&7))<<2=28し、 は右に 28 ビットシフトします。これをまとめると、 を計算し0x87654321u<<4 | 0x87654321u >> 28ます。32 ビット整数の場合、これは0x76543210|0x8=0x76543218. しかし、64 ビット整数の場合は0x876543210|0x8=0x876543218であるため、その場合は 32 ビットに切り詰める必要があり、これが final の&0xffffffff動作です。整数が 32 ビットより短い場合、これは機能しませんが、質問の例では 32 ビットだったので、整数型は少なくともその長さであると想定しています。

ちょっとした補足として: リストにない 1 つの演算子 (演算子) を許可するsizeofと、長い int のすべてのビットを自動的に処理するバージョンを作成できます。Aki に触発されて、次のようになります (16 個の演算子を使用します ( sizeofC の演算子であることを思い出してください)):

int moveNib(int x, int n) {
    int nbit = (n&((sizeof(int)<<1)+~0u))<<2;
    return (x|0u)<<nbit | (x|0u)>>((sizeof(int)<<3)+1u+~nbit);
}
于 2014-03-02T02:36:15.010 に答える
3

追加の制限がなければ、典型的なrotate_left操作（0 < n < 32による）は自明です。

uint32_t X = (x << 4*n) | (x >> 4*(8-n));

回転について話しているので、n < 0 は問題ではありません。右に 1 回転することは、左に 7 単位回転することと同じです。すなわち。nn=n & 7;そして私たちは終わりました。

int nn = (n & 7) << 2;                         // Remove the multiplication
uint32_t X = (x << nn) | (x >> (32-nn));

の場合nn == 0、x は 32 だけシフトされますが、これは未定義です。これは単純に に置き換えることができますx >> 0。つまり、まったく回転しません。(x << 0) | (x >> 0) == x.

減算を加算に置き換えます: a - b = a + (~b+1)および単純化:

int nn = (n & 7) << 2;
int mm = (33 + ~nn) & 31;
uint32_t X = (x << nn) | (x >> mm);    // when nn=0, also mm=0

ここで唯一の問題は、 signed int xを右にシフトすることです。これにより、符号ビットが複製されます。それはマスクで治すべきです：(x << nn) - 1

int nn = (n & 7) << 2;
int mm = (33 + ~nn) & 31;
int result = (x << nn) | ((x >> mm) & ((1 << nn) + ~0));

この時点で、許可された操作のうち 12 個しか使用していません。次に、sizeof(int) の問題を掘り下げることができます...

int nn = (n & (sizeof(int)-1)) << 2; // etc.
于 2014-03-02T12:40:51.583 に答える