今日暗号機を実装していました。暗号機は必ずと行っていいほど循環シフトがあります。今回使い慣れているC++で実装していたわけですが、循環シフトがあるのかな？と思って調べたらあったのでメモしています。
1.ビットシフトと循環シフト
ビットシフトは任意ビット左右のどちらかにシフトさせることです。このとき空いたビットには0が入ります。またシフト方向に溢れたビットは消えます。
例えば10110111というビット列を左に3ビットシフトさせると、10111000になります。
一方で巡回シフトはビット列の左端と右端が繋がっているように扱ってシフトします。シフト方向に溢れた桁は逆の端に置かれます。
先程の10110111というビット列を左に3ビット循環シフトさせると、10111101になります。
2.C++での循環シフトの実装
PythonではNumpyのroll関数で実装されています。これは右循環シフトを正としていることに注意です。左循環シフトの場合は第2引数を負の数にするようです。
さて、今までC++ではビットシフトはありましたが、循環シフトはありませんでした。そのため循環シフトをする場合は次のように実装する必要がありました。先程の10110111というビット列を左に3ビット循環シフトさせたいとき次のようになります。
bitset<8> sample("10110111"); //例のビット列
sampleB = (sample << 3) | (sample >> 5);
cout << sampleB << endl;
つまり、左にaビット循環シフトさせたい時は、ビット列の長さがNであった場合、次のように実装すると実現できます。
(sample << a) | (sample >> (N - a))
3.C++20での循環シフト
C++20から左循環シフトはrotl()関数、右循環シフトはrotrが実装されました。bitヘッダのincludeが必要です。
この2つの関数ですが、第2引数を負の数にすることでrotlは右循環シフト、rotrは左循環シフトの結果を出力させることが出来ます。
4.ビットシフトとシフトローテーションの比較コード
5.おわりに
C++まじでわからん。