ビット演算

プログラマーからひとこと

この章では、「ビット演算えんざん」というものをおぼえます。
前にちらっと出てきましたね。
その時は、むずかしいので説明はしませんでした。
そうです、ビット演算はむずかしいのです。
あんまりむずかしいので、飛ばして読んでもいいです。ほら、ここにボタンも用意しましたよ。とばし読み

これまでもむずかしい話はいろいろしました。どれもむずかしいかわりに、かならず必要なものでしたから、それはいいと思うんです。
配列変数なんて、かなりめんどくさかったですが、ないと困るものでしたよね。
ところがビット演算は使わないでも、まあなんとかなるんです。
私もはじめにおぼえたときは、「なくていいじゃん」と思いました。
どうです、とばし読みしたくなってきたでしょう。

じゃあ何のためにおぼえるの? いくつか理由はあります。

1.コンピューターの考え方がわかる
私たちがものを考えるとき、だいたいイメージとか日本語でものを考えるように、コンピューターは「ビット」でものを考えます。
つまり、ビットの考え方を理解すると、ぐっとコンピューターの考え方に近づけると言えるでしょう。
こう言われてヤル気が出てきた人は、わりとプログラマー向きな性格だと思います。
ぶっちゃけ、コンピューターの考え方がわかってもモテませんよ。そんなに役に立たないですよ。

2.短いプログラムが書ける
ビット演算をうまく使うと、IF文を何行も使うようなプログラムも1行でぐっとシンプルに書けるようになります。
これはアツいですね。と、私は思いますが、それは私がプログラマーだからかもしれません。
プログラマー的にはシンプルにスパッと書けるとプロっぽくてうれしいものですが、でもちょっとくらいプログラム長くたって別にいいじゃん、と言われると、まあ、それもそうだな、なんて気もします。

3.速いプログラムが書ける
コンピューターは「ビット」でものを考える、とさっき書きました。
ビット演算はビットを使ったプログラムなので、コンピューター的にはラクっていうか、やりやすいものみたいです。
おおざっぱに言って、ビット演算を使ったプログラムと、同じことをビット演算を使わずにやったプログラムでは、ビット演算した方が速くなります。
よくゲームで「処理落ち」とか「重い」とか言うでしょ。アレが少なくなります。
もっとも、この講座で教えているレベルだと、違いがまったくわからないていどの速さだったりもします。高レベルなプログラムになるほど必要になってくるんですが、いま必要かっていうと別にそうでもないんですね。

4.人のプログラムが読みやすくなる
けっきょく一番だいじなのは、ここかもしれません。
ビット演算を使ってるプログラムは、ビット演算の考え方を知らないと、何が書いてあるのかよくわかりません。
そして参考にしたいプログラムにかぎって、ビット演算を使ってるのです。これはプログラムあるあるです。
おおむねすぐれたプログラマーというのは、コンピューターが好きで、短くて速く動くプログラムを書きたがるものです。つまりビット演算をしたがるものなのです。
すぐれたプログラマーが書いたプログラムを読むのはとても勉強になりますが、書いてあることがわからないとあまり勉強になりません。そこでビット演算の初歩だけでもおぼえておくといい、というわけです。

どうです? ビット演算を知りたくなってきましたか?
やっぱりそうでもないですか?
その気持ちもとてもよくわかるので、ここにボタンがあるのです。とばし読み
まあ、今までの話をきいて、じゃあおぼえてみるか、と思った人だけが読むくらいのサジかげんでちょうどいいような気がします。

2進数

ワンパク
いいかげんにしろ! あれだけムズかしいとかスグには役に立たねェとか言われたアトじゃ、そうそうヤル気は起きねーぞ……

インテリ
ではビット演算のキソから始めようか! ワクワクするよね!

ワンパク
コ……コイツ、ものすげえタフか、それともオレのハナシをきいてねェのか……。

神崎
どっちにしてもダメージを受けそうだから、スナオに話にのっておこうか。

インテリ
ビット演算をリカイするには、その前に「2進数」のことを知らないといけないね。

神崎
2進数?

インテリ
ボクらがふだんイシキせずに使ってる数字は、「10進数」でできているんだ。これがコンピューターだと、2進数になるんだね。

ワンパク
それにしちゃ、今までBASICでフツーに数字を使ってなかったか? アレも2進数ってやつなのか?

