ビットをローテートするプログラムの解説をお願いします。（C言語）

質問

下記のプログラムは、rotate() を呼び出されるたびに１つずつ左にビットをローテートするものです。

#include <stdio.h>

void rotate(unsigned char *c);

int main(void)
{
unsigned char ch;
int i;

ch = 1;

for(i=0; i<16; i++) {
rotate(&ch);
printf("%u\n", ch);
}

return 0;
}

void rotate(unsigned char *c)
{
union {
unsigned char ch[2];
unsigned u;
} rot;

rot.u = 0; /* 16ビットをクリア */

rot.ch[0] = *c;

/* 整数を左にシフト */
rot.u = rot.u << 1;

/* ビットがc[1]にシフトしたかどうか確認する。
シフトしていれば、OR演算を実行して他方の端に戻る
*/
if(rot.ch[1]) rot.ch[0] = rot.ch[0] | 1;

*c = rot.ch[0];
}

【質問】
自分で考えてみたので、間違いがあれば、ご指摘お願いします。
---------------------------------------------------------
ch = 1; だから rotate(&ch); で初回実行時に *c に1を渡す。
i=0 のとき、

rot.ch[0]　　rot.ch[1]
0000 0000　　0000 0000　　　　rot.u = 0;
　　　　rot.u

0000 0001　　0000 0000　　　　rot.ch[0] = *c; *c は 1

0000 0010　　0000 0000　　　　rot.u = rot.u << 1;

if(rot.ch[1])　→　偽

*c = rot.ch[0]; で *c が 0000 0010 すなわち 2 になる。
printf文で「2」を表示。
---------------------------------------------------------
i=1 のとき、

rot.ch[0]　　rot.ch[1]
0000 0000　　0000 0000　　　　rot.u = 0;
　　　　rot.u

0000 0010　　0000 0000　　　　rot.ch[0] = *c; *c は 2

0000 0100　　0000 0000　　　　rot.u = rot.u << 1;

if(rot.ch[1])　→　偽

*c = rot.ch[0]; で *c が 0000 0100 すなわち 4 になる。
printf文で「4」を表示。
---------------------------------------------------------
i=2 のとき、rot.ch[0] が 0000 1000 で *c が 8 になる。
printf文で「8」を表示。
i=3 のとき、rot.ch[0] が 0001 0000 で *c が 16 になる。
printf文で「16」を表示。
i=4 のとき、rot.ch[0] が 0010 0000 で *c が 32 になる。
printf文で「32」を表示。
i=5 のとき、rot.ch[0] が 0100 0000 で *c が 64 になる。
printf文で「64」を表示。
i=6 のとき、rot.ch[0] が 1000 0000 で *c が 128 になる。
printf文で「128」を表示。
---------------------------------------------------------
i=7 のとき、

【ここからがどうしても分かりません。どうか力をかして頂けないでしょうか？お願いします。】

回答No.7

Oh-Orange · ベストアンサー

★回答者 No.1 です。
＞ただ、わかりやすく並び替えただけですね！
　↑
　はい、その通りです。
　一般に配列は左から右に配置するイメージで考えますが、場合によっては逆の右から左に
　配置するイメージで考えることもあります。この場合は配列の処理内容によって変わります。
・今回は共用体のお勉強ですよね。
　去年も全く同じ質問がありました。
　共用体を使ってローテーションするもので何かの本に載っているのですよね。
　普通、１バイトのビットのローテーションは回答者No.5(jacta)さんのように記述します。
　今回は共用体の仕組みを理解するためのローテーションにも使えると本に書かれていただけです。
　実際にはエンディアンが絡んでくるので共用体よりもビットシフト、ビットORを組み合わせます。
・ちなみに共用体を使えばlong型の上位16ビット、下位16ビットを取り出すことも可能です。

　共用体を次のようにします。
　union {
　　unsigned short s[ 2 ];
　　unsigned long v;
　} x;

　x.v = 0x12345678;…代入
　x.s[0]=0x5678…下位16ビット
　x.s[1]=0x1234…上位16ビット
　となります。

・また、構造体と組み合わせるともっと分かりやすくなります。
　union {
　　struct {
　　　unsigned short lo;
　　　unsigned short hi;
　　} s;
　　unsigned long v;
　} x;

　x.v = 0x12345678;…代入
　x.s.lo=0x5678…下位16ビット
　x.s.hi=0x1234…上位16ビット
　となります。

まとめ:
・リトル・エンディアンでは
　union {
　　struct {
　　　unsigned char a;…下位ビット
　　　unsigned char b;
　　　unsigned char c;
　　　unsigned char d;…上位ビット
　　} s;
　　unsigned long v;
　} x;

