115

左シフト演算子と右シフト演算子 (<< と >>) は C++ で既に使用できます。ただし、循環シフトまたは回転操作を実行する方法がわかりませんでした。

「左に回転」「右に回転」などの操作はどのように実行できますか?

ここで右に2回転

Initial --> 1000 0011 0100 0010

結果は次のようになります。

Final   --> 1010 0000 1101 0000

例が役に立ちます。

(編集者注: C で回転を表現する一般的な方法の多くは、回転カウントがゼロの場合、または単一の回転マシン命令以上にコンパイルされた場合、未定義の動作に悩まされます。この質問の回答は、ベスト プラクティスを文書化する必要があります。)

4

16 に答える 16

124

x86 用に asm gcc/clang が生成するものに関する詳細については、別のローテーションの質問に関するこの回答の以前のバージョンも参照してください。

未定義の動作を回避する、C および C++ でローテーションを表現する最もコンパイラに適した方法は、John Regehr の実装のようです。タイプの幅で回転するように調整しました（のような固定幅タイプを使用uint32_t）。

#include <stdint.h>   // for uint32_t
#include <limits.h>   // for CHAR_BIT
// #define NDEBUG
#include <assert.h>

static inline uint32_t rotl32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);  // assumes width is a power of 2.

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n<<c) | (n>>( (-c)&mask ));
}

static inline uint32_t rotr32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n>>c) | (n<<( (-c)&mask ));
}

だけuint32_tでなく、任意の符号なし整数型で機能するため、他のサイズのバージョンを作成できます。

多くの安全性チェック (型幅が 2 のべき乗であることを含む) を備えた C++11 テンプレート バージョンも参照static_assertしてください。これは、たとえば、一部の 24 ビット DSP や 36 ビット メインフレームには当てはまりません。

テンプレートは、回転幅を明示的に含む名前を持つラッパーのバックエンドとしてのみ使用することをお勧めします。 整数昇格規則は、rotl_template(u16 & 0x11UL, 7)が 16 ビットではなく 32 ビットまたは 64 ビットの回転を行うことを意味します( の幅に応じてunsigned long)。Evenuint16_t & uint16_tは、C++ の整数昇格規則によって に昇格されます。ただし、が より広くないsigned intプラットフォームを除きます。intuint16_t

x86 では、このバージョンはそれを grok するコンパイラでシングルrol r32, cl(または) にインライン展開されます。これは、 x86 の回転命令とシフト命令が C ソースと同じ方法でシフト カウントをマスクすることをコンパイラが認識しているためです。rol r32, imm8

x86 でのこの UB 回避イディオムのコンパイラ サポート、uint32_t xおよびunsigned int n可変カウント シフトの場合:

  • clang: clang3.5 以降の可変カウント ローテーション、複数のシフト + またはその前の insn で認識されます。
  • gcc: gcc4.9 以降の変数カウント ローテーション、複数のシフト+またはその前の insns で認識されます。gcc5 以降では、変数カウントにroror命令のみを使用して、ウィキペディア バージョンでもブランチとマスクを最適化します。rol
  • icc: ICC13 以前から可変カウント ローテーションでサポートされています。MOV を保存するために BMI2 が利用できない場合、一部の CPU (特に AMD だけでなく一部の Intel)shld edi,edi,7よりも遅く、より多くのバイトを必要とする定数カウント ローテーションの使用。rol edi,7rorx eax,edi,25
  • MSVC: x86-64 CL19: 定数カウントのローテーションでのみ認識されます。(ウィキペディアのイディオムは認識されますが、ブランチと AND は最適化されていません)。x86 (x86-64 を含む)の_rotl/_rotr組み込み関数を使用します。<intrin.h>

ARM の gcc はand r1, r1, #31for variable-count ローテーションを使用しますが、実際のローテーションは 1 つの命令で行います: ror r0, r0, r1。そのため、gcc は、回転カウントが本質的にモジュールであることを認識していません。ARM のドキュメントにあるように、「シフト長の RORnは、32 以上はシフト長の ROR と同じn-32」です。ここで gcc が混乱するのは、ARM の左/右シフトがカウントを飽和させるためだと思います。そのため、32 以上のシフトはレジスタをクリアします。(シフトが回転と同じようにカウントをマスクする x86 とは異なります)。そのターゲットで非循環シフトがどのように機能するかにより、回転イディオムを認識する前に AND 命令が必要であると判断する可能性があります。

現在の x86 コンパイラは、おそらく ARM で AND を回避しないのと同じ理由で、8 ビットと 16 ビットのローテーションの変数カウントをマスクするために追加の命令を使用しています。パフォーマンスは x86-64 CPU のローテーション カウントに依存しないため、これは最適化の失敗です。(カウントのマスキングは、パフォーマンス上の理由から 286 で導入されました。これは、最新の CPU のように一定の待機時間ではなく、シフトを反復的に処理するためです。)

32-nところで、右回転のみを提供するARMやMIPSなどのアーキテクチャでコンパイラが左回転を実装することを避けるために、可変カウント回転には右回転を優先します。(これにより、コンパイル時の定数カウントが最適化されます。)

