ビット演算
プログラマーからひとこと
この章では、「ビット前にちらっと出てきましたね。
その時は、むずかしいので説明はしませんでした。
そうです、ビット演算はむずかしいのです。
あんまりむずかしいので、飛ばして読んでもいいです。ほら、ここにボタンも用意しましたよ。
これまでもむずかしい話はいろいろしました。どれもむずかしいかわりに、かならず必要なものでしたから、それはいいと思うんです。
配列変数なんて、かなりめんどくさかったですが、ないと困るものでしたよね。
ところがビット演算は使わないでも、まあなんとかなるんです。
私もはじめにおぼえたときは、「なくていいじゃん」と思いました。
どうです、とばし読みしたくなってきたでしょう。
じゃあ何のためにおぼえるの? いくつか理由はあります。
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進数だと、「0」「1」の次は「10」になるんだ。」
ここからは、区別しやすいよう2進数には線を引いておくよ。
たとえば10進数で「0」「1」の次は「2」だよね。
2進数だと、「0」「1」の次は「10」になるんだ。」
ワンパク「ジ、10だと!?」
インテリ「2進数だと10と書いて「イチゼロ」とか読む方がいいんだけど……」
神崎「うーん……急にチシキをつめこまれてる気がしないでもないぞ。」
インテリ「もうちょっとユックリいこうか。
10進数では、使える10コの数字の中で一番大きいのは「9」だよね。9より大きい数を書くときはどうするかな?」
10進数では、使える10コの数字の中で一番大きいのは「9」だよね。9より大きい数を書くときはどうするかな?」
ワンパク「そりゃトウゼン、1ケタ位 が上がって「10」だゼ! ……ン? 10?」
インテリ「そう、2進数も同じようなものなのさ。」
神崎「ええと、2進数だと使える2コの数字の中で一番大きいのは「1」。それより大きい数を書くときは……」
ワンパク「位が上がって、「10」になるワケか!」
インテリ「そういうコト。このルールだけオボエれば、2進数はカンペキさ。」
神崎「ホント!? うーん、10の次は1ケタ目が上がるから、11。その次は、もう上げられる位が残ってないから、位上がりして100……。」
ワンパク「オイオイ、とんでもねえハイペースでケタが上がってるぞ! ホントにコレで合ってるのか?」
インテリ「バッチリだよ! 0〜10までを数えた表がコレになるね。
こんなカンジで、どんどんケタが上がるから、1010と書いて「イチマルイチマル」とか読むんだね。」
10進数 | 2進数 |
---|---|
0 | 0 |
1 | 1 |
2 | 10 |
3 | 11 |
4 | 100 |
5 | 101 |
6 | 110 |
7 | 111 |
8 | 1000 |
9 | 1001 |
10 | 1010 |
ワンパク「フーム……じゃあ10進数で「1976」は、2進数だとどうなるんだ?」
インテリ「……。」
神崎「……。」
ワンパク「ナンだソレ! ググんのかよ!」
神崎「しかも、本当にそれで答が出るんだ!」
インテリ「まあ、2進数をいちいち手で計算するのはタイヘンだからね。検索とかアプリで出すのがフツウなのさ。」
ワンパク「「1976 = 0b11110111000」か……。この「0b」ってのはナンだ?」
インテリ「10進数と区別するための記号だね。1976をただ2進数で言えば11110111000だけど、これだと10進数の「111億1千11万1千」にも見えるから、アタマに0bと付けるのがマナーってことかな。」
神崎「だいたいわかってきたけど、それにしてもメンドくさい数え方だね……。」
インテリ「もともとコンピューターはスイッチがON かOFF かの組み合わせで作られたからねえ。この2つの組み合わせを「ビット」と言うんだ。」
神崎「ん……ビット?」
ワンパク「ワスれるトコだったぜ、アブねえ! 「ビット演算」のハナシはドコ行ったんだ?」
初歩のビット演算
インテリ「それじゃあ、プチコンで使うビット演算のサンプルを見てもらおうか。
0001#. A=5 AND 3
0002#. PRINT A
Aは変数だね。これをRUNすると、変数Aに1が入るよ!」0002#. PRINT A
ワンパク「ハ、ハァ!?」
RUN
1
OK
1
OK
神崎「ANDっていうから、てっきり5+3みたいなコトかと思ったけど……」
インテリ「5 AND 3はそういう計算とはちがうモノだってオボエておこうね。
答だけ見ても何だかわからないだろうから、トチュウの計算式も見てみよう!
」
答だけ見ても何だかわからないだろうから、トチュウの計算式も見てみよう!
101
AND 011
= 001
AND 011
= 001
」
神崎「えーと……」
ワンパク「なんだコレ! ワカるフンイキがまったくねェぞ! 5 AND 3のドコからこの式になるってんだ!」
神崎「いやいや、たぶん2進数がここで出てくるんだよね……。」
インテリ「そのとおり。5を2進数にすると101。3を2進数にすると011になるね。」
ワンパク「……3を2進数にすると11じゃなかったか?」
インテリ「アタマにつけるゼロは、いくらつけてもいいんだ。101と位をそろえるために、1コつけておいたよ。」
ワンパク「ウーム……つまり、5 AND 3を2進数にすると、
ココまではまあワカッたぜ。だがコタエが001ってのは、ナットクいかねェな!
」
101
AND 011
AND 011
ココまではまあワカッたぜ。だがコタエが001ってのは、ナットクいかねェな!
」
インテリ「習ったことのない計算だから、そう思うのもトウゼンだね。
ビット演算の「AND」では、「両方とも1になっている位だけ1になる」とオボエると……カンタン……かなあ?」
ビット演算の「AND」では、「両方とも1になっている位だけ1になる」とオボエると……カンタン……かなあ?」
神崎「……かなあ?」
ワンパク「ダレもナットクいってねェじゃねえか!」
神崎「うーん。「位」がポイントなんだよね。たとえば1ケタ目は……
両方とも「1」になっている位……だから……
答も1になるってコト?
」
101
AND 011
AND 011
両方とも「1」になっている位……だから……
101
AND 011
= ??1
AND 011
= ??1
答も1になるってコト?
」
インテリ「いいよ! そこまでワカれば、あともカンタンなハズ!」
ワンパク「つまり2ケタ目も、こういうコトか?
コレはかたっぽが「0」、もうかたっぽは「1」だから、
ゼロがくるワケか?
」
101
AND 011
= ??1
AND 011
= ??1
コレはかたっぽが「0」、もうかたっぽは「1」だから、
101
AND 011
= ?01
AND 011
= ?01
ゼロがくるワケか?
」
インテリ「そのとおり! 3ケタ目はもうわかるよね。
片方が「1」、もう片方が「0」ということは……
これで001までは答が出たね。
」
片方が「1」、もう片方が「0」ということは……
101
AND 011
= 001
AND 011
= 001
これで001までは答が出たね。
」
神崎「その001は2進数だから、10進数に直すと……」
ワンパク「1が変数Aに入るってコトか。」
インテリ「計算のしかたさえワカれば、あんがいラクだろう。たとえばB=7 AND 11だとどうなるかな?」
ワンパク「ツギツギに出してきやがって! まあヤリ方はワカッてるぜ。まず2進数に変えるんだろ?
7は111、11は1011だから、こうなるゼ!
」
7は111、11は1011だから、こうなるゼ!
0111
AND 1011
= ????
AND 1011
= ????
」
神崎「で、「両方とも1になっている位」をさがすと……
1ケタ目と2ケタ目が「1」になるね。のこった位はトウゼン「0」だから……
」
0111
AND 1011
= ??11
AND 1011
= ??11
1ケタ目と2ケタ目が「1」になるね。のこった位はトウゼン「0」だから……
」
インテリ「答はこうなるね。
0011、つまり10進数で言いかえると3が変数Bに入ることになるね。どうだい、思ったよりはカンタンだろう?
」
0111
AND 1011
= 0011
AND 1011
= 0011
0011、つまり10進数で言いかえると3が変数Bに入ることになるね。どうだい、思ったよりはカンタンだろう?
」
ワンパク「やり方ドオリにやれば、まあデキねえコトはねェが……トンデモなくメンドくせェぜ!」
インテリ「ANDのほかにも、「OR」や「XOR」の計算もあるんだけど……」
ワンパク「ウオォー! メンドくせェー!!」
ORとXOR、NOTのビット演算
ワンパク君、すっかりOverflowエラーというトコロじゃな。などとBASICネタもクールに使いこなすワシじゃ、ハカセじゃ。ビット演算の「OR」も「XOR」も「AND」とあまり変わらんぞい。ものはためしじゃ、ジッサイの計算式を見てもらおうかの。
- OR
-
0101
OR 0011
= 0111
ワカるかの? 「どちらか片方でも1がある位は1になる」のがOR の計算じゃ。 - XOR
-
0101
XOR 0011
= 0110
XORじゃと、「両方とも1になっている位は0になり、片方にだけ1がある位は1になる」わけじゃ。ちょっとヤヤコシイのう。
そうそう、「XOR」は「exclusive OR」略して「エクスオア」とか「エックスオア」などと読むのじゃぞ。伝説の剣かなんかの名前っぽくてカッコイイわい。 - NOT
-
NOT 1101
= 0010
NOT はちょっとトクシュじゃな。2つの数をくらべたりせず、ただ0と1がひっくり返るのが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
」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文の組み合わせで、十字ボタンの押された方向を調べるんだったっけ。」
BUTTON()命令とIF文の組み合わせで、十字ボタンの押された方向を調べるんだったっけ。」
インテリ「「IF B AND 1」と書くと、「Bの中に1がまじっている」というイミになると習ったよね。」
ワンパク「十字ボタンの右上が押されたら、BUTTON()命令で変数Bのナカミには1(上)+8(右)の9が入る……。
で、Bのナカミが9でもなぜか「IF B AND 1」や「IF B AND 8」と書くとアタリになる、って話だったな……。
あらためて考えると、ワケがわからねェぜ!」
で、Bのナカミが9でもなぜか「IF B AND 1」や「IF B AND 8」と書くとアタリになる、って話だったな……。
あらためて考えると、ワケがわからねェぜ!」
神崎「あれ、だけどこのB AND 1って、ビット演算の書き方じゃないかな?」
インテリ「そのとおり! もう1度、このIF文をビット演算の考え方で見てみると、イミがわかってくると思うよ。」
ワンパク「チクショウ、またビット演算すんのかよ!
まず右上が押されて変数Bに9が入ったとするだろ……で、58行目がIF B AND 1 THEN……。
これは変数のナカミを考えると、IF 9 AND 1 THENってコトだよな。」
まず右上が押されて変数Bに9が入ったとするだろ……で、58行目がIF B AND 1 THEN……。
これは変数のナカミを考えると、IF 9 AND 1 THENってコトだよな。」
神崎「9 AND 1は、こう計算するんだったよね。
答は0001、10進数に直すと「1」になるね。
」
1001
AND 0001
= 0001
AND 0001
= 0001
答は0001、10進数に直すと「1」になるね。
」
ワンパク「じゃあ次の59行は……IF B AND 2 THENだから、9 AND 2をビット演算すると……
オ、オォ!? キレイにゼロになったぜ。
」
1001
AND 0010
= 0000
AND 0010
= 0000
オ、オォ!? キレイにゼロになったぜ。
」
インテリ「だんだんカラクリが見えてきたね。「B AND 4」を調べる60行だと、
やっぱりゼロ。
「B AND 8」を調べる61行なら、
これを10進数に直すと「8」になるね。
」
1001
AND 0100
= 0000
AND 0100
= 0000
やっぱりゼロ。
「B AND 8」を調べる61行なら、
1001
AND 1000
= 1000
AND 1000
= 1000
これを10進数に直すと「8」になるね。
」
ワンパク「下方向(AND 2)も左方向(AND 4)もビット演算のケッカはゼロ……。上(AND 1)や右(AND 8)だと、ゼロにはならねェんだな。」
インテリ「ソコだね!
ちょっと話がそれるようだけど、IF (変数) THENというカタチのIF文は、「変数がゼロじゃなければ」というイミになるんだよ。
ここと合わせて考えてみよう。」
ちょっと話がそれるようだけど、IF (変数) THENというカタチのIF文は、「変数がゼロじゃなければ」というイミになるんだよ。
ここと合わせて考えてみよう。」
神崎「ってコトは……58行と61行のIF文の中にあるビット演算のケッカがゼロじゃないから……」
ワンパク「……THENのサキの命令がジッコウされるってワケか!」
インテリ「そういうコト!
BUTTON()命令で変数に入る数字には、はじめからビット演算しやすい数字が選ばれているんだよ。」
BUTTON()命令で変数に入る数字には、はじめからビット演算しやすい数字が選ばれているんだよ。」
神崎「フムフム。たしかに変数Bに8(右ボタン)が入った時は、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と書けば変数Aに3が入ります。 - ビット演算(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を使ったビット演算です。