CommonLisp のビット演算を調べた話

ことのあらまし

Lispの勉強用サイトとして、SBCL をサポートしているプログラミング問題サイト HackerRankを愛用している。

その挑戦の中で、ビット演算を必要とする問題があり、いざどのようにするかを調べてみたのだが、最初探し方がまずくて見つけられなかった。というか、最近真っ先に逆引きCommonLispを参照するクセをつけているのだが、探して見つからなかった。

というわけで、調べ、おおむね逆引きにまとめたのだが、整数が”無限の長さを持つ”ことによる”負の整数のビット表現”でドはまりした。やってみるとパズル的で面白いのだが、初めて使った人は同じ罠にはまらないかな、、とも思った。初心者バイバイ感あった。

というわけで、

この記事では、調べたことを逆引きに書いたよという単なる報告と、ドはまりした負の整数とビット演算の関係について別の記事 に書いたことの報告を書く。あまりに長くなったので分けた。

概要

• CommonLispにおけるビット演算について調べた
• 整数のビット演算をする log*系関数 を知った
  
  • それと等価な演算ができる boole 関数があることを知った
• 今回は書いていない：bit-vector によるビット演算があることを知った
  
  • 処理は log-*系関数 で行う
  • こちらはまだ試していないのでこの記事にも逆引きにも書かない
  • ライブラリや実例のリンクだけ。
• 本題：log* 系関数でのビット演算と負の数値について
  
  • あまりに長かったので次の記事にする

参照

• 逆引き記事
  
  • 数値
  • 基本的なビット演算をする
• Hyperspec
  
  • log*系関数
  • boole関数
  • bit-vector用 bit-*系関数
• ビット演算に関する有用な情報源
  
  • 整数の論理演算とビット操作(M.Hiroi’s Home Page)
  • CLの学習:ビット操作(Common LISP users jp)
  • Successfull Lisp - Chapter 18 - Very Logical, Indeed…
  • 書籍：PAIP本 : 実用 Common Lisp
  • 74ページ , ビット演算とビットベクターについての話題あり
  • Bitwise operations (Rosetta code)
  • 参考：Scheme での例 SRFI-60 - 整数とビット
• bit-vector関連
  
  • coerce関数(Hyperspec)
  • Convert integer to bit array and vice versa? (LispForum)
  • LOUDS++(4): bit-vector
  • Efficient Implementation of Bit-vector Operations in Common Lisp
  • bit-smasher
  • bit-vector と整数値の相互変換ライブラリ, quicklisp登録あり
  • How do I convert an integer to a list of bits?(Common Lisp Tips)
  • 「オフラインリアルタイムどう書く」をLispで
  • いくつかの問題で bit-vector, ビット演算をつかっておられます。

全カットでお送りします

CommonLisp における整数値のビット演算 -> log*系関数, boole関数

logand, logior (or演算), logxor, lognotなどビット演算処理が一通りそろっている。逆引きのビット演算の項目として書いた

あと、boole 関数はlog関数と同じことを「オペレータを指定して」できる。よく見ると、boole のほうが少し処理の種類が多い。なんとなく、遺伝プログラムとか人工知能などといったプログラム生成の論理処理用に作られたのでは？と想像した。データとして演算が扱えるということで。逆引きのビット演算の項目の中に一緒に書いた。

bit-vectorを使うという選択肢 -> bit-*系関数

bit-vector についてはそこまで調べていない。

• ビットベクターのリテラル表記は #*10110100 のように、 #* から始める
• bit-vector 同士の演算は、bit-*系関数 を使う
  
  • ほぼすべての種類の演算がそろっている
  • vector なので、シーケンス関連の関数が一通り使える
• ビットベクターと整数との相互変換を扱う標準の方法は、無いといってよい
  
  • coerce 関数 を使う方法があるらしいことはわかった
• ライブラリ bit-smasher がある
  
  • 整数値、文字列、ビットベクタとの相互変換ライブラリ

log* 系関数でのビット演算と負の数値について

まとめというには長い記事になったので、別の記事 としてまとめた。

概要としては

1. なんで (format t "~b" (lognot 8)) ;-> -1001 となるのだろう？
   
   • 自分が表示してほしい値は 1011 とか 1111 1011 なのだが？
2. あ、整数値は無限に長いので表現が無理なのか、え？でも 1001 と 1011 ではだいぶ違うけど、、
3. ああ、、、符号部と整数部が分かれて表示されているのか、、、
4. これは、、仕様っぽい、、、しょうがない、ちょっと考えるか、、、

そういうわけでいろいろ考えた結果、負の整数値でもビット値として表示できる次の関数を作ってみた。

(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

とはいえこの関数では

• format 関数に統合したい
• lognot のビット反転の値と反転前の値の桁数が現状そろわない
• 固定桁数での表示をしたい

などいくつかの自分ニーズに応えられていないので、今後の改良が待たれる。

Written with StackEdit.
Written with ATOM