インテリ
BASICではふつう、ボクらにもわかりやすいように10進数しか出てこないんだ。ボクらの目に見えないだけで、コンピューターの中では2進数で動いているんだよ。

神崎
そうか……わざわざオボエなくていいっていうのは、そういうトコロなのかあ。10進数と2進数はどう違うの?

インテリ
ボクらの10進数では、0・1・2・3・4・5・6・7・8・9の10コの数字の組み合わせで数をつくるよね。これが2進数だと、「0」と「1」の2コの数字しか使わないんだ。

ワンパク
エ、……ハァ!? それじゃモノを数えられねェだろ!

インテリ
そうでもないんだな。
ここからは、区別しやすいよう2進数には線を引いておくよ。
たとえば10進数で「0」「1」の次は「2」だよね。
2進数だと、「」「」の次は「10」になるんだ。

ワンパク
ジ、10だと!?

インテリ
2進数だと10と書いて「イチゼロ」とか読む方がいいんだけど……

神崎
うーん……急にチシキをつめこまれてる気がしないでもないぞ。

インテリ
もうちょっとユックリいこうか。
10進数では、使える10コの数字の中で一番大きいのは「9」だよね。9より大きい数を書くときはどうするかな?

ワンパク
そりゃトウゼン、1ケタくらいが上がって「10」だゼ! ……ン? 10?

インテリ
そう、2進数も同じようなものなのさ。

神崎
ええと、2進数だと使える2コの数字の中で一番大きいのは「」。それより大きい数を書くときは……

ワンパク
位が上がって、「10」になるワケか!

インテリ
そういうコト。このルールだけオボエれば、2進数はカンペキさ。

神崎
ホント!? うーん、10の次は1ケタ目が上がるから、11。その次は、もう上げられる位が残ってないから、位上がりして100……。

ワンパク
オイオイ、とんでもねえハイペースでケタが上がってるぞ! ホントにコレで合ってるのか?

インテリ
バッチリだよ! 0〜10までを数えた表がコレになるね。
10進数2進数
10
11
100
101
110
111
1000
1001
101010
こんなカンジで、どんどんケタが上がるから、1010と書いて「イチマルイチマル」とか読むんだね。

ワンパク
フーム……じゃあ10進数で「1976」は、2進数だとどうなるんだ?

インテリ
……。

神崎
……。

インテリ
Google検索してみようか!

ワンパク
ナンだソレ! ググんのかよ!

神崎
しかも、本当にそれで答が出るんだ!

インテリ
まあ、2進数をいちいち手で計算するのはタイヘンだからね。検索とかアプリで出すのがフツウなのさ。

ワンパク
「1976 = 0b11110111000」か……。この「0b」ってのはナンだ?

インテリ
10進数と区別するための記号だね。1976をただ2進数で言えば11110111000だけど、これだと10進数の「111億1千11万1千」にも見えるから、アタマに0bと付けるのがマナーってことかな。

神崎
だいたいわかってきたけど、それにしてもメンドくさい数え方だね……。

インテリ
もともとコンピューターはスイッチがONオンOFFオフかの組み合わせで作られたからねえ。この2つの組み合わせを「ビット」と言うんだ。

神崎
ん……ビット?

ワンパク
ワスれるトコだったぜ、アブねえ! 「ビット演算」のハナシはドコ行ったんだ?


初歩のビット演算

インテリ
それじゃあ、プチコンで使うビット演算のサンプルを見てもらおうか。
A=5 AND 3
は変数だね。これをRUNすると、変数が入るよ!

ワンパク
ハ、ハァ!?

神崎
ANDっていうから、てっきり5+3みたいなコトかと思ったけど……

インテリ
5 AND 3はそういう計算とはちがうモノだってオボエておこうね。
答だけ見ても何だかわからないだろうから、トチュウの計算式も見てみよう!
    101
AND 011
  = 001


神崎
えーと……

ワンパク
なんだコレ! ワカるフンイキがまったくねェぞ! 5 AND 3のドコからこの式になるってんだ!

神崎
いやいや、たぶん2進数がここで出てくるんだよね……。

インテリ
そのとおり。を2進数にすると101を2進数にすると011になるね。

ワンパク
……3を2進数にすると11じゃなかったか?

インテリ
アタマにつけるゼロは、いくらつけてもいいんだ。101と位をそろえるために、1コつけておいたよ。

ワンパク
ウーム……つまり、5 AND 3で、
    101
AND 011

