質問: 0; i < n; i++){ if(x & 1U){ x >>= 1; x ^ ~bitMax; }else{ x >>= 1; } } return x; } ``` ### 疑問点 xの最下位ビットが1であれば全ビットを右に1シフトして、 最上位ビットのみ1である ~bitMaxと排他的論理和をすれば、良いのでは? と、思ったのですが上手く動作しませんでした。 この方法では、この問題は解けないのかどうか知りたいです。 また、ネットで調べてみると右にシフトした後左にシフトし・・・ といった方法があるみたいですが、良く分からなかったのでその解説もしていただけると有り難いです。 ### 補足情報 左回りは右回りの理解ができたらしようと思っています。 int型が32ビットの実行環境 書籍 新・明解 c言語 入門編 演習 7-3
回答: ちゃんと実装してみました。 ``` #include unsigned int rrotate(unsigned int x, int n); unsigned int lrotate(unsigned int x, int n); #define UINT_BIT (sizeof(unsigned int) * CHAR_BIT) unsigned int rrotate(unsigned int x, int n) { n %= UINT_BIT; if (n < 0) n += UINT_BIT; return (x >> n) | (x << (UINT_BIT - n)); } unsigned int lrotate(unsigned int x, int n) { return rrotate(x, -(n % UINT_BIT)); } ``` まず、`UINT_BIT`は`unsigned int`のビット数です。`sizeof`でバイト数を求めて1バイトのビット数である`CHAR_BIT`をかけています。 全ての肝は、`(x >> n) | (x << (UINT_BIT - n))`の部分です。`x >> n`は`x`を`n`ビット**右に**ずらす事になりますが、左側の`n`ビット分が全て0になってしまいます。ここにちょうど、もともとの`x`での右側`n`ビット分が入れば良い事になります。`x`は全体で`UINT_BIT`ありますから`UINT_BIT - n`ビット分**左に**ずらせば、ちょうど良く、右側`n`ビット分が先頭に来ることになり、残りは0になります。それが`x << (UINT_BIT - n)`の部分です。あとは、この二つのビット和を取れば、回転したものになります。なお、負の値は逆方向とも考えられます。つまり、左回転は右回転での負の方向と言うだけです。 `n`が`UINT_BIT`を超える場合や負の場合は、`UINT_BIT`毎回転した場合は同じであるという性質から、適切な`UINT_BIT`の倍数を加算または減算すれば良い事になります。つまりそれは`UINT_BIT`で割った余りを求めるのと同じです。 さて、これで済んでいれば簡単ですが、C言語特有の動作未定義や実装依存を考慮しなければなりません。 * シフト演算子右辺値が負の値またはビット数を超える場合は動作未定義。 * `INT_MIN`の`-`単項演算子はオーバーフローするため動作未定義。 * `%`の商が切り詰められる方向は、C99より前は実装依存、C99以降は0の方向。 そういった諸々を考慮した結果、上のコードになります。 【おまけ】 1ビットずつずらす版も作りました。nが大きいととても遅いです。**最適化しない場合や、最適化が甘いコンパイラでコンパイルした場合、スタックオーバフローを起こす場合があります。**(GCCで-O2なら大丈夫です) ``` #include unsigned int rrotate(unsigned int x, int n); unsigned int lrotate(unsigned int x, int n); #define UINT_BIT (sizeof(unsigned int) * CHAR_BIT) #define UINT_TOP_BIT (0x1u << (UINT_BIT - 1)) unsigned int rrotate(unsigned int x, int n) { if (n == 0) return x; else if (n < 0) return rrotate((x << 1) | (!!(UINT_TOP_BIT & x)), n + 1); else return rrotate((x >> 1) | (UINT_TOP_BIT * (x & 0x1u)), n - 1); } unsigned int lrotate(unsigned int x, int n) { if (n < -INT_MAX) return rrotate((x >> 1) | (UINT_TOP_BIT * (x & 0x1u)), -(n + 1)); return rrotate(x, -n); } ```