初めに
Common Lisp のビット演算について調べていた私は、lognot 関数の出力を確かめようと (format t "~b" (lognot #b10110100)) のようなコードを書いていた。
しかし、その結果が -10110101 となっているのを見て、一瞬納得しかけたが、、、おかしい。本当は 01001011 ではないのか。いやまて。これは明らかにおかしい。思っていたのと違う！違うやろ？
いったい何が起こっているのか？謎を解くために私は調査に乗り出した。
概要(ネタバレ注意)
- format 関数は、負の数値をバイナリ表示する際、
通常の整数同様に符号部と整数部に分け、整数部のバイナリで表示する
- 例
((format t "~b" (lognot #b10110100))) ;-> -10110101
- 期待しているのは、あくまで２の補数として表現した場合の値
- 例
((format t "~b" (lognot #b10110100))) ;期待は... 01001011
- format 関数の定義では、
~Dと同じに出す、基数だけ2にすると書いてある
- その原因はおそらく、Common Lisp の”普通の整数は無限に桁が続く”仕様にあると思われる
- 自分なりに負の数もビット表現できるような方法を考えた
- ビット反転を伴う計算をするときぐらいにしか、おそらく問題にはならないだろう。
- 脳内で何とかする方法として：表示された値に対して、
ビット反転した値 + １ を求め、そこに 最上位ビット 1 を加えた値が本来表示したい値である。
- 例
-10110101 -> 反転 -> 01001010 -> +1 -> 01001011 -> 後は最上位ビットを加える
参照
- そもそも２の補数について
- Common Lisp の整数の仕様
- Common Lisp における数値の文字列表示
- format や print 関数と *print-base*
最初に気付いたのは、すでに書いているが、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 は、次のように解釈できる。
- signed の 8bitの値で、-127 を表している
- unsigned の 8bitの値で、64 を表している
しかし、ビット列が上位側へ無限につながっているとしたら、次のような場合も考えられる。
- 暗黙に 8bit以上ある値として、この後の上位ビットには 0 が続く。したがって 64 を表している
- 表示上の最上位ビットが 1 なのだから負の値である、したがって上位ビットは1が続き、-127 を表している
そして、「いずれも正解である」と言える。単に表示に対する解釈が違うだけである。前提がはっきりしていない（もしくは自分の中でだけはっきりしている）ので一つに決められるだけではないか。
このおかしさに気付くと、そもそも負の数のビット表現ってどうやってするのだったかを思い出すことになる。先の例のいずれの整数も 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 は -181
- 整数値として、
101001011 (あるいは 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 乗の整数は容易に求められる。
- ある負の整数値 -A のビット長 が L であるとする
- -A という整数が「あたかも (L+1) bit幅の符号付き整数値である」かのように考えてみると、、、
- -A = 2^(L+1) - A
- もしビット長が制限されていれば、L = ビット長、のときにこの計算で得られる値は負の値を表すビット列になる
- Common Lisp では、ビット長に制限はないため、常に L+1 は A より大きな正の整数である。
- 結果、”正の整数だが、Ａの２の補数に相当するビット表現を持つ値”が得られる
負の値のビット表現をおおむね思った通りにできる関数
そうやって結論にたどり着いて最終的にできたものがこちら。
(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 関数への組み込み？
- 固定桁数での表示
- ４ビット・８ビットで区切ってほしいかな
- １６進数への対応
ちなみに：脳内補完する方法
この際 format 関数での負の値の表現を使用し続けることにした場合の脳内での計算方法について。ビット反転による２の補数の定義を使うことができる。
- format 関数の出力を見る
- 符号を消してビット反転する
- +1 する
これで何も問題ない。
ところで、この関数を使うタイミングはいつなのか？について
Common Lisp を勉強していてありがちな現象が、「それ、ＸＸに書いてあるよ」 である。今回遭遇した負の値の表現に関しても、その現象が起こらないかなと思う部分がある。自分で書いたコードは、自分なりには努力したが、なんだか、おさまりがすごく悪いような気がしている。感覚なのでうまく言えないのだが、、、。ただ、仕様文書にも、いくつかのキーワードでの検索結果でも見つけられなかったことから見るに、検索性の悪い話題であることは間違いない。
そもそも、この問題は実際いつ発生する問題なのか？話題にならない程度に問題のおこらない現象なのではないか？今のところ自分としての見解は、「ビット反転を使用しない限りは発生しない」 のではないかということである。
単に計算をしているときに「負の値のビット表現がほしい！」と思うだろうか？思わないと思う。そもそも１６進数にせよ２進数にせよ、必要とされるのはビット演算がかかわってくる場合に限られるように思われる。
ビット演算をしているときに、負の値がふつう現れるか？基本的には現れないように思う。今自分が思いつく限り、ビット演算を必要とする計算のほとんどは、正の整数のまま処理ができるように思われる。
- バイナリファイル、バイナリストリーム（ネットワークとか）の読み書き - ldb関数が使える
- データに対するマスク処理、パターンマッチ - and, or, あるいは bit-vectorを用いる
ふとした瞬間に「負の値」が現れるのは、ビット反転を行ったときだけである。くどいようだがCommonLispの整数は無限に桁を持つことができ、有限桁数の値であれば正の数のまま処理ができる。and も or(ior) も、xor もだ。唯一の例外が、ビット反転を伴う計算をした時である。上位側まで無限に続く１のビットを表現するために、内部的に負の整数となる値を得ることになる。
(show-binary #b10110100)
(show-binary (logand #b10110100 #b11110000))
(show-binary (logior #b10110100 #b11110000))
(show-binary (logxor #b10110100 #b11110000))
(show-binary (lognot #b10110100))
回避策：ash 関数を用いたビット幅の制限
負の値を負の値のままビット演算したいという場合は、どうしても無限に続いているということを意識する必要がある。よく注意して扱えばなんとかなる。
反面、正の値のままで扱う方法もある。lognot による反転の代わりに、２の補数の計算をすることでそれができる。
(show-binary (lognot #b10110100))
(show-binary (- (ash 1 9) #b10110100))
できるとは書いたが、私は使わないだろうと思う。ビット幅が制限されるのも、どうにも都合が悪い。型の宣言をすれば必要なかったりしないだろうか？
終わりに
この調査を始める前に、ビット演算の方法を調査していた。その中で lognot の出力がどうにもおかしいことに気付いた。その原因は何だと調べていたら、format関数とビット値の表現方法の問題だとわかった。思った通りの表示の方法を得るために、工夫をした。大変面白い体験となった。
また、この記事の内容は、実用的にはおそらく必要性が低いと思われる。読み物として楽しんでいただければ幸いである。返事は遅くて内容もお礼だけになる気もするが、、、コメントいただければ幸いである。
