[techaday:0001] C言語での符号とビットシフトについて

[techaday:0001] C言語での符号とビットシフトについて

はじめに

「1日1技シリーズ(別名techadayも併用することにします)」記念すべき第1回は,整数型の符号とビットシフトに関する話題です.
ビット演算は特にマイコンプログラミング等において,IOを使用するためだけでなく高速化やメモリ節約のためにも頻繁に使用されます.
今回と次回はそんなビット演算について,知らないとハマりやすいポイントについて書いていきます.

前提知識

  • C言語の基礎的文法がわかる
  • ビット演算についてイメージできる

効能

  • signed な整数型変数と unsigned な整数型変数でのビットシフトの処理の違いがわかる
  • 異なる処理をわざわざ行う理由が分かる
  • unsigned char と書くべきところをうっかり char と書いて闇に落ちてしまうのを防止できるようになる

動機

突然ですが問題です.
以下のコードを実行した時に,変数 poyo の値は2進数でどうなるでしょうか?

char hoge = (1<<7) | (1<<3);
char poyo = (hoge >> 4) | 0x80;

答えはこちら

どうでしょうか?予想したものと答えは合ってましたか?合ってた人はあんまりこの記事を読む必要はないかもしれません.
間違ってしまった人はぜひ読んでください.さもなくばいつか闇にハマることになるでしょう…

符号付き整数と符号なし整数

C言語に限らず,プログラミング言語の入門書を開いてみると,比較的早い段階から型の話が出てくると思います.
私は初めてこの概念に触れた際に,なぜ整数は整数でも符号なし(非負)の整数と符号付きの整数とに分けて考える必要があるのだろうかと疑問に思いました.どっちも同じ整数なのに.
ほかにも型の説明については short intlong intlong long int とが存在するのはなぜかとか…当時いろいろと疑問は尽きなかったのですが,今回の話題にはあまり関係ないので閑話休題.

今回はC言語についてというタイトルですが,これから説明する点については,ほとんどの場合はほかの言語でも同じだと思います.説明にあたって楽なのでC言語を選んでいるに過ぎません.
また,エンディアンの話に触れるとややこしくなるので,この記事では8bitの整数について議論していきます(気になる人は最後にある参考ページを参照してください).

まず,C言語での符号の扱いについて復習しておきましょう.

修飾子 説明
signed 符号付き
unsigned 符号なし

これを頭につけた整数型の変数,例えば

unsigned char hoge;

とすれば 符号なし 8bit の整数型変数 hoge を定義できます.

整数型の変数がメモリ上にどのように格納されているかについてもイメージする必要があります.
符号なしの場合は2進数による表現そのままで格納されています.すなわち, unsigned char a = 34; のときは, $$34 = 2^1 + 2^5$$ ですから,

(7) (6) (5) (4) (3) (2) (1) (0)
0 0 1 0 0 0 1 0

といった具合に格納されています.

一方で,符号付き整数の場合は少し違った格納のされ方をしています.signed char b = -34; の場合を見てみると,

(7) (6) (5) (4) (3) (2) (1) (0)
1 1 0 1 1 1 1 0

となっています(ほんまかよと思う人はこれをみてください).
なぜこのような形式で入っているのでしょうか?この点については後述することにして,その前にビットシフト演算についておさらいしておきましょう.

ビットシフト

ビットシフトは,数種類あるビット演算の中でもなかなか感動的な発明だと思います.
他のビット演算ではビットごとの,ビット同士の演算を行うのに対して,ビットシフトはビット列に対する操作を行うからです.
そういう意味で,ビットシフトはビット演算であってビット演算でないような微妙な存在です.またしても閑話休題.

さて,すでにご存知とは思いますが,ビットシフトには2種類あります.右ビットシフトと左ビットシフトです.
右ビットシフトは,その名の通り指定した個数だけビットを右に移動させます.
左ビットシフトはこれとは逆に左向きにビットを移動させます.
で,説明としては終了にしたいのですが,一応何が起こるのか模式的に書いておきます.

符号なし整数型の場合

例えば先述の符号なし整数 a に対して,右ビットシフトを

unsigned char c = a >> 2;

のように行うと,

(7) (6) (5) (4) (3) (2) (1) (0)
a 0 0 1 0 0 0 1 0
c 0 0 0 0 1 0 0 0

となり,結果の数値は 8 になります.ずらすことでもともと右の方にいたビットがあふれて切り捨てられ,空いた左のビットには0が埋められていることがわかります.
左ビットシフトの場合は,左の方にいるビットがあふれて切り捨てられ,右に0がつきます.説明は省きます.
計算結果をいろいろ見てみると,シフトするビットの数を \(n\) とすると,右ビットシフトは \(2^n\) での除算(小数点以下切り捨て),左ビットシフトは \(2^n\) との乗算になっていることがわかります.