興味深い事実: ARM には専用のシフト/回転命令は実際にはありません。ROR モードでソース オペランドがバレル シフターを通過するだけの MOVですmov r0, r0, ror r1。したがって、回転は、EOR 命令などのレジスタ ソース オペランドにフォールドできます。

nと戻り値にunsigned 型を使用していることを確認してください。(x86 ターゲットの gcc は算術右シフトを行い、ゼロではなく符号ビットのコピーをシフトするためOR、2 つのシフトされた値を一緒にすると問題が発生します。負の符号付き整数の右シフトは、C の実装定義の動作です。)

また、シフト カウントが unsigned typeであることを確認してください。符号付き(-n)&31の型は 1 の補数または符号/大きさになる可能性があり、符号なしまたは 2 の補数で得られるモジュラー 2^n とは異なるためです。(Regehr のブログ投稿のコメントを参照してください)。 unsigned intのすべての幅について、私が見たすべてのコンパイラでうまくいきますx。他のいくつかの型は、実際には一部のコンパイラのイディオム認識を無効にするため、 と同じ型を使用しないでくださいx。

一部のコンパイラは、rotates の組み込み関数を提供します。これは、対象のコンパイラでポータブル バージョンが適切なコードを生成しない場合、inline-asm よりもはるかに優れています。私が知っているコンパイラには、クロスプラットフォームの組み込み関数はありません。x86 オプションの一部を次に示します。

  • と組み込み関数を<immintrin.h>提供する_rotl_rotl64インテルのドキュメント、および右シフトについても同じです。MSVC は必要ですが<intrin.h>、gcc は必要です<x86intrin.h>。An#ifdefは gcc と icc を区別します。Clang 9.0にもありますが、それ以前は、MSVC互換モードを除いて、-fms-extensions -fms-compatibility -fms-compatibility-version=17.00どこにも提供されていないようです. そして、それが彼らのために発するasmは最悪です（余分なマスキングとCMOV）。
  • MSVC:_rotr8および_rotr16.
  • gcc および icc (clang ではない): / ( 8 ビットの左/右回転用)、/ (16 ビット)、 / (32 ビット)、/ (64 ビット、64 ビット ターゲットに対してのみ定義)<x86intrin.h>も提供します。狭いローテーションの場合、実装ではorを使用しますが、32 ビットと 64 ビットのローテーションは shift/or を使用して定義されます (コードはx86 の gcc でのみ動作する必要があるため、UB に対する保護はありません)。GNU Cには、クロスプラットフォーム機能がないように見えます（単一の命令でなくても、ターゲットプラットフォームで最適なものに拡張されます）。ほとんどの場合、イディオム認識から適切なコードが得られます。__rolb__rorb__rolw__rorw__rold__rord__rolq__rorq__builtin_ia32_rolhi...qiia32intrin.h__builtin_rotate__builtin_popcount
// For real use, probably use a rotate intrinsic for MSVC, or this idiom for other compilers.  This pattern of #ifdefs may be helpful
#if defined(__x86_64__) || defined(__i386__)

#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>  // Not just <immintrin.h> for compilers other than icc
#endif

uint32_t rotl32_x86_intrinsic(rotwidth_t x, unsigned n) {
  //return __builtin_ia32_rorhi(x, 7);  // 16-bit rotate, GNU C
  return _rotl(x, n);  // gcc, icc, msvc.  Intel-defined.
  //return __rold(x, n);  // gcc, icc.
  // can't find anything for clang
}
#endif

おそらく一部の非 x86 コンパイラにも組み込み関数がありますが、このコミュニティ wiki の回答を拡張してそれらすべてを含めることはやめましょう。（組み込みに関する既存の回答でそれを行うかもしれません）。

