【Common Lisp】
ビット演算の基本の使い方
（bignumとsimple-bit-vector）

by
  • Common Lispでは整数のビット演算にlogand/logior/logxor/lognot/ash/logbitpなどを使います。
  • 整数は桁に重みがあり、ashによるシフトやldb/dpbによるビットフィールド操作など計算用途に向いています。
  • simple-bit-vectorはインデックスで要素を参照するフラグ集合として使い、bit-and/bit-iorなどで集合演算ができます。
  • 整数とsimple-bit-vectorは相互変換できますが、変換関数は標準にないため自前で書きます。

関連記事

1. ビット演算が役に立つとき

ビット演算は、コンピュータのデータの最小単位、ビットを直接操作します。

2の冪乗に絡む乗除算をシフトで置き換えたり、複数の状態を1つの整数にまとめて管理したり、ビットの特性を活用すると効率的に計算できることがあります。

たとえば、累乗を速く計算するための「繰り返し二乗法」です。

long long pow_int(long long x, unsigned long long n)
{
    long long ans;
    for (ans = 1; n; n >>= 1, x *= x)
        if (n & 1) ans *= x;
    return ans;
}Code language: Arduino (arduino)

n 乗をまともに n 回かけるのではなく、二乗を使って繰り返し計算を減らします。
これを Common Lispで書くと、

(defun pow (x n)
  (loop with ans = 1
        for base = x then (* base base)
        for exp = n then (ash exp -1)
        while (plusp exp)
        when (logbitp 0 exp)
          do (setf ans (* ans base))
        finally (return ans)))
;; (pow 4 3) ;=> 64        Code language: Lisp (lisp)

ashやlogbitpがビット演算の関数です。

Common Lispには、「整数値のビット演算」だけでなく、「simple-bit-vector」という2つの方法が用意されています。

  • 整数は、ビットを「桁」として扱い、シフトや計算と組み合わせる場面に向いています。
  • simple-bit-vectorは、ビットを「インデックス付きの要素」として扱い、フラグ集合を抽象化する場面に向いています。

1.1. Common Lispのビット演算とC言語

整数値のビット演算は、C言語でのビット演算と同じように考えることができます。

Cでビット演算といえば、intやunsigned intに対して&/|/^/~/<</>>を使います。

int flags = 0;
flags |= (1 << 3);   /* 3番目のビットを立てる */
flags &= ~(1 << 3);  /* 3番目のビットを消す */
int val = flags & (1 << 3);  /* 3番目のビットを調べる */Code language: Arduino (arduino)

Common Lispでも同じ操作ができます。

(let ((flags 0))
  (setf flags (logior flags (ash 1 3))) 
  (setf flags (logand flags (lognot (ash 1 3)))) 
  (let ((val (logand flags (ash 1 3)))) 
    val))Code language: Lisp (lisp)
C言語なら数値のビット演算simple-bit-vector
&logandbit-and
|logiorbit-ior
^logxorbit-xor
~lognotbit-not
&logbitparef
<< / >>ash
&ldb
&dpbsetf aref
make-array :element-type 'bit
simple-bit-vector-p

1.2. fixnumとbignum（任意精度）

整数の型によって、何桁のビットを扱えるかが変わります。

Cのintは固定幅ですが、Common Lispの整数は、基本的に任意精度です。

fixnumは、1ワード（SBCLの64bit環境では62ビット分）で扱える整数です1。

fixnumの範囲を超えると、自動的にbignumに昇格します。

most-positive-fixnum
;=> 4611686018427387903  ; 2^62 - 1

(integer-length most-positive-fixnum)
;=> 62

(type-of (1+ most-positive-fixnum))
;=> BIGNUMCode language: Lisp (lisp)

bignumでの演算は、ビット幅に比例して重くなりますが、メモリが許す限り大きくなります。
たとえば、100万ビットの整数でも扱えます2。

(integer-length (expt 2 1000000))
;=> 1000001Code language: Lisp (lisp)

2. 整数のビット演算

2.1. 数値のバイナリリテラル（#b）

