ビットの回転について

###前提
現在書籍でｃ言語を学習している者です。
その書籍の演習問題は解答が存在しておらず（著者の意図的に）
学習を進めることが困難な時があるので、問題のヒント等を教えていただきたいです。

###問題
符号なし整数ｘの全ビットを右にｎビット回転した値を返す関数rrotateと、左にnビット回転した値を返す関数lrotateを作成せよ。

lang
1unsigned rrotate(unsigned x, int n){/* ...  */}
2unsigned lrotate(unsigned x, int n){/* ...  */}

※回転とは、再開ビットと最上位ビットがつながっているとみなしてシフトすることである。

###該当のソースコード

lang
1#define bitMax 2147483647 /*最上位ビット以外１*/
2
3unsigned rrotate (unsigned x, int n){
4    int i;
5    for(i = 0; i < n; i++){
6        if(x & 1U){
7            x >>= 1;
8            x ^ ~bitMax;
9        }else{
10            x >>= 1;
11        }
12    }
13    return x;
14}

###疑問点
ｘの最下位ビットが１であれば全ビットを右に１シフトして、
最上位ビットのみ１である ~bitMaxと排他的論理和をすれば、良いのでは？
と、思ったのですが上手く動作しませんでした。

この方法では、この問題は解けないのかどうか知りたいです。

また、ネットで調べてみると右にシフトした後左にシフトし・・・
といった方法があるみたいですが、良く分からなかったのでその解説もしていただけると有り難いです。

###補足情報
左回りは右回りの理解ができたらしようと思っています。

int型が３２ビットの実行環境
書籍新・明解ｃ言語入門編
演習７－３

行動規範の内容に同意します

回答4件

こんにちは。

また、ネットで調べてみると右にシフトした後左にシフトし・・・
といった方法があるみたいですが、良く分からなかったのでその解説もしていただけると有り難いです。

おそらく、次の画像のようなイメージかと思われます。

n ビット右シフトした値と、32-n ビット左シフトした値の論理和をとれば、求めたい値になるはずです。

c:
1unsigned int rrotate (unsigned int x, unsigned int n) {
2  return x>>n | x<<(32-n);
3}

投稿2017/08/26 13:39

退会済みユーザー

総合スコア0

kamecha

2017/08/26 23:33

有り難うございます。図を使った解説とても分かりやすかったです。

行動規範の内容に同意します

こんにちは。

x ^ ~bitMax;にx=が漏れているだけでは？
ところで、排他的論理和でダメではないですが、このような時は論理和を使った方が素直と思います。

投稿2017/08/26 12:54

Chironian

総合スコア23272

kamecha

2017/08/26 23:32

有り難うございます。簡単なミスがあったみたいです。

行動規範の内容に同意します

最下位ビットが1であればシフト後に最上位ビットを1にするというアプローチは方法の一つとして問題ないと思います。
この場合、シフト後に取得するのは排他的論理和ではなく、論理和ではないでしょうか。

投稿2017/08/26 11:42

退会済みユーザー

総合スコア0

kamecha

2017/08/26 23:26

なるほど！論理和の方がすっきりしてますね。

行動規範の内容に同意します

ベストアンサー

ちゃんと実装してみました。

C
1#include <limits.h>
2
3unsigned int rrotate(unsigned int x, int n);
4unsigned int lrotate(unsigned int x, int n);
5
6#define UINT_BIT (sizeof(unsigned int) * CHAR_BIT)
7
8unsigned int rrotate(unsigned int x, int n)
9{
10	n %= UINT_BIT;
11	if (n < 0) n += UINT_BIT;
12	return (x >> n) | (x << (UINT_BIT - n));
13}
14
15unsigned int lrotate(unsigned int x, int n)
16{
17	return rrotate(x, -(n % UINT_BIT));
18}

まず、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なら大丈夫です)

C
1#include <limits.h>
2
3unsigned int rrotate(unsigned int x, int n);
4unsigned int lrotate(unsigned int x, int n);
5
6#define UINT_BIT (sizeof(unsigned int) * CHAR_BIT)
7#define UINT_TOP_BIT (0x1u << (UINT_BIT - 1))
8
9unsigned int rrotate(unsigned int x, int n)
10{
11	if (n == 0)
12		return x;
13	else if (n < 0)
14		return rrotate((x << 1) | (!!(UINT_TOP_BIT & x)), n + 1);
15	else
16		return rrotate((x >> 1) | (UINT_TOP_BIT * (x & 0x1u)), n - 1);
17}
18
19unsigned int lrotate(unsigned int x, int n)
20{
21	if (n < -INT_MAX)
22		return rrotate((x >> 1) | (UINT_TOP_BIT * (x & 0x1u)), -(n + 1));
23	return rrotate(x, -n);
24}

投稿2017/08/26 14:33

編集2017/08/27 04:24

raccy

総合スコア21735

kamecha

2017/08/26 23:43

１ビットずつずらす版のコードで rrotate関数の戻り値にrrotateがありますが、これはどういうことなのでしょうか（ｃ言語の初心者なので・・・）

raccy

2017/08/27 00:01

再帰呼び出しと言われる方法です。関数の中で自分自身を再度呼び出します。数学の漸化式のように一つ前や一つ後を次々呼び出すことでループの代わりにすることができます。「xを右にnビットずらした値」は「xを右に1ビットずらした値をn-1ビットずらした値」になります。そうやって「xを右に1ビットずらした値を右に1ビットずらした値を右に1ビットずらした値を...(n回繰りかえし)を右に0ビットずらした(つまり何もしない)値」を求めることにでき、ほしかった値が得られます。負の場合は逆方向になるだけで、同じく0に辿り着きます。このような関数では、自分の中で関数を何度も何度も入れ子で呼び出すことになります、単純に処理をした場合はn回の関数呼び出しが存在することになります。しかし、呼び出しの入れ子の段数には限界があり、あまり多すぎるとスタックオーバーフローと呼ばれるエラーが発生して、プログラムが停止します。ですが、上のプログラムはきちんと最適化すればスタックオーバーフローはおきません。なぜなら、一定の条件(末尾呼び出しと言われるパターン)を満たす再帰関数はループとして書き直すことができるため、コンパイラがループとして処理するようにコンパイルしてくれるからです。詳しくは「再帰呼び出し」で検索してみてください。最適化については「末尾再帰最適化」で検索すると解説サイトが見られると思います。

kamecha

2017/08/27 03:35

丁寧な解説ありがとうございます。あと、気になったのですが、0x1とは、何を意味しているのですか？

raccy

2017/08/27 04:28

0x1は16進数表記です。整数値というより00000000000000000000000000000001というビット列だというのが意識できるようにするために区別して書いています。ただ、よくみたら、uつけてunsigned intに強制するのを忘れてました。

kamecha

2017/08/27 12:57

なるほど。度々すみませんが、(UINT_TOP_BIT * (x & 0x1u))はどういう働きをしているのですか？特に＊は、最上位ビットのみが１のビットと、入力値と最下位ビットのみが１のビットとの論理積をかける、ということですか？

raccy

2017/08/27 14:09

本当は (x & 0x1u) ? UINT_TOP_BIT : 0 と書こうとしたんですけど、0か1なら、そのままかけた方がはやくないかなとそうなってしまいました。 !!(UINT_TOP_BIT & x) も (UINT_TOP_BIT & x) ? 1 : 0 と丁寧に書いた方が良かったような気がします。

kamecha

2017/08/27 22:09

条件式を使用すると、いうことなんですね！ありがとうございます。様々な方の解説をまとめた感じがして分かりやすかったです。

行動規範の内容に同意します

あなたの回答