ココまではまあワカッたぜ。だがコタエが001ってのは、ナットクいかねェな!

インテリ
習ったことのない計算だから、そう思うのもトウゼンだね。
ビット演算の「AND」では、「両方ともになっている位だけになる」とオボエると……カンタン……かなあ?

神崎
……かなあ?

ワンパク
ダレもナットクいってねェじゃねえか!

神崎
うーん。「位」がポイントなんだよね。たとえば1ケタ目は……
    10
AND 01

両方とも「」になっている位……だから……
    10
AND 01
  = ??

答も1になるってコト?

インテリ
いいよ! そこまでワカれば、あともカンタンなハズ!

ワンパク
つまり2ケタ目も、こういうコトか?
    
AND 
  = 

コレはかたっぽが「」、もうかたっぽは「」だから、
    
AND 
  = 

ゼロがくるワケか?

インテリ
そのとおり! 3ケタ目はもうわかるよね。
    01
AND 11
  = 01

これで001までは答が出たね。

神崎
その001は2進数だから、10進数に直すと……

ワンパク
が変数に入るってコトか。

インテリ
計算のしかたさえワカれば、あんがいラクだろう。たとえばB=7 AND 11だとどうなるかな?

ワンパク
ツギツギに出してきやがって! まあヤリ方はワカッてるぜ。まず2進数に変えるんだろ?
7は111、11は1011だから、こうなるゼ!
    0111
AND 1011
  = ????


神崎
で、「両方ともになっている位」をさがすと……
    01
AND 10
  = ??

1ケタ目と2ケタ目がそうだから「」にして、のこりは「」だから……

インテリ
答はこうなるね。
    0111
AND 1011
  = 0011

0011、つまり10進数で言いかえるとが変数に入ることになるね。どうだい、思ったよりはカンタンだろう?

ワンパク
やり方ドオリにやれば、まあデキねえコトはねェが……トンデモなくメンドくせェぜ!

インテリ
ANDのほかにも、「OR」や「XOR」の計算もあるんだけど……

ワンパク
ウオォー! メンドくせェー!!


ハカセ ORとXOR、NOTのビット演算

ワンパク君、すっかりOverflowエラーというトコロじゃな。
などとBASICネタもクールに使いこなすワシじゃ、ハカセじゃ。ビット演算の「OR」も「XOR」も「AND」とあまり変わらんぞい。ものはためしじゃ、ジッサイの計算式を見てもらおうかの。
OR
   0101
OR 0011
 = 0111

ワカるかの? 「どちらか片方でもがある位はになる」のがORオアの計算じゃ。
XOR
    0101
XOR 0011
  = 0110

XORじゃと、「両方ともになっている位はになり、片方にだけがある位はになる」わけじゃ。ちょっとヤヤコシイのう。
そうそう、「XOR」は「exclusive OR」略して「エクスオア」とか「エックスオア」などと読むのじゃぞ。伝説の剣かなんかの名前っぽくてカッコイイわい。
NOT
NOT 1101
  = 0010

NOTノットはちょっとトクシュじゃな。2つの数をくらべたりせず、ただがひっくり返るのがNOTじゃよ。

ビット演算の実例

ワンパク
ゼェ、ゼェ……。アタマがワレそうだぜ……。

神崎
ひととおりオボエたけれど、けっきょくコレって何につかうの?

インテリ
たしかに、何の役に立つのかわからないとハリアイがないよね。
じゃあ、ちょっと前に出てきたこのプログラムをおぼえてるかな?
0056#. B=BUTTON()
0058#. IF B AND 1 THEN BEEP 52
0059#. IF B AND 2 THEN BEEP 53
0060#. IF B AND 4 THEN BEEP 62
0061#. IF B AND 8 THEN BEEP 25

神崎
たしかサンプルプログラム3で出てきたね。
BUTTON()命令とIF文の組み合わせで、十字ボタンの押された方向を調べるんだったっけ。

インテリ
IF B AND 1」と書くと、「Bの中に1がまじっている」というイミになると習ったよね。

ワンパク
十字ボタンの右上が押されたら、変数に入る数字は1+8で……。で、「IF B AND 1」や「IF B AND 8」と書くと、なぜかBのナカミがでもアタリになるって話だったな……。
あらためて考えると、ワケがわからねェぜ!

神崎
あれ、だけどこのB AND 1って、ビット演算の書き方じゃないかな?