数値は、ビットでも書くことができます。
#bは、バイナリリテラルのプレフィックスです。

#b1100
;;=> 12

(format t "~b" 13)
;;-> 1101Code language: Lisp (lisp)

#b1100は2進数の1100、つまり10進数の12を表します。
Common Lispでは#bのほかに#o（8進）・#x（16進）も使えます。

2.2. logand / logior / logxor / lognot

基本の論理演算です。

(logand #b1100 #b1010)
;=> 8   ; #b1000

(logior #b1100 #b1010)
;=> 14  ; #b1110

(logxor #b1100 #b1010)
;=> 6   ; #b0110

(lognot #b0011)
;=> -4  ; 2の補数表現での補数Code language: Lisp (lisp)

lognotの結果が負になるのは、Common Lispの整数が2の補数で無限に符号ビットが続くものとして扱われるためです3。

2.3. ashでビットをシフトする

ashは、算術シフト（Arithmetic Shift）です。

正の数で左シフト、負の数で右シフトします4。

(ash 1 4)    ;=> 16   ; 1を4ビット左シフト（2^4）
(ash 16 -2)  ;=> 4    ; 16を2ビット右シフト（16 / 4）
(ash #b1010 1)  ;=> 20  ; #b10100Code language: Lisp (lisp)

ashは、2の冪乗の掛け算や割り算と同じように使えますが、ビット演算では、「桁」を指定するためにも使われます。

(defun align-down (n alignment)
  (ash (ash n (- (integer-length (1- alignment))))
       (integer-length (1- alignment))))
;; (align-down 1234 800) ;=> 1024Code language: Lisp (lisp)

2.4. logbitpでビットを調べる

logbitpは、整数の指定ビットが1かどうかを返します。

(logbitp 0 #b1010)  ;=> NIL  ; 0番目のビット
(logbitp 1 #b1010)  ;=> T    ; 1番目のビット
(logbitp 3 #b1010)  ;=> T    ; 3番目のビットCode language: Lisp (lisp)

フラグの確認に使うパターンです。

(defun flag-set-p (mask i)
  (logbitp i mask))

(defun set-flag (mask i)
  (logior mask (ash 1 i)))

(defun clear-flag (mask i)
  (logand mask (lognot (ash 1 i))))

(let ((mask 0))
  (setf mask (set-flag mask 2))
  (setf mask (set-flag mask 5))
  (list mask
        (flag-set-p mask 2)
        (flag-set-p mask 3)))
;=> (36 T NIL)Code language: Lisp (lisp)

2.5. ldbとdpbでビット範囲を読み書きする

ldbは、load byteの略で、整数から指定したビット範囲を取り出します。

;; 8ビットの下位4ビットを取り出す
(ldb (byte 4 0) #b10101100)
;=> 12  ; #b1100

;; 2ビット幅を4ビット目から取り出す
(ldb (byte 2 4) #b11110000)
;=> 3  ; #b11Code language: Lisp (lisp)

(byte size position)でビットフィールドを指定します5。

ldbは、lognotした整数から下位ビットを取り出すときにも使えます。

;; 8ビットの範囲でlognot
(ldb (byte 8 0) (lognot #b00001111))
;=> 240  ; #b11110000Code language: Lisp (lisp)

dpbは、deposit byteの略で、整数の指定ビット範囲に値を書き込みます6。

;; 4ビット目から2ビット幅に #b10 を書き込む
(dpb #b10 (byte 2 4) #b00000000)
;=> 32  ; #b00100000Code language: Lisp (lisp)

3. simple-bit-vectorの基本

整数のビットは「桁」であり、位置が重みを持ちます。
一方、simple-bit-vectorのビットは「インデックス付きの要素」です。

要素が1かどうか、フラグの集合として扱うのに向いていて、基本的には、位置間の大小関係や重みを使わないことが多いです。

3.1. 作成とリテラル（make-array ‘bit）

make-arrayに、:element-type 'bitを指定して作ります。

(make-array 8 :element-type 'bit :initial-element 0)
;=> #*00000000Code language: Lisp (lisp)

#*で始まるリテラルでも書けます7。
桁が右から進むのに対して、bit-vectorは、左端が 0 番目の要素（インデックス0）として扱われます。

(aref #*10110100 0)  ;=> 1
(aref #*10110100 1)  ;=> 0
(aref #*10110100 2)  ;=> 1Code language: Lisp (lisp)

3.2. simple-bit-vector-p

型を確認するには、simple-bit-vector-pを使います8。

(simple-bit-vector-p #*1010)
;=> T

(simple-bit-vector-p (make-array 4 :element-type 'bit))
;=> TCode language: Lisp (lisp)

3.3. arefで要素を読み書きする

要素の読み書きは、通常の配列と同じくarefとsetfを使います。

(defparameter *flags* (make-array 8 :element-type 'bit :initial-element 0))

(setf (aref *flags* 2) 1)
(setf (aref *flags* 5) 1)

*flags*
;=> #*00100100

(aref *flags* 2)  ;=> 1
(aref *flags* 3)  ;=> 0Code language: Lisp (lisp)

simple-bit-vectorの要素は0と1の整数値で、論理値のt/nilではありません9。
ですので、条件分岐に使う場合は(= 1 (aref bits i))のように明示的に比較する必要があります。

(= 1 (aref *flags* 2))  ;=> T   ; 比較はこう書くCode language: Lisp (lisp)

4. simple-bit-vectorの論理演算

4.1. bit-and / bit-ior / bit-xor / bit-not

simple-bit-arrayは、配列全体に対して論理演算できます。
これが、集合演算に使いやすいです。

(defparameter *a* #*11001010)
(defparameter *b* #*10101100)

(bit-and *a* *b*)  ;=> #*10001000  ; 積集合
(bit-ior *a* *b*)  ;=> #*11101110  ; 和集合
(bit-xor *a* *b*)  ;=> #*01100110  ; 対称差
(bit-not *a*)      ;=> #*00110101  ; 補集合Code language: Lisp (lisp)

たとえば、bit-andを「AとBの両方で有効なフラグ」を一度の演算で得られます10。

(defun active-in-both (flags-a flags-b)
  (bit-and flags-a flags-b))

(active-in-both #*11001010 #*10101100)
;=> #*10001000Code language: Lisp (lisp)

4.2. 第3引数で破壊的に書き込む

そのまま、bit-andやbit-orを使うと、そのたびに毎回新しい配列を確保するコストが発生します。

第3引数に結果を受け取るsimple-bit-vectorを渡せば、そこに書き込めます。
第3引数にtを渡すと、第1引数に破壊的に書き込むこともできます11。

繰り返し処理で使うときには、結果をどこに書き込むのか意識しましょう。

(defparameter *result* (make-array 8 :element-type 'bit))

(bit-and *a* *b* *result*)

*result*
;=> #*10001000

(bit-ior *a* *b* t)  ; *a* 自体が更新されるCode language: Lisp (lisp)

4.3. bit-eqv / bit-nand / bit-norなど

bit-and/bit-ior/bit-xor/bit-not以外にも、bit-プレフィックスの論理演算関数が揃っています12。

(bit-eqv  *a* *b*)   ; 同値（XORの否定）
(bit-nand *a* *b*)   ; NANDはbit-andしてbit-not
(bit-nor  *a* *b*)   ; NORはbit-iorしてbit-not
(bit-andc1 *a* *b*)  ; (not a) and b
(bit-andc2 *a* *b*)  ; a and (not b)
(bit-orc1  *a* *b*)  ; (not a) or b
(bit-orc2  *a* *b*)  ; a or (not b)Code language: Lisp (lisp)

5. simple-bit-vectorによるフラグ管理

5.1. フラグ集合とメモリ効率

N個の要素それぞれに「有効か無効か」というフラグを持たせる場合、通常のvectorにt/nilを持つよりも、simple-bit-vectorの方がメモリ効率がよいです。

;; t/nil のベクタ：要素1個あたりポインタ1個分（64bit環境で約8MB）
(make-array 1000000 :initial-element nil)

;; bit-vector：要素1個あたり1ビット（約125KB）
(make-array 1000000 :element-type 'bit :initial-element 0)Code language: Lisp (lisp)

100万要素にもなると、約8MBと約125KBの差になります13。

simple-bit-vectorでのフラグ管理の基本パターンです。

(defun make-flags (n)
  (make-array n :element-type 'bit :initial-element 0))

(defun enable (flags i)
  (setf (aref flags i) 1)
  flags)

(defun disable (flags i)
  (setf (aref flags i) 0)
  flags)

(defun enabled-p (flags i)
  (= 1 (aref flags i)))

(let ((f (make-flags 8)))
  (enable f 1)
  (enable f 4)
  (enable f 6)
  (list f
        (enabled-p f 1)
        (enabled-p f 2)))
;=> (#*01001010 T NIL)Code language: Lisp (lisp)

5.2. 整数マスクとの比較

整数のビットマスクでも同じフラグ管理はできます。

ただし、整数マスクはfixnumの範囲なら高速ですが、フラグ数が62を超えるとbignumになり、多倍長整数の演算になります。
一方、simple-bit-vectorは、フラグ数が多くなっても一定のアクセス速度を保てます14。

もう一つの違いは、simple-bit-vectorはフラグ集合として抽象化されているぶん、コードの意図が読みやすくなります15。

5.3. まとめて演算することで得られる効率

bit-andなどの演算は、内部的にはワード単位で処理されます。

;; 遅い：1ビットずつループ
(defun intersect-slow (a b n)
  (let ((result (make-array n :element-type 'bit)))
    (dotimes (i n result)
      (setf (aref result i)
            (logand (aref a i) (aref b i))))))

;; 速い：ワード単位でまとめて処理
(defun intersect-fast (a b)
  (bit-and a b))Code language: Lisp (lisp)

1ビットずつ Lispレベルでループするより速くなります16。

ただし、1ビットずつarefでアクセスする処理はビットの取り出し処理が入る分、fixnum配列より遅くなることがあります。
全体をまとめて演算するときにsimple-bit-vectorが有利です。

6. 整数とsimple-bit-vectorの相互変換

整数とsimple-bit-vectorを変換するには、変換関数を自前で書く必要があります17。
Common Lispの標準にはありません。

6.1. fill-bit-vector-from-integer

(defun fill-bit-vector-from-integer (bits n)
  (declare (type simple-bit-vector bits))
  (loop for i below (length bits)
        do (setf (aref bits i)
                 (if (logbitp i n) 1 0))
        finally (return bits)))

(fill-bit-vector-from-integer #*0000 5) 
;=> #*1010  ; 右から読むと0101Code language: Lisp (lisp)

6.2. bit-vector->integer

(defun bit-vector->integer (bits)
  (let ((n 0))
    (dotimes (i (length bits) n)
      (when (= 1 (aref bits i))
        (setf n (logior n (ash 1 i)))))))

(bit-vector->integer #*1010)
;=> 5Code language: Lisp (lisp)

6.3. 負数とldbの注意点

integer->bit-vectorは、非負整数を前提にしています。

負の整数はCommon Lispの仕様上、全ビットが符号ビットで無限に続くように扱われるためです18。

(logbitp 100 -1)  ;=> T  ; -1はすべてのビットが1Code language: Lisp (lisp)

負の整数の下位Nビットだけを取り出すにはldbを使います。

;; -1の下位8ビット
(ldb (byte 8 0) -1)
;=> 255  ; #b11111111

(integer->bit-vector (ldb (byte 8 0) -1) 8)
;=> #*11111111Code language: Lisp (lisp)

7. 使い分けの判断基準

シンボル名は、bitsは、整数値にもsimple-bit-vectorにも、ともに使われます。
そのため、型を意識する画面ではあいまいです。

整数をビット列として扱うときには、mask、 flags、bit-mask などの名前がわかりやすく、simple-bit-vectorを使うときは bit-vector、bit-array、bitvec などの名前が使われます。

7.1. 小さなビット集合にはinteger

フラグ数がfixnumの範囲（62）に収まるなら、整数のビット演算が速くて簡単です。

;; N <= 62 程度なら fixnum マスクで十分
(dotimes (mask (ash 1 n))
  (when (logbitp i mask)
    ...))Code language: Lisp (lisp)

状態圧縮DPや部分集合の全探索など、ビット列を数値として扱う計算用途に向いています19。

7.2. 大量フラグにはsimple-bit-vector

フラグ数が多いか、配列全体をまとめて演算したいならsimple-bit-vectorです。

;; 訪問済みフラグ（100万要素）
(defparameter *visited*
  (make-array 1000000 :element-type 'bit :initial-element 0))

(setf (aref *visited* 12345) 1)
(= 1 (aref *visited* 12345))  ;=> TCode language: Lisp (lisp)

グラフの到達可能性、集合演算、大量のフラグ管理に向いています。

7.3. 単一アクセスが多い場合のunsigned-byte配列

1ビットずつarefでアクセスする処理が多く、速度が問題になるなら(unsigned-byte 8)配列も選択肢です。

(make-array 1000000 :element-type '(unsigned-byte 8) :initial-element 0)Code language: Lisp (lisp)

メモリはsimple-bit-vectorの8倍になりますが、要素アクセスのビットマスク処理がなくなります20。

まとめるとこうです。

用途選択肢
小さなビット集合・計算・シフトinteger（fixnum）
fixnumを超えるビット列integer（bignum）
大量フラグ・集合演算simple-bit-vector
1ビットずつアクセスが多く速度優先(unsigned-byte 8) 配列
  1. HyperSpecではfixnumは(signed-byte 16)のスーパータイプであることだけを要求しており、実際の範囲は処理系依存です。SBCLが62ビットなのは、64bitワードの下位2ビットをタグビットとして使うためです。 – CLHS: Type FIXNUM
  2. Common Lispの仕様上、integerの大きさに上限はありません。bignumはfixnumに収まらない整数すべてを指します（(and integer (not fixnum))）。ビット幅wに対してlogandなどの演算はO(w)になります。 – CLHS: Type FIXNUM
  3. 下位ビットだけを取り出すにはldbを使います。CLtL2では「整数は無限のビットベクタとして扱われ、負数は上位が無限に1で続く」と説明されています。(lognot n)は数学的に-1 - nと等価です。 – 12.7. Logical Operations on Numbers（CLtL2）
  4. 算術シフトは符号ビットを保持します。論理シフトと異なり、右シフトで上位に0ではなく符号ビットが入ります。任意精度整数には「上位が無限に続く」という概念しかないため、Common Lispではashのみ定義され、論理シフトは存在しません。 – Arithmetic shift（Wikipedia）
  5. ldbとdpbの名前はDEC PDP-10のアセンブリ命令に由来します。HyperSpecには「dpbという名前はDEC PDP-10のアセンブリ言語命令deposit byteから来ている」と明記されています。byteはデータ型ではなくバイト指定子（byte specifier）を返す関数で、内部表現は処理系依存です。 – CLHS: Function DPB
  6. HyperSpecでは(dpb newbyte bytespec integer)として定義されており、newbyteの下位sビット（sはbytespecのsize）が結果の指定位置に入り、それ以外はintegerのビットがそのまま保たれます。(setf (ldb bytespec place) value)という形でも同じ操作ができます。 – CLHS: Function DPB
  7. HyperSpecではSharpsign Asteriskと呼ばれるリーダーマクロです。#*と#0*はどちらも空のbit-vectorを表します。 – CLHS: 2.4.8 Sharpsign
  8. simple-bit-vectorはbit-vectorのサブタイプです。(simple-array bit (*))と等価で、displaced配列でなく、fill pointerもなく、adjustableでない1次元のbit配列を指します。#*リテラルで生成されるのはsimple-bit-vectorです。 – CLHS: Type SIMPLE-BIT-VECTOR
  9. CLtL2では(integer 0 1)という型にbitという名前が付いていると説明されています。tはbit型ではなく、1もboolean型ではありません。 – Common Lisp the Language, 2nd Edition – Type Specifiers
  10. 集合演算としてのbit-and（積集合）・bit-ior（和集合）・bit-xor（対称差）・bit-not（補集合）という見方は、整数のlogand/logior/logxor/lognotと対応しています。Baker(1990)の論文ではこれらを「integer bit-vector」と「array bit-vector」として同じ演算の2つの表現として整理しています。 – Efficient Implementation of Bit-vector Operations in Common Lisp
  11. HyperSpecではresult-bit-arrayとして第3引数を説明しています。tを渡すと第1引数のbit-arrayが結果を格納する配列として使われます。nilを渡すか省略すると新しいbit-arrayが確保されます。 – CLHS: Function BIT-AND
  12. 整数側のlogand/logiorなどと対応する演算がbit-プレフィックスで用意されています。bit-eqvはXORの否定（XNOR）です。HyperSpecに掲載されているbit系関数はbit-and・bit-andc1・bit-andc2・bit-eqv・bit-ior・bit-nand・bit-nor・bit-not・bit-orc1・bit-orc2・bit-xorの11種類です。 – Efficient Implementation of Bit-vector Operations in Common Lisp
  13. SBCLでは:element-type 'bitを指定すると実際にビット単位で詰めて格納します。汎用vectorは要素1個あたりポインタ1個（64bit環境で8バイト）を使います。100万要素ならbit-vectorは125,000バイト（約122KB）、汎用vectorは8,000,000バイト（約7.6MB）です。 – clustered-intset（Quickdocs）
  14. fixnumのビットマスク演算はレジスタ1個の操作に対応するため、bignumになると多倍長演算が必要になります。一方、simple-bit-vectorへのランダムアクセスはO(1)で、フラグ数に依存しません。ただし1ビットずつのarefはビット取り出し処理が入る分のオーバーヘッドがあります。 – The Common Lisp Cookbook – Numbers
  15. Baker(1990)の論文でも「整数のビット演算とbit-vector演算は同じ操作を異なる表現で行っており、用途に応じた選択が必要」と述べています。logandはビット計算の文脈、bit-andはコレクション操作の文脈で読まれる傾向があります。 – Efficient Implementation of Bit-vector Operations in Common Lisp
  16. Henry Bakerによる1990年のACM論文「Efficient Implementation of Bit-vector Operations in Common Lisp」では、ワード単位処理によってキャラクタ（バイト）操作と比較してワードサイズ分のスピードアップが得られると述べています。同期化（synchronization）処理によってワード境界に揃えてから演算します。 – Efficient Implementation of Bit-vector Operations in Common Lisp
  17. Baker(1990)の論文でも「整数表現とarray表現の間の変換関数は標準化されていない」と指摘しています。Quicklispにはbit-smasherというライブラリがあり、整数とbit-vectorの算術演算や変換を提供しています。 – bit-smasher（GitHub）
  18. CLtL2では負の整数を「0ビットの数が有限で、上位が無限に1で続くビット列」として表現すると説明しています。これはfiniteなsimple-bit-vectorには直接変換できません。ldbで下位Nビットを取り出すことで対処できます。 – 12.7. Logical Operations on Numbers（CLtL2）
  19. 整数のビット列を集合として扱う考え方はCLtL2にも記載されています。「非負整数を集合として表現できる。要素uが集合にあるとき、ビットuが1になる。logior/logand/logxorが和集合・積集合・対称差に対応する」と説明されています。 – 12.7. Logical Operations on Numbers（CLtL2）
  20. (unsigned-byte 8)は0〜255の整数に型を特化させる指定で、SBCLではunboxedな形で格納されます。1要素あたり1バイト使うため、bit-vectorの8倍のメモリが必要です。1ビットずつ頻繁にアクセスする処理では、ビット取り出しのマスク処理が省けるため速くなる場合があります。 – Successful Lisp – Chapter 18