Common Lisp のビット演算について調べていた私は、lognot 関数の出力を確かめようと (format t "~b" (lognot #b10110100)) のようなコードを書いていた。
しかし、その結果が -10110101 となっているのを見て、一瞬納得しかけたが、、、おかしい。本当は 01001011 ではないのか。いやまて。これは明らかにおかしい。思っていたのと違う！違うやろ？
いったい何が起こっているのか？謎を解くために私は調査に乗り出した。
((format t "~b" (lognot #b10110100))) ;-> -10110101((format t "~b" (lognot #b10110100))) ;期待は... 01001011~Dと同じに出す、基数だけ2にすると書いてある ビット反転した値 + １ を求め、そこに 最上位ビット 1 を加えた値が本来表示したい値である。 -10110101 -> 反転 -> 01001010 -> +1 -> 01001011 -> 後は最上位ビットを加える最初に気付いたのは、すでに書いているが、lognot関数 の値をformat 関数に与えると、思っていたのと違う値として表示されることだった。例えば次のようになる。ちなみに、この記事は全体に SBCL 1.2.13 で動作を確認している。
* (defun show-bin (value) (format t "~b" value))
SHOW-BIN
* (show-bin 128)
10000000
NIL
* (show-bin (lognot 128))
-10000001
NIL
* #b10000001
129
* (show-bin -129)
-10000001
NIL
* (show-bin #b10110100)
10110100
NIL
* (show-bin (lognot #b10110100))
-10110101
NILうーん。いくつか結果を出して、その結果を計算してみて分かったのだが、どうも、format 関数は符号と整数部を分けて表示している感じがする。いや、している。
うーん。うーん。なるほどね！そうだよね、数値は符号と整数部に分けられるからね！そうだよね！。。。ちがわい。期待しているのは、ビット反転した値だわ。表示されているのは負の符号と、整数部の正のビットの値だわ。そうじゃないだわ。
| 値 | ~b表示 | 期待する表示 | 補足 |
|---|---|---|---|
| 128 | 10000000 | 0000 1000 0000 | |
| (lognot 128) | -10000001 | 1111 0111 1111 | = -129 |
| -128 | -10000000 | 1111 1000 0000 | |
| (lognot -128) | 1111111 | 0000 0111 1111 | = 127 |
| -3 | -11 | 1101 | |
| 3 | 11 | 0011 |
こうだろ！？そうだろ！？ＣとかＣ＃だったらそうしてくれるんじゃないかね！？
ま、しかし、こういう挙動が起こった場合、それはCommonLisp においては「仕様を知らないだけだがね」ってなる。今回の場合も、おそらく仕様だろうと決め打って調査を開始した。
そしたら案の定だわ。format 関数の定義の一部に、~bの表示の仕様というページがあり、そこには次のように書かれていた。
~D のように表示しますが、基数のみ 2 とします。と書いてある。~D は、意識することはないが、普通にしていたらたしかに「符号」と「整数部は正の整数で」出してくれる。すなわち、負の数値はあくまで - を付け、整数部は正の整数で表示するという仕様である。負の数値のビット表現については、とくに考慮しない。~dの表示の仕様 も確認してみたが、負の数のビット表現に関する記載は、見つけられなかった。
他に、他の表示関数 write や、表示の帰趨を決定するスペシャル変数 *print-base*を確認してみたが、負の値を私が求めているようなビット列として表示する方法に関する仕様は見つけられなかった。
Common Lisp は私が生きているよりずっと長く、私よりもはるかに賢い人たちにもまれた言語である。今は漬け込まれている。（その存在に気付いた人がおいしく食べていく）したがって、そうしているのには理由があると思われた。あるいは、”そうしないと決めた理由がどこかにあるだろう”と想像された。
ここまでの調査でひとまずわかったこととして。負の値となるような計算結果について、format 関数が、あるいは私の調べた範囲のCommonLisp の標準仕様が、思い通りの挙動をしてくれないことはわかった。しかし、どうしてこのような挙動をするのだろうか？調べていったところ、Common Lisp の整数値は、無限に桁数を持つことができる、という仕様がかかわっているように思われた。
CommonLisp で、SBCLで初めて ビット演算を試したとき、どうやら私は暗黙に有限桁数のビット列を想像していたようである。16ビットなり、8ビットなり、64ビットなりで表現された数値を想像している。そして、暗黙にsigned, unsigned について区別して考えている。そうした場合、負の数はたった一つの表現を得ることになる。符号なしであれば、符号ありの場合に負の数にあたるビット表現に対しては、正の整数が与えられる。しかし、CommonLispの整数は違う。無限の桁数を持っている。無限に桁数を持つということはどういうことか？考えてみるにそれは、有限桁で区切ると、「そのビットより上位側のビットが０なのか、１なのかわからなくなる」ということである。
例えば、整数値を８ビットで表現してみました！といって次のような表を出すとする。
| 数値 | 下位8ビット分 |
|---|---|
| 1 | 0000 0001 |
| 127 | 0111 1111 |
| 180 | 1011 0100 |
| -1 | 1111 1111 |
| -127 | 1000 0000 |
| 64 | 1000 0000 |
私の頭の中では今回の例を試したとき、このような感じの頭になっていた。だが、冷静になってから見てみると、何かがおかしい。この整数の型は、なんだ？気付いてみるとものすごい違和感を覚える。-127と64が同じ表現になっていて混乱しないのか問いただしたくなる。180という数値もしれっと混ざっているが、本当に8bit整数ならunsigned じゃないと表現できないだろう、、、。型がある言語であればその上限・下限に強く意識を持つものだが、境界を持たないという定義を持つ環境では、具体的なビット表現に思いを寄せることがなくなっているのに気づく。。結局これらの値は果たして、signed なのか unsigned なのか？そもそもこの数値は、本当に８ビットで考えているのか？若干怪しい。いや、だいぶおかしい。それでいて違和感を覚えないのは、今何をしているか、どのような結果になるかについて、”内部の表現に考えを寄せることなく”想像できているためなのだろう。
さて、ビット表現の話に戻そう。たとえばバイナリ表現 1000 0000 は、次のように解釈できる。
しかし、ビット列が上位側へ無限につながっているとしたら、次のような場合も考えられる。
そして、「いずれも正解である」と言える。単に表示に対する解釈が違うだけである。前提がはっきりしていない（もしくは自分の中でだけはっきりしている）ので一つに決められるだけではないか。
このおかしさに気付くと、そもそも負の数のビット表現ってどうやってするのだったかを思い出すことになる。先の例のいずれの整数も 16bitあればsignedの値として正常に表現できることだろう。しかし、無限に桁数があるとすれば、、、？
| 数値 | 4bit? | 8bit ? | signed 16 bit | signed 32bit (上位24bitを省略) |
|---|---|---|---|---|
| 1 | 0001 | 0000 0001 | 0000 0000 0000 0001 | 0..0 0000 0001 |
| 127 | 不可 | 0111 1111 | 0000 0000 0111 1111 | 0..0 0111 1111 |
| 180 | 不可 | 1011 0100 | 0000 0000 1011 0100 | 0..0 1011 0100 |
| -1 | 1111 | 1111 1111 | 1111 1111 1111 1111 | 1..1 1111 1111 |
| -127 | 不可 | 1000 0000 | 1111 1111 1000 0000 | 1..1 1000 0000 |
| 64 | 不可 | 1000 0000 | 0000 0000 1000 0000 | 0..0 1000 0000 |
無限に長さを持つということは、何ビット目を見ても、まだ上位側にビットが続いているということである。もちろん、どこかで「あるビットからは、どの上位ビットを見ても０だらけ（正）か１だらけ（負）」である状態になるのだが。
また、表示するうえでは無限にビット列を表示するわけにもいかないため、有限桁数で止めることになる。その場合に、その後続く上位側のビットが１なのか０なのか、区別がつかない可能性が残るということである。たとえば、上記の例では64 と -127 が8bit表示したところで止めてしまった場合、同じ表現に見えるということである。
そして Common Lisp の format 関数は、これらの表現とは別の表現を用いることにしているようである。符号＋整数部（負であれば正の値に符号反転した値）で表現する。無限にビットが続くということを考えると、よい割り切り方だと思う。しかし、整数部をそのままビット値で表してくれるのは、、、使ってみると悩ましい。そうじゃねえ、そうじゃねえだわ。結果的に予期せぬ落とし穴になっていた。
上記の例の32bit表記の際にも用いたが、便宜上 正の値は 0..0 で上位側の 0 を省略し、負の値は 1..1 で上位側の 1 を省略している。今後もそのように表記するし、表示用のコード例も同じようにしている。
ここまでで、何が起こっているか、何を間違っていたかはおおむね分かった。だが、目的のビット表現は。今後も私は符号と整数部が分かれたformat 関数の表現を使い続けるのか。いやまあ、関数とか作ることができるだろう。format関数は、負の整数は思ったのと違う結果になるが、正の整数については正常に値を表示するのだから。単に、無限に桁数を考えたときの表示を考えてやればよいだけの話である。
手掛かりは、format関数のビット表現である。ビット表現が全くできないわけではない。正の整数であれば、思った通りの値を表示できる。では、負の数をビット表示した場合に、上位側ビットがすべて１になる前の部分を正の整数として表現できれば、何とかなる。つまり、次のように考えられる。
(lognot #b10110100) の値は、ビット列としては 1..101001011 と表現できる #b10110100 は 180, 1..101001011 は -181101001011 (あるいは 0..0101001011) の値を持つ値が計算できれば、表示ができるようになる 1101001011, 11101001011,, でも間違ってはいない0..0101001011 の値は 331, 0..01101001011 の値は 843それを考えるには、そもそも負の値はどのようなビット列になるのか？それを１０進数で表示すると一般的にはどうなるのか？考える必要がある。
log*系関数はいずれも２の補数であることを前提とした処理となっている。Hyperspec にも書いてある。バイナリによる負の数の表現には、２の補数を用いることが多い。負の値のビット表現は知らずのうちに２の補数による表現になっていることがある。知識として１の補数（負の数は、正の数ビット表現に対するビットごとのxorの結果に等しい）が言及されることもあるが、今回は関係ない。
２の補数とは？
その最上位ビット (MSB) よりひとつ上のビットが1で、残りが全て0であるような値
（8ビットの整数であれば、100000000(二進) = 256）から、
元の数を引いた数が2の補数である。
(Wikipedia)他にも次の性質がある。
- 正の整数 A と、対応する負の整数(補数) -A について、足すと 最上位ビットのみ１、それ以外は０となる
- A + -A => 0..010..0 (2^n となる整数)
- 正の整数 A から、そのビット反転 ~A を求め、1 を足すことで 対応する負の整数(補数) -A となる
- -A = ~A + 1
おお、、なるほど、、、どれを使えばいいんだろう、、、。
たとえば８ビットの値で符号ありの値を考える場合、正の値に対応する負の値は次のように表せる
| 正の値 | 正の2進数 | 負の値 | 負の2進数 | 正と負の値を足した結果 (9bit目あり) |
|---|---|---|---|---|
| 127 | 0111 1111 | -127 | 1000 0001 | 1 0000 0000 |
| 3 | 0000 0011 | -3 | 1111 1101 | 1 0000 0000 |
これで無限にビット列があると想定した場合も、例えば次のように表せる。
| 正の値 | 正の2進数 | 負の値 | 負の2進数 | 正の値の反転 |
|---|---|---|---|---|
| 127 | 0..0 0111 1111 | -127 | 1..1 1000 0001 | 1..1 1000 0000 |
| 3 | 0..0 0000 0011 | -3 | 1..1 1111 1101 | 1..1 1111 1100 |
補数についてわかったところで、今のところ現時点での目的であるビット表現に考えを戻してみる。求めたい値は何だろうか？それがほしい負の整数値のビット表現を得るために必要な正の整数値である。
う、、うん。何がほしいんだろう？えーっと。無限にビット列が続く負の値 -127 (= 1..1 1000 0000) があったとしよう。これを黙ってformat 関数に与えると、結果は -111111 (※ 127 = 0..0 0111 1111) となる。それは期待する結果ではない。そこで、一度 ビット列 1..1 1000 0000 に対して、表現だけ考えると 0..0 1000 0000 (= 64) あるいは 0..0 0001 1000 0000 (= 384),,, などを求めれば、format 関数は少なくとも一部は思った通りの値として表示できる。
| 数値 | ビット表現 | format 関数の表示 |
|---|---|---|
| -127 | 1..1 1111 1000 0000 | -1111111 |
| 64 | 0..0 0000 1000 0000 | 10000000 |
| 384 | 0..0 0001 1000 0000 | 110000000 |
あとは、format 関数の出力にしれっと 1..1 とつけてやれば、思った通りのビット表現を得られる。
残る問題は、このビット列で表現したい負の整数値（例の場合 -127）に対して、ほしいビット表現を得るための正の整数（例の場合 64, 384など）をどのように計算するかである。
ここで２の補数の定義を思い出す。CommonLispの整数値は無限に桁を持てるのだ。だから、ある整数を超える 2^n 乗の整数は容易に求められる。
そうやって結論にたどり着いて最終的にできたものがこちら。
(defun show-binary (value)
(if (>= value 0)
(format nil "0..0~b" value)
(let* ((sign-inverted-value (* -1 value))
(bigger-2-power (ash 1 (+ 1 (integer-length sign-inverted-value))))
(display-value (- bigger-2-power sign-inverted-value)))
(format nil "1..~b" display-value))))出力したものがこちらである。
| 値 | 出力 | 補足 |
|---|---|---|
| -128 | 1..110000000 | = (lognot 127) |
| 128 | 0..010000000 | |
| 127 | 0..01111111 | = (lognot -128) |
| -3 | 1..101 | |
| 0 | 0..00 | |
| 3 | 0..011 |
- 128 + (-128) = 最上位ビット以外は０という関係になる値となっている
- 127 と (lognot 127) のビット値が、確かに反転した値とみえる
うん。満足した。これだってこれ！これだわ！そうやろ？
この際 format 関数での負の値の表現を使用し続けることにした場合の脳内での計算方法について。ビット反転による２の補数の定義を使うことができる。
-101101010100101001001011これで何も問題ない。
Common Lisp を勉強していてありがちな現象が、「それ、ＸＸに書いてあるよ」 である。今回遭遇した負の値の表現に関しても、その現象が起こらないかなと思う部分がある。自分で書いたコードは、自分なりには努力したが、なんだか、おさまりがすごく悪いような気がしている。感覚なのでうまく言えないのだが、、、。ただ、仕様文書にも、いくつかのキーワードでの検索結果でも見つけられなかったことから見るに、検索性の悪い話題であることは間違いない。
そもそも、この問題は実際いつ発生する問題なのか？話題にならない程度に問題のおこらない現象なのではないか？今のところ自分としての見解は、「ビット反転を使用しない限りは発生しない」 のではないかということである。
単に計算をしているときに「負の値のビット表現がほしい！」と思うだろうか？思わないと思う。そもそも１６進数にせよ２進数にせよ、必要とされるのはビット演算がかかわってくる場合に限られるように思われる。
ビット演算をしているときに、負の値がふつう現れるか？基本的には現れないように思う。今自分が思いつく限り、ビット演算を必要とする計算のほとんどは、正の整数のまま処理ができるように思われる。
ふとした瞬間に「負の値」が現れるのは、ビット反転を行ったときだけである。くどいようだがCommonLispの整数は無限に桁を持つことができ、有限桁数の値であれば正の数のまま処理ができる。and も or(ior) も、xor もだ。唯一の例外が、ビット反転を伴う計算をした時である。上位側まで無限に続く１のビットを表現するために、内部的に負の整数となる値を得ることになる。
(show-binary #b10110100) ;=> "0..010110100"
(show-binary (logand #b10110100 #b11110000)) ;=> "0..010110000"
(show-binary (logior #b10110100 #b11110000)) ;=> "0..011110100"
(show-binary (logxor #b10110100 #b11110000)) ;=> "0..01000100"
(show-binary (lognot #b10110100)) ;=> "1..101001011"負の値を負の値のままビット演算したいという場合は、どうしても無限に続いているということを意識する必要がある。よく注意して扱えばなんとかなる。
反面、正の値のままで扱う方法もある。lognot による反転の代わりに、２の補数の計算をすることでそれができる。
(show-binary (lognot #b10110100)) ;=> "1..101001011"
(show-binary (- (ash 1 9) #b10110100)) ;=> "0..0101001100"できるとは書いたが、私は使わないだろうと思う。ビット幅が制限されるのも、どうにも都合が悪い。型の宣言をすれば必要なかったりしないだろうか？
この調査を始める前に、ビット演算の方法を調査していた。その中で lognot の出力がどうにもおかしいことに気付いた。その原因は何だと調べていたら、format関数とビット値の表現方法の問題だとわかった。思った通りの表示の方法を得るために、工夫をした。大変面白い体験となった。
また、この記事の内容は、実用的にはおそらく必要性が低いと思われる。読み物として楽しんでいただければ幸いである。返事は遅くて内容もお礼だけになる気もするが、、、コメントいただければ幸いである。
Lispの勉強用サイトとして、SBCL をサポートしているプログラミング問題サイト HackerRankを愛用している。
その挑戦の中で、ビット演算を必要とする問題があり、いざどのようにするかを調べてみたのだが、最初探し方がまずくて見つけられなかった。というか、最近真っ先に逆引きCommonLispを参照するクセをつけているのだが、探して見つからなかった。
というわけで、調べ、おおむね逆引きにまとめたのだが、整数が”無限の長さを持つ”ことによる”負の整数のビット表現”でドはまりした。やってみるとパズル的で面白いのだが、初めて使った人は同じ罠にはまらないかな、、とも思った。初心者バイバイ感あった。
この記事では、調べたことを逆引きに書いたよという単なる報告と、ドはまりした負の整数とビット演算の関係について別の記事 に書いたことの報告を書く。あまりに長くなったので分けた。
logand, logior (or演算), logxor, lognotなどビット演算処理が一通りそろっている。逆引きのビット演算の項目として書いた
あと、boole 関数はlog関数と同じことを「オペレータを指定して」できる。よく見ると、boole のほうが少し処理の種類が多い。なんとなく、遺伝プログラムとか人工知能などといったプログラム生成の論理処理用に作られたのでは？と想像した。データとして演算が扱えるということで。逆引きのビット演算の項目の中に一緒に書いた。
bit-vector についてはそこまで調べていない。
#*10110100 のように、 #* から始めるまとめというには長い記事になったので、別の記事 としてまとめた。
概要としては
(format t "~b" (lognot 8)) ;-> -1001 となるのだろう？ 1011 とか 1111 1011 なのだが？そういうわけでいろいろ考えた結果、負の整数値でもビット値として表示できる次の関数を作ってみた。
(defun show-binary (value)
(if (>= value 0)
(format nil "0..0~b" value)
(let* ((sign-inverted-value (* -1 value))
(bigger-2-power (ash 1 (+ 1 (integer-length sign-inverted-value))))
(display-value (- bigger-2-power sign-inverted-value)))
(format nil "1..~b" display-value))))この関数を使った時の表現は, 正の値には 0..0 を、負の値には 1..1 を付けて表示する。
負の符号の整数値は、上位ビット側に無限に 1 のビットがあることを表現しているつもり。
| value | binary | 補足 |
|---|---|---|
| -128 | 1..11110000000 | = (lognot 127) |
| 128 | 0..010000000 | |
| 127 | 0..01111111 | = (lognot -128) |
| -3 | 1..11101 | |
| 0 | 0..00 | |
| 3 | 0..011 |
とはいえこの関数では
などいくつかの自分ニーズに応えられていないので、今後の改良が待たれる。
keyword)という 特別なパッケージに属しているcl, common-lispという名前空間に属しているcl-user, common-lisp-user という名前空間に属している package-name:symbol-name で export されているシンボルにアクセス ppcre:scan ql:quickload asdf:load-system などpackage-name::symbol-name で パッケージ内の任意のシンボルにアクセス :keyword のように、コロン(:)から始まるシンボルをキーワードという * :test
:testkeywordパッケージに属する ライブラリ名 + : + 関数名、で呼べるんだね？ cl-ppcre:scan とか asdf:load-system とか。cl-ppcre は ppcre でもOK。**を定義するマクロ」だと思って間違いありません。Written with StackEdit.
Blogger はURLを指定して画像を記事に埋め込むことができる。StackEditはMarkdownの画像埋め込み機能を使ってそれを簡単に実現できる。
アップロードはどうせGoogleのサービスを使っているのだからGoogle+ がよいだろう。StackEdit のGUIに Google+の画像をImportしてくるというボタンもあるため、使いやすい。
画像のをつける機能はないのである！
Markdownの記法としては
Google+ の画像を使うときは、素直に StackEditの機能を使ったほうが良さそうである。URLが埋め込み専用のシンプルなものになっている。
画像だからね。
怪物に襲われたゴミ処理場、何かの生物に襲われた？医療設備、何かあったらしい宇宙ステーションなどのさまざまな惨劇の舞台を清掃するゲームである。
Visceraとは臓物の意
ぶちまけられた血、反撃の後のと思われる銃痕、薬莢に銃、何よりバラバラになった人体と臓物、たおされた怪物の一部などなどのグロ要素
そこに馬鹿みたいに散りばめられた菓子の袋や紙コップ、中華料理のテイクアウト箱、缶。などの、なんで片付けねぇんだクソ、、と思わされる要素に満ち溢れた素敵なゲームである。
この記事はプレイしたことがある人を対象に書いている。ゲームの様子などはぜひ実況者さんのプレイを参照されたし。
センサーには二種類あることはプレイされた方であればご存知のことと思う。だが、何に反応するかは、割とわからなくなりがちであるので、まとめた。
リアルタイム2時間を平気で食いつぶしてゆくゲーム。
ゲームにおける効率化の追求とミスをしない手際のよさの育成がされる（プレイヤーの。）
綺麗になった部屋を見てなんか満たされる感覚を味わえる
イラついたらプラズマ溶接銃で溶かしまくろう！
StackEditがBloggerにアップロードする場合、YAML Formatter によるメタ情報の埋め込みに対応している。記事テキストの冒頭に、次のようにメタ情報を記載する。
---
title: 記事タイトル
tags: タグ１,tag2,タグ３
---利用可能と説明されているタグは
title : 記事公開用タイトルtags : 記事のタグ, カンマで区切るpublished : (未確認) date : (未確認) 情報は2015-11-09現在。
#一つ, ===による区切りWritten with StackEdit.
Land of Lisp (書籍) : 日本語訳10章にある Loopマクロ周期表が役に立つ
使用方法については次を参照。
- Lisp入門サイト(そのうちまとめる)
- Hyperspec
- 逆引きCommonLisp の 制御構造のページ
どれぐらい役割や使い方が簡単に理解できた かの順に並べている
Written with StackEdit.
大切なことなので２回書いた。
StackEdit がその欲求を かなり 満たしてくれる。
特にソースが書きやすい。Blogger のソースコード対応は実際残念
(defun tarai (x y z)
(if (< x y)
y
(tarai (tarai (1- x) y z)
(tarai (1- y) z x)
(tarai (1- z) x y))))うまくいったらごかっさい！
published: falseを指定することで非公開でアップロード可能注意点をまとめた記事を書いた。
Written with StackEdit.
(truename "~")
(require 'asdf) ; あるいは (require "asdf")