インテリ
そのとおり! もう1度、このIF文をビット演算の考え方で見てみると、イミがわかってくると思うよ。

ワンパク
チクショウ、またビット演算すんのかよ!
まず右上が押されて変数が入ったとするだろ……で、58行目がIF B AND 1 THEN……。
これは変数のナカミを考えると、IF 9 AND 1 THENってコトだよな。

神崎
9 AND 1は、こう計算するんだったよね。
    1001
AND 0001
  = 0001

答は0001、10進数に直すと「」になるね。

ワンパク
じゃあ次の59行は……IF B AND 2 THENだから、9 AND 2をビット演算すると……
    1001
AND 0010
  = 0000

オ、オォ!? キレイにゼロになったぜ。

インテリ
だんだんカラクリが見えてきたね。「B AND 4」を調べる60行だと、
    1001
AND 0100
  = 0000

やっぱりゼロ。
B AND 8」を調べる61行なら、
    1001
AND 1000
  = 1000

これを10進数に直すと「」になるね。

ワンパク
下方向(AND 2)も左方向(AND 4)もビット演算のケッカはゼロ……。上(AND 1)や右(AND 8)だと、ゼロにはならねェんだな。

インテリ
ソコだね!
ちょっと話がそれるようだけど、IF (変数) THENというカタチのIF文は、「変数がゼロじゃなければ」というイミになるんだよ。
ここと合わせて考えてみよう。

神崎
ってコトは……58行と61行のIF文の中にあるビット演算のケッカがゼロじゃないから……

ワンパク
……THENのサキの命令がジッコウされるってワケか!

インテリ
そういうコト!
BUTTON()命令で変数に入る数字には、はじめからビット演算しやすい数字が選ばれているんだよ。

神崎
フムフム。たしかに変数(右ボタン)が入った時は、B AND 8以外ではゼロになるね。

インテリ
それ以外のどの数でも、ちゃんとウマく動くようにできてるよ。なかなかベンリだろう。

ワンパク
ナルホド……サンプルプログラム3のころのギモンが、やっとトケたってカンジだぜ。
しかしよォ……

神崎
どうしたのワンパク君。スッキリしないカオじゃないか。

ワンパク
BUTTON()命令はもともとコレのために作られてるけどよォ、こんなコトをイチから作るのってムズカシくねえか?

神崎
たしかに、アタマで考えてココまで作るのはタイヘンそうだよね。

インテリ
うん、サスガになにもかも2進数で考えてプログラムに組むのはムズカシいだろうね。だけどビット演算にはいくつか必勝法になるパターンがあるんだ。BUTTON()命令で使ってる数の組み合わせもそのひとつだよ。

ワンパク
つまり……その必勝パターンと使い方をオボエれば、ウマくプログラムに使えるってのか?

インテリ
そういうコトなんだけど……

神崎

インテリ
その話をするともっと長くなっちゃうから、また今度にしよう!

ワンパク
ウォオー!! 今回の話がオレのプラスになったのかどうか、サッパリわからねー!!

博士
なかなかタイヘンじゃったようじゃのう。しかしワンパク君、ここでオボエたコトはけっしてムダにはならんぞい。ツギのサンプルプログラムでもビット演算がさっそく出てくるくらいじゃ。


今回のまとめ

2進数
0と1の組み合わせでできた数え方が2進数です。アタマに「0b」と付けて区別したりします。3を2進数で言うとどうかとか、111100を10進数(ふつう)に言いなおすとどうかとか、検索して調べれば早いんじゃないでしょうか。
ビット演算(AND)
7 AND 11のような形で使います。
これを2進数におきかえると「111 AND 1011」。さらに見やすい式の形にすると、
    0111
AND 1011
  = 0011

「両方とも1になっている位だけ、1になる」のがANDを使ったビット演算です。
この場合、答の0011を10進数に変えれば「3」、つまりA=7 AND 11と書けば変数が入ります。
ビット演算(OR)
   0101
OR 0011
 = 0111

「どちらかでも1がある位は、1になる」のがORを使ったビット演算です。
ビット演算(XOR)
    0101
XOR 0011
  = 0110

「両方とも1になっている位は0になり、片方にだけ1がある位は1になる」のがXORを使ったビット演算です。
ビット演算(NOT)
NOT 1101
  = 0010

2つの数をくらべずに、ただ0と1がひっくり返るのがNOTを使ったビット演算です。