C ++での循環シフト(回転)操作のベストプラクティス

2009年04月22日に質問されました。  ·  閲覧回数 115.7k回  ·  ソース

Elroy picture
2009年04月22日

左および右のシフト演算子(<<および>>)は、C ++ですでに使用可能です。 しかし、どうすれば循環シフトや回転操作ができるのかわかりませんでした。

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

ここで右に2回回転します

Initial --> 1000 0011 0100 0010

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

Final   --> 1010 0000 1101 0000

例が役に立ちます。

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

回答

AndreasT picture
2009年04月22日
106

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

未定義の振る舞いを回避するCおよびC ++で回転を表現するための最もコンパイラーに優しい方法は、 JohnRegehrの実装のようです。 タイプの幅で回転するように調整しました( 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だけでなく、任意の符号なし整数型で機能するため、他のサイズのバージョンを作成できます。

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

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


x86では、このバージョンは、 x86の回転およびシフト命令がCと同じようにシフトカウントをマスク単一のrol r32, cl (またはrol r32, imm8 )にインライン化されます。ソースはします。

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

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

ARMのgccは、可変カウントローテーションにand r1, r1, #31を使用しますが、実際のローテーションは1つの命令ror r0, r0, r1ます。 したがって、gccは、rotate-countが本質的にモジュール式であることを認識していません。 ARMのドキュメントにあるように、 「シフト長n ROR、32を超えるものは、シフト長n-32 RORと同じです

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

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

おもしろい事実:ARMには実際には専用のシフト/回転命令はありません。RORモードでソースオペランドがバレルシフタを通過するMOVmov r0, r0, ror r1 。 したがって、rotateは、EOR命令などのレジスタソースオペランドに折りたたむことができます。


nと戻り値に符号なし型を使用していることを確認してくださいORすると問題が発生します。負の符号付き整数の右シフトは実装です- Cで定義された動作。)

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


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

  • Intelは、 <immintrin.h>_rotl_rotl64組み込みを提供し、右シフトについても同じであることを文書化しています。 MSVCには<intrin.h>必要ですが、gccには<x86intrin.h>必要です。 #ifdefはgccとiccを処理しますが、 -fms-extensions -fms-compatibility -fms-compatibility-version=17.00を使用するMSVC互換モードを除いて、 clangはそれらをどこにも提供していないようです。 そしてそれが彼らのために放出するasmは吸う(余分なマスキングとCMOV)。
  • MSVC: _rotr8および_rotr16
  • gccおよびicc(clangではない): <x86intrin.h>は、8ビットの左/右回転に__rolb / __rorb__rolw / __rorw (16ビット)、 __rold / __rord (32ビット)、 __rolq / __rorq (64ビット、64ビット用にのみ定義ターゲット)。 狭いローテーションの場合、実装は__builtin_ia32_rolhiまたは...qiを使用しますが、32ビットおよび64ビットのローテーションはshift / orを使用して定義されます( ia32intrin.hコードのため、UBに対する保護はありません) __builtin_popcount場合のようにクロスプラットフォームの__builtin_rotate関数がないようです(これは、単一の命令でなくても、ターゲットプラットフォームで最適なものに拡張されます)。 ほとんどの場合、イディオム認識から優れたコードを取得します。

// 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コンパイラーにも組み込み関数がありますが、このcommunity-wikiの回答を拡張してすべてを含めることはしないでください。 (おそらく、組み込み関数に関する既存の回答でそれを


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

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

MSalters picture
2009年04月22日
33

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));
}
VolkerK picture
2009年04月22日
21

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

C ++ 20 std::rotlおよびstd::rotr

到着しました! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.htmlで、 <bit>ヘッダーに追加する必要があります

cppreferenceによると、使用法は次のようになります。

#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t i = 0b00011101;
    std::cout << "i          = " << std::bitset<8>(i) << '\n';
    std::cout << "rotl(i,0)  = " << std::bitset<8>(std::rotl(i,0)) << '\n';
    std::cout << "rotl(i,1)  = " << std::bitset<8>(std::rotl(i,1)) << '\n';
    std::cout << "rotl(i,4)  = " << std::bitset<8>(std::rotl(i,4)) << '\n';
    std::cout << "rotl(i,9)  = " << std::bitset<8>(std::rotl(i,9)) << '\n';
    std::cout << "rotl(i,-1) = " << std::bitset<8>(std::rotl(i,-1)) << '\n';
}

出力を与える:

i          = 00011101
rotl(i,0)  = 00011101
rotl(i,1)  = 00111010
rotl(i,4)  = 11010001
rotl(i,9)  = 00111010
rotl(i,-1) = 10001110

サポートがGCCに到着したら試してみますが、 g++-9 -std=c++2a GCC9.1.0はまだサポートしていません。

提案は言う:

ヘッダ:

namespace std {
  // 25.5.5, rotating   
  template<class T>
    [[nodiscard]] constexpr T rotl(T x, int s) noexcept;
  template<class T>
    [[nodiscard]] constexpr T rotr(T x, int s) noexcept;

そして:

25.5.5回転[bitops.rot]

以下の説明では、Nがstd::numeric_limits<T>::digits表すとします。

template<class T>
  [[nodiscard]] constexpr T rotl(T x, int s) noexcept;

制約:Tは符号なし整数型です(3.9.1 [basic.fundamental])。

rをs%Nとします。

戻り値:rが0の場合、x; rが正の場合、 (x << r) | (x >> (N - r)) ; rが負の場合、 rotr(x, -r)

template<class T>
  [[nodiscard]] constexpr T rotr(T x, int s) noexcept;

制約:Tは符号なし整数型です(3.9.1 [basic.fundamental])。 rをs%Nとします。

戻り値:rが0の場合、x; rが正の場合、 (x >> r) | (x << (N - r)) ; rが負の場合、 rotl(x, -r)

1ビットの数を数えるためにstd::popcountも追加されました: 32ビット整数のセットビットの数を数える方法は?

Didac Perez Parera picture
2012年12月06日
15

間違いなく:

template<class T>
T ror(T x, unsigned int moves)
{
  return (x >> moves) | (x << sizeof(T)*8 - moves);
}
Abhay picture
2009年04月22日
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、

Farhadix picture
2010年04月27日
7

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

x=(x>>1 | x<<7);
S M Kamran picture
2009年04月22日
6

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

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

 1000 0011 0100 0010

次に、2つの右シフトでロールオーバーする必要があります。最初にビットパターンのコピーを作成し、次にそれを左シフトします。長さ-右シフト、つまり長さは16右シフト値は2 16-2 = 14

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
 ===================

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

nimrodm picture
2009年04月22日
5

Lビットだけ右にシフトしたいとし、入力xNビットの数値であると仮定します。

unsigned ror(unsigned x, int L, int N) 
{
    unsigned lsbs = x & ((1 << L) - 1);
    return (x >> L) | (lsbs << (N-L));
}
user3102555 picture
2014年05月30日
4

正解は次のとおりです。

#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 ) ) ) )