符号あり整数型の場合

さて,ここまでの話は符号なしの整数に対する話でした.符号ありの場合はどうなるのでしょうか.実際に実行した際の結果を示します.

signed char d = b >> 2;
(7) (6) (5) (4) (3) (2) (1) (0)
b 1 1 0 1 1 1 1 0
d 1 1 1 1 0 1 1 1

となり,符号なしの場合と処理が異なることがわかります.なぜこのようなことが行われるのでしょうか?
これには,負の数を合理的に取り扱うための大人の事情,もとい,CPUのハードウェア的な事情が深く関係しています.

2の補数と負の整数の演算

ビット列で負の整数を表現する際に使われているのが2の補数という考え方です.
イメージとしては,ある数 \(x\) があったときに,考えるビットの範囲(例えば今回の場合8bit)で \(x + y = 0\) となるような \(y\) を \(-x\) として利用するというものです.

例えば,先述の 34 と -34 の場合,繰り上がりに気をつけて足し算を行うと

(8) (7) (6) (5) (4) (3) (2) (1) (0)
0 0 1 0 0 0 1 0
+) 1 1 0 1 1 1 1 0
(1) 0 0 0 0 0 0 0 0

のようになって,8bitの範囲 (0〜7) を見るとすべてのビットが 0 なので,値としては 0 となります.
勘のいい人は気づいているかもしれませんが,2の補数はビットを反転した値に1を足したものになります.
このように負の整数を表現するとき,7bit目は必ず1になります.このビットのことを符号ビットと呼ぶこともあります.

では負の整数どうしの演算はどうなるのでしょうか?試しに -34 どうしを足して2倍にしてみましょう

(8) (7) (6) (5) (4) (3) (2) (1) (0)
1 1 0 1 1 1 1 0
+) 1 1 0 1 1 1 1 0
(1) 1 0 1 1 1 1 0 0

ところで,2倍するというのは左に1ビットシフトするのと等価でした.結果を見るとそうなっていることがよくわかりますね.
値も確かに -68 になっています(結果の値の補数をとってみると簡単にわかります).

ということは,右ビットシフトにも対応関係があると嬉しいですね.すなわち, -34 の補数表現と -17 の補数表現に上記のような関係があれば嬉しいわけです.
まずはシンプルに右ビットシフトしてみましょう.

(7) (6) (5) (4) (3) (2) (1) (0)
1 1 0 1 1 1 1 0
? 1 1 0 1 1 1 1

あれっ,7bit目はどうすればよいのでしょうか?符号ビットを0にしたら正の数になってしまいますね.つじつま合わせにここを1にしましょう.

(7) (6) (5) (4) (3) (2) (1) (0)
1 1 1 0 1 1 1 1

これを10進数になおしてみましょう.補数の補数は元の数になりますから,ビット反転して1を足すと-1をかけた値になります.補数をとると,

(7) (6) (5) (4) (3) (2) (1) (0)
0 0 0 1 0 0 0 1

この値は10進数で17ですから,すなわち-17となります.ここで,なるほど右ビットシフトというのは単純なシフトによって空いた上位ビットに符号ビットをどんどんくっつけていく処理なんだと考えられます.
つまり,負の数を1ビットずつどんどん右シフトしていくと次のようになります.

(7) (6) (5) (4) (3) (2) (1) (0)
1 1 0 1 1 1 1 0
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1

このようにすることですべてが綺麗におさまります(すごい).

このようなビットシフトのことを算術ビットシフトと呼びます.
これに対して,シフトによって空いたビットを0で埋めるビットシフト(符号なしの場合ですね)を論理ビットシフトと呼んで区別します.

まとめ

  • 算術ビットシフトと論理ビットシフトの違いについて述べ,符号の有無によってそれぞれが適用されることを示した.
  • CPUでの負の整数の取り扱い方として,補数の考え方を用いると加減算とビットシフトが綺麗に解決することを示した.

補足

符号ビットが繰り上がって0になることはないのか?

8bit符号付き整数で表現できる範囲(-128〜127)で演算をする限りは起こりません.\(-64+(-64)\) をビット演算でやって確かめてみてください.

私の環境だとchar型がもともとunsignedみたいなんだけど?

Makefile等があるなら,コンパイラオプションを見てみてください.たぶん -funsigned-char がいます.
C Dialect Options - Using the GNU Compiler Collection (GCC)

参考