(この回答の古いバージョンでは、MSVC 固有のインライン asm (32 ビット x86 コードでのみ機能します)、またはC バージョンの場合はhttp://www.devx.com/tips/Tip/14043が提案されました。コメントはそれに返信しています。 .)

インライン asm は、入力の保存/再読み込みを強制するため、特に MSVC スタイルの多くの最適化を無効にします。慎重に作成された GNU C inline-asm の回転により、カウントをコンパイル時定数シフト カウントの直接オペランドにすることができますが、シフトする値がコンパイル時定数でもある場合、完全に最適化することはできませんでした。インライン化後。 https://gcc.gnu.org/wiki/DontUseInlineAsm .

于 2009-04-22T10:28:05.637 に答える
35

C++ であるため、インライン関数を使用します。

template <typename INT> 
INT rol(INT val) {
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

C++11 バリアント:

template <typename INT> 
constexpr INT rol(INT val) {
    static_assert(std::is_unsigned<INT>::value,
                  "Rotate Left only makes sense for unsigned types");
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}
于 2009-04-22T10:35:58.970 に答える
23

ほとんどのコンパイラには、そのための組み込みがあります。_rotr8、_rotr16などの Visual Studio

于 2009-04-22T10:42:58.360 に答える
16

決定的に：

template<class T>
T ror(T x, unsigned int moves)
{
  return (x >> moves) | (x << sizeof(T)*8 - moves);
}
于 2012-12-05T20:50:36.793 に答える
8

xが8ビット値の場合、次を使用できます。

x=(x>>1 | x<<7);
于 2010-04-27T11:55:02.130 に答える
7

標準のビットセットを使用して、このようなものをどのように使用するか...

#include <bitset> 
#include <iostream> 

template <std::size_t N> 
inline void 
rotate(std::bitset<N>& b, unsigned m) 
{ 
   b = b << m | b >> (N-m); 
} 

int main() 
{ 
   std::bitset<8> b(15); 
   std::cout << b << '\n'; 
   rotate(b, 2); 
   std::cout << b << '\n'; 

   return 0;
}

HTH、

于 2009-04-22T11:01:21.717 に答える
6

詳細には、次のロジックを適用できます。

ビットパターンが整数で 33602 の場合

1000 0011 0100 0010

次に、2 つの右シフトでロール オーバーする必要があります。最初にビット パターンのコピーを作成し、次に左シフトします。

左シフトを14回行った後、取得します。

1000 0000 0000 0000

ここで、値 33602 を必要に応じて 2 回右シフトします。あなたが得る

0010 0000 1101 0000

ここで、左に 14 倍シフトした値と右に 2 倍シフトした値の間で OR を取ります。

1000 0000 0000 0000
0010 0000 1101 0000
===================
1010 0000 1101 0000
===================

そして、シフトされたロールオーバー値を取得します。ビット単位の操作の方が高速であり、ループも必要ないことを忘れないでください。

于 2009-04-22T11:40:05.370 に答える
5

ビット単位で右にシフトしたいと仮定Lし、入力xはNビットを含む数値です。

unsigned ror(unsigned x, int L, int N) 
{
    unsigned lsbs = x & ((1 << L) - 1);
    return (x >> L) | (lsbs << (N-L));
}
于 2009-04-22T10:36:29.063 に答える
3

正しい答えは次のとおりです。

#define BitsCount( val ) ( sizeof( val ) * CHAR_BIT )
#define Shift( val, steps ) ( steps % BitsCount( val ) )
#define ROL( val, steps ) ( ( val << Shift( val, steps ) ) | ( val >> ( BitsCount( val ) - Shift( val, steps ) ) ) )
#define ROR( val, steps ) ( ( val >> Shift( val, steps ) ) | ( val << ( BitsCount( val ) - Shift( val, steps ) ) ) )
于 2014-05-30T15:20:05.670 に答える
0

別の提案

template<class T>
inline T rotl(T x, unsigned char moves){
    unsigned char temp;
    __asm{
        mov temp, CL
        mov CL, moves
        rol x, CL
        mov CL, temp
    };
    return x;
}
于 2013-11-16T02:13:28.073 に答える
0

ソースコード×ビット数

int x =8;
data =15; //input
unsigned char tmp;
for(int i =0;i<x;i++)
{
printf("Data & 1    %d\n",data&1);
printf("Data Shifted value %d\n",data>>1^(data&1)<<(x-1));
tmp = data>>1|(data&1)<<(x-1);
data = tmp;  
}
于 2013-10-31T05:24:14.910 に答える
-1 
--- Substituting RLC in 8051 C for speed --- Rotate left carry
Here is an example using RLC to update a serial 8 bit DAC msb first:
                               (r=DACVAL, P1.4= SDO, P1.5= SCLK)
MOV     A, r
?1:
MOV     B, #8
RLC     A
MOV     P1.4, C
CLR     P1.5
SETB    P1.5
DJNZ    B, ?1

Here is the code in 8051 C at its fastest:
sbit ACC_7  = ACC ^ 7 ; //define this at the top to access bit 7 of ACC
ACC     =   r;
B       =   8;  
do  {
P1_4    =   ACC_7;  // this assembles into mov c, acc.7  mov P1.4, c 
ACC     <<= 1;
P1_5    =   0;
P1_5    =   1;
B       --  ; 
    } while ( B!=0 );
The keil compiler will use DJNZ when a loop is written this way.
I am cheating here by using registers ACC and B in c code.
If you cannot cheat then substitute with:
P1_4    =   ( r & 128 ) ? 1 : 0 ;
r     <<=   1;
This only takes a few extra instructions.
Also, changing B for a local var char n is the same.
Keil does rotate ACC left by ADD A, ACC which is the same as multiply 2.
It only takes one extra opcode i think.
Keeping code entirely in C keeps things simpler sometimes.
于 2015-08-14T21:12:11.750 に答える
-1 
#define ROTATE_RIGHT(x) ( (x>>1) | (x&1?0x8000:0) )
于 2009-04-22T10:26:11.693 に答える
-1

関数をオーバーロードします。

unsigned int rotate_right(unsigned int x)
{
 return (x>>1 | (x&1?0x80000000:0))
}

unsigned short rotate_right(unsigned short x) { /* etc. */ }
于 2009-04-22T10:38:09.713 に答える