　x.v=0x12345678;
　x.s.a=0x78
　x.s.b=0x56
　x.s.c=0x34
　x.s.d=0x12
　となります。
・以上。

お礼

２度も回答ありがとうございます！
検索したら、同じ質問をしている人がいました。
もう少し、調べてから質問した方が良かったのかもしれません。ごめんなさい！
質問したローテーションするプログラムは『独習C 第3版』に記載されているものです。
コードのサンプル、今後の参考にさせて頂きます！！
いろいろ勉強になりました！！
回答本当にありがとうございました。

回答No.6

nak777r

>int型はIntel系CPUを意識して、「16または32」としたんでしょうか？

int と Intel系はまったく関係ありません

short は short int の略で、2byte の整数
long は long int の略で、4byte の整数

int は、short int 又は long int の略された部分の文字で、
integer の略、和訳すると単なる「整数」の意味になります

ですので、int と記述した場合、short int と解釈するのか、
long int と解釈するのかは、コンパイラによるわけです

通常は、コンピュータの演算が楽な方を、コンパイラを作成
しているメーカーが採用していたので、DOSの時代（8bit、
16 bit CPU主流の時代）は、int = short 解釈が多かったの
ですが

32bit CPUが主流の現在では、逆に long の方が処理しやすい為、
int = long 解釈のコンパイラが多くなってます

お礼

疑問に対する回答ありがとうございます！！
int は、short int 又は long int の略された部分の文字なんですね！
そしてコンパイラによってintの長さが決まるから「16または32」なんですね！
勉強に使っている本を読み直したら、
「short intはintより短く、long intはintより長くなるのが普通です。たとえば、ほとんどの16ビット環境では、intは16ビット長で、long intは32ビット長です。ただし、longとshortの厳密な意味は処理系に依存します。(中略)。事実、ほとんどの16ビット環境では、intもshort intも同じサイズとして扱われます。さらに、多くの32ビット環境ではintとlong intのサイズが同じです。」
と記載されていました！！
何回も回答本当にありがとうございました。

回答No.5

jacta

質問に対する回答というわけではありませんが...

なぜ共用体を使ったりして、こんな面倒なことをしなければならないのか謎です。

void rotate(unsigned char *c)
{
　*c = (unsigned char)(*c << 1 | *c >> (CHAR_BIT - 1));
}

で済んでしまうのではないでしょうか？
敢えて分かりにくくしているような気がします。

お礼

回答ありがとうございます！
このプログラムは『独習C 第3版』にシフト演算子の練習問題として載っている、
「Cにはローテート(rotate)演算子はありません。ローテートはシフトに似ていますが、はみ出たビットを逆の端に置きます。(中略)。呼び出されるたびに１つずつ左にローテートするrotate()という関数と、それを利用するプログラムを作成してください。」
という問題の解答の例として載っているものです。
問題文にはヒントとして、
「バイトの端からはみ出たビットにアクセスするには、共用体を使用します。」
とあるため、解答例にも共用体が使用されています。

ご指摘の通り、「CHAR_BIT」を使うために #include <limits.h> を追加して、

void rotate(unsigned char *c)
{
*c = (unsigned char)(*c << 1 | *c >> (CHAR_BIT - 1));
}

とした方が簡単でした！！ありがとうございます！！

回答No.4

nak777r

説明が少し不十分だったので補足します

short b;
と型宣言した場合、プログラムは、メモリ上に２バイト分のメモリ領域を確保します

long c;
と型宣言した場合、プログラムは、メモリ上に４バイト分のメモリ領域を確保します

b=0x1234;
と記述した場合、
プログラムは、確保されたメモリに、 [0x34][0x12]と格納します

c=0x12345678;
と記述した場合、
プログラムは、確保されたメモリに、 [0x78][0x56][0x34][0x12]と格納します

上記の様にメモリに値を保存するのが、リトルエンディアン と呼ばれる方式で
Intel系のCPUでは、これを採用しています

逆にビッグエンディアンと呼ばれる方式の場合、
b=0x1234;
と記述した場合、[0x12][0x34]と格納します

c=0x12345678;
と記述した場合、[0x12][0x34][0x56][0x78]と格納します

union は同じメモリの領域を参照するので、、、後は先の説明の通りです。

お礼

補足ありがとうございます！！
ちょっと、理解に不安が残っているので、
エンディアンがどういうものなのか自分で調べてみたいと思います。
回答本当にありがとうございました。

回答No.3

luckymako

実行している環境がわからないので
　int型 2 Byte
　char型 1 Byte
　リトルエンディアンマシン
と仮定します。

ビックエンディアンマシンだと正常に動かないと思われます。

