11

整数 x を左に n ビット回転する左回転関数を実装しようとしています。

  • 例：rotateLeft(0x87654321,4) = 0x76543218
  • 法的操作: ~ & ^ | + << >>

これまでのところ、私はこれを持っています:

int rotateLeft(int x, int n) {
  return ((x << n) | (x >> (32 - n)));
}

署名された整数では機能しないことがわかりました..これを修正する方法について誰かアイデアがありますか?

だから今私は試しました：

int rotateLeft(int x, int n) {
  return ((x << n) | ((x >> (32 + (~n + 1))) & 0x0f));
}

そしてエラーを受け取ります：

エラー：rotateLeft（-2147483648 [0x80000000]、1 [0x1]）のテストに失敗しました... ... 15 [0xf]を返します。1[0x1] である必要があります

4

6 に答える 6

16

コンパイラに適したローテーションの現在のベスト プラクティスは、このコミュニティ ウィキの Q&Aです。ウィキペディアのコードは、clang や 5.1 より前の gcc では非常に優れた asm を生成しません。

ウィキペディアには、循環シフトとも呼ばれるビット ローテーションの非常に優れた詳細な説明があります。

そこから引用：

unsigned int _rotl(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
      return value;
    return (value << shift) | (value >> (sizeof(value)*8 - shift));
}

unsigned int _rotr(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
      return value;
    return (value >> shift) | (value << (sizeof(value)*8 - shift));

あなたの場合、乗算演算子にアクセスできないため、に置き換えることができ*8ます<< 3。

編集if使用できないステートメントを指定して、ステートメントを削除することもできますif。これは最適化ですが、それがなくても正しい値が得られます。

整数のビットを本当にローテーションするつもりならsigned、ローテーションされた結果の解釈はプラットフォームに依存することに注意してください。具体的には、プラットフォームが2 の補数または1 の補数を使用するかどうかによって異なります。符号付き整数のビットをローテーションすることが意味のあるアプリケーションは考えられません。

于 2012-04-13T03:31:55.133 に答える
4 
int rotateLeft(int x, int n) {
  return (x << n) | (x >> (32 - n)) & ~((-1 >> n) << n);
}

更新:(どうもありがとう@George)

int rotateLeft(int x, int n) {
  return (x << n) | (x >> (32 - n)) & ~(-1 << n);
}

「-」バージョンは使用しないでください。

int rotateLeft(int x, int n) {
    return (x << n) | (x >> (0x1F & (32 + ~n + 1))) & ~(0xFFFFFFFF << n);
}

//test program
int main(void){
    printf("%x\n",rotateLeft(0x87654321,4));
    printf("%x\n",rotateLeft(0x87654321,8));
    printf("%x\n",rotateLeft(0x80000000,1));
    printf("%x\n",rotateLeft(0x78123456,4));
    printf("%x\n",rotateLeft(0xFFFFFFFF,4));
    return 0;
}
/* result : GCC 4.4.3 and Microsoft(R) 32-bit C 16.00.40219.01
76543218
65432187
1
81234567
ffffffff
*/
于 2012-04-13T09:43:06.317 に答える
1

最良の方法は次のとおりです。

int rotateLeft(int x, int n)
{
    _asm
    {
        mov eax, dword ptr [x]
        mov ecx, dword ptr [n]
        rol eax, cl
    }
}

intコード内で変数を正しくローテーションする必要がある場合、最も速い方法は次のとおりです。

#define rotl( val, shift ) _asm mov eax, dword ptr[val] _asm mov ecx, dword ptr [shift] _asm rol eax, cl _asm mov dword ptr [val], eax

valは回転する値、shiftは回転の長さです。

于 2016-07-07T14:11:23.333 に答える
0

の「左回転」を定義できますsigned intか?

にキャストxして、unsigned int現在の方法でローテーションを実行するだけです。

別の注意: コードは (32 ビットだけでなく) さまざまなアーキテクチャで動作する必要がありますか? ビットサイズのハードコーディングは避けたほうがよいintでしょう。

于 2012-04-13T03:27:05.073 に答える
0

ISO C (これが実装言語であるかどうかはわかりませんが、確かにそのように見えます) では、負の符号付き整数の右シフトは実装定義であるため、避ける必要があります。

とにかく bitops を行っている場合は、最初に符号なし整数にキャストする必要があります。

于 2013-09-17T19:46:53.140 に答える