まず union の確認から
union は一つの領域を複数名で参照するための物です(共用体)。

よって、提示されたプログラムが正しく動くのであれば
u に 1 を代入するとメモリ上には

　|ch[0]---|ch[1]---|　名前1
　|00000001|00000000|　メモリ上のビット列
　|u_下位--|u_上位--|　名前2

のように格納されているはずです。
(リトルエンディアンマシンでは上位バイトと下位バイトが逆順になります。)
ビット列の遷移を見てみると
　|00000001|00000000| 0 回ローテート
　|00000010|00000000| 1 回ローテート
　　・・・
　|01000000|00000000| 6 回ローテート
　|10000000|00000000| 7 回ローテート
　|00000000|00000001| 8 回ローテート
　　↓
　|00000001|00000001| 論理和の結果

8 回目のローテートで u の上位バイトつまり ch[1] にビットが立ちます。
7 回目までは
　ch[1] = 0 で
8 回目で
　ch[1] = 1 となり
ch[1] が 非0 なので ifの条件が 真 となり ch[0] と 1 の論理和が ch[0] に代入されます。
rotate は ch[0] の中身のみ ( |00000001| ) を返しているので 8 回目以降は 0 回と同じことの繰り返しになります。

つまり
i=7 のとき、rot.ch[0] が 0000 0001 で *c が 1 になる。
printf文で「1」を表示。

i=8 のとき、rot.ch[0] が 0000 0010 で *c が 2 になる。
printf文で「2」を表示。

お礼

回答ありがとうございます！！
リトル・エンディアンマシンでは上位バイトと下位バイトが逆順になるんですか…ややこしいですね…
エンディアンについて詳しく載っている書籍とかないものですかね…
ちょっと頭がパニックになっています。
回答ありがとうございました。

回答No.2

nak777r

union {
unsigned char ch[2];
unsigned u;
} rot;

問題のプログラムは、int = 16Bit で Intel系のCPUでないと
まともに動かないプログラムなので、あまりよいプログラムとは
いえないですね

32Bit CPU時代のコンパイラで実行するのなら
unsigned u は、unsigned short u に直してください

union でくくられた u と ch[0] はメモリ上同じ領域に確保されます
Intel系は LOW ワード、HIワードの順に確保されているので、

rot.u = 256; とした場合
rot.ch[0]　　rot.ch[1]
0000 0000　　0000 0001
となります

お礼

回答ありがとうございます！！
int=16Bit で Intel系のCPUでないとまともに動かないんですか…
私の使っている本には、

[型]　　　　　　　　[典型的なビット長]
int　　　　　　　　　　16または32
unsigned short int　　　　　16

とあるんですが、int型はIntel系CPUを意識して、「16または32」としたんでしょうか？
unsigned short int は 16 でちょうどいいですね。

回答No.1

Oh-Orange

★共用体を理解していないだけです。
＞rot.ch[0]　　rot.ch[1]
　↑
　こう考えるから分かりづらいのです。
　書き方を
　rot.ch[1]　　rot.ch[0]
　と書けば分かりやすくなりませんか？
　つまり
　rot.ch[1]　rot.ch[0]
　0000 0000　0000 0001　i=0
　0000 0000　0000 0010　i=1
　0000 0000　0000 0100　i=2
　0000 0000　0000 1000　i=3
　0000 0000　0001 0000　i=4
　0000 0000　0010 0000　i=5
　0000 0000　0100 0000　i=6
　0000 0000　1000 0000　i=7
　0000 0001　0000 0000　i=8　←注目
　↑
　ch[1]にシフトします。
　このとき if ( rot.ch[1] )→真 となります。
　その後に rot.ch[0] = rot.ch[0] | 1; を演算することでローテーションします。
・あと共用体を使う場合は処理系によってエンディアンが違うことがあるため注意して下さい。
　もしもビッグ・エンディアンだと rot.ch[0] = *c; と代入しても rot.u が 0x0001 とならず
　0x0100 になってしまい正しくローテーションで来ません。
　処理系がリトル・エンディアンなら正しくローテーションできるでしょうね。
・以上。

お礼

回答ありがとうございます！！！
ビットの並び(右から左)に対して、配列の並びが左から右だから、逆だったんですね！
リトル・エンディアンとビッグ・エンディアンですか…
私のコンピュータはIntelのx86系CPUだからリトル・エンディアンですね？
今後、共用体を使う際には、そのことも頭に入れておきたいと思います。

補足

お礼の訂正。
>ビットの並び(右から左)に対して、配列の並びが左から右だから、逆だったんですね！
書き方によっては一概に言えないですね(ANo.3の書き方とか)。
ただ、わかりやすく並び替えただけですね！