For Development HEAD DRAFTSearch (procedure/syntax/module):

Next: , Previous: , Up: ライブラリモジュール - Gauche拡張モジュール   [Contents][Index]

9.3 gauche.bitvector - ビットベクタユーティリティ

このモジュールは、ビットベクタを扱う多くの操作を提供します。 このモジュールの手続きと組み込みのビットベクタ手続きは、SRFI-178のスーパーセットに なっています (srfi.178 - ビットベクタライブラリ参照)。

Module: gauche.bitvector

Gaucheはビットベクタを組み込みでサポートしていますが、コアで提供されるのは ごく基本的な手続きのみです(ビットベクタ参照)。 このモジュールではビットベクタに対する包括的な操作を提供します。

コンストラクタ

Function: bitvector-unfold f length seed …
Function: bitvector-unfold-right f length seed …

[SRFI-178]{gauche.bitvector} 長さlengthのビットベクタを作り、その内容をfを繰り返し呼ぶことで 埋めて行きます。fseed …に与えられた引数の数よりひとつ多い 引数を取り、同じ数の戻り値を返します。まず、fはインデックスおよびseed … を引数として呼び出され、戻り値の最初の値(それはビット、すなわち0, 1, 真偽値のいずれかでなければなりません)がビットベクタのインデックス位置の値にセットされます。 次のfは、新たなインデックスおよび残りの戻り値を引数として呼び出されます。 これがlength回繰り返されます。

bitvector-unfoldはビットを左から右に、 bitvector-unfold-rightは右から左に埋めて行きます。

(use math.prime)
(bitvector-unfold (^[index n]
                    (values (small-prime? n) (+ n 1)))
                  20 0)
  ⇒ #*00110101000101000101
(bitvector-unfold-right (^[index n]
                          (values (small-prime? n) (+ n 1)))
                        20 0)
  ⇒ #*10100010100010101100

註: この手続きはvector-unfoldのプロトコルに準じています (scheme.vector - R7RSベクタ参照)。 他のunfoldのプロトコルとは異なることに注意してください (scheme.list - R7RSリスト参照)。

Function: bitvector-reverse-copy bv :optional start end

[SRFI-178]{gauche.bitvector} ビットベクタbvの、順序を逆にしたものを新に作って返します。 省略可能なstartend引数は入力の範囲を制限します。

(bitvector-reverse-copy #*10110011100011110000 4 16)
  ⇒ #*111100011100
Function: bitvector-append bv …

[SRFI-178]{gauche.bitvector} 全ての引数はビットベクタでなければなりません。全てのビットベクタをつなげたビットベクタを 新たに作って返します。

Function: bitvector-concatenate bvs

[SRFI-178]{gauche.bitvector} 引数はビットベクタのリストでなければなりません。 その全てのビットベクタをつなげたビットベクタを新にたに作って返します。

Function: bitvector-append-subbitvectors bv start end …

[SRFI-178]{gauche.bitvector} 引数の総数は3の倍数でなければなりません。それぞれの三つ組は、 ビットベクタと、そのビットベクタに対する開始インデックス、終了インデックスです。 それぞれのビットベクタの、インデックスで指定される範囲を抜き出したものを つなげたビットベクタを新たに作って返します。

(bitvector-append-subbitvectors
  #*11100011 2 6
  #*01010101 3 8)
 ⇒ #*100010101

述語

Function: bitvector-emtpy? bv

[SRFI-178]{gauche.bitvector} bvが空のビットベクタなら#tを、空でないビットベクタなら#fを返します。 bvがビットベクタでなければエラーが投げられます。

Function: bitvector=? bv …

[SRFI-178]{gauche.bitvector} 全ての引数はビットベクタでなければなりません。 全てのビットベクタが同じ長さ、同じ内容なら#tを、そうでなければ#fを返します。 引数が0個もしくは1個の場合は#tを返します。

繰り返し

Function: bitvector-take bv n
Function: bitvector-take-right bv n

[SRFI-178]{gauche.bitvector} ビットベクタbvの最初から/終わりのnビットを切り出した新たなビットベクタを 返します。bvの長さがnより小さければエラーが投げられます。

Gaucheではジェネリックな(subseq bv 0 n)で最初のnビットを 切り出すこともできます (gauche.sequence - シーケンスフレームワーク参照)。

Function: bitvector-drop bv n
Function: bitvector-drop-right bv n

[SRFI-178]{gauche.bitvector} ビットベクタbvの最初から/終わりのnビットを取り除いた新たなビットベクタを 返します。bvの長さがnより小さければエラーが投げられます。

Gaucheではジェネリックな(subseq bv n)で最初のnビットを 取り除いたビットベクタを得ることもできます (gauche.sequence - シーケンスフレームワーク参照)。

Function: bitvector-segment bv n

[SRFI-178]{gauche.bitvector} ビットベクタbvnビットごとの切片に切り分け、 それぞれを新たなビットベクタにしたもののリストを返します。 bvnの倍数でなければ、最後のビットベクタはnビット未満になります。

Function: bitvector-fold/int kons knil bv1 bv2 …
Function: bitvector-fold/bool kons knil bv1 bv2 …
Function: bitvector-fold-right/int kons knil bv1 bv2 …
Function: bitvector-fold-right/bool kons knil bv1 bv2 …

[SRFI-178]{gauche.bitvector} 状態値を受け渡しながら、konsをビットベクタの各要素に適用してゆきます。 knilは最初の状態値です。

kons(kons state e1 e2 …)のように 呼び出されます。ここでe1 e2 … は引数の各ビットベクタの対応する 要素を取り出したものです (/intの手続きでは0/1、/boolの手続きでは #f/#t)。 これはscheme.vectorモジュールのvector-foldと同じ引数順です (scheme.vector - R7RSベクタ)。 (リストについてのfold手続きではkons手続きの最後の引数として 状態値が渡されることに注意してください。リストをたどる手続き参照)。

引数の全てのビットベクタは同じ長さでなければなりません。 そうでなければエラーが投げられます。

Function: bitvector-map/int f bv1 bv2 …
Function: bitvector-map/bool f bv1 bv2 …

[SRFI-178]{gauche.bitvector} 手続きfを与えられたビットベクタから取り出したビットに対して適用し、 その結果を新たなビットベクタにまとめて返します。

(bitvector-map/int logand #*10101 #*00111)
  ⇒ #*00101

引数の全てのビットベクタは同じ長さでなければなりません。 そうでなければエラーが投げられます。

Function: bitvector-map!/int f bv1 bv2 …
Function: bitvector-map!/bool f bv1 bv2 …

[SRFI-178]{gauche.bitvector} 手続きfを与えられたビットベクタから取り出したビットに対して適用し、 その結果をbv1に破壊的代入します。

これらの手続きは未定義値を返します。呼び出し側はbv1への副作用を使わなければ なりません。言い換えれば、これらの手続きは線形更新手続きではありません。

引数の全てのビットベクタは同じ長さでなければなりません。 そうでなければエラーが投げられます。

Function: bitvector-map->list/int f bv1 bv2 …
Function: bitvector-map->list/bool f bv1 bv2 …

[SRFI-178]{gauche.bitvector} 手続きfを与えられたビットベクタから取り出したビットに対して適用し、 その結果をリストに集めて返します。

引数の全てのビットベクタは同じ長さでなければなりません。 そうでなければエラーが投げられます。

Function: bitvector-value-map-index->list f bv val

{gauche.bitvector} ビットベクタbvの要素のうち、それがvalとビットとして 一致するもの (#t1なら真と一致、#f0なら偽と一致) について、それぞれそのインデックスを引数に手続きfを呼びます。結果は インデックスの小さい順にリストに集められて返されます。

下の例はビットベクタのビットが真であるインデックスのリストを返します。

(bitvector-value-map-index->list identity #*10011 #t)
  ⇒ (0 3 4)
Function: bitvector-for-each/int f bv1 bv2 …
Function: bitvector-for-each/bool f bv1 bv2 …

[SRFI-178]{gauche.bitvector} 与えられたビットベクタの各ビットに対してfを適用します。fの結果は捨てられます。

引数の全てのビットベクタは同じ長さでなければなりません。 そうでなければエラーが投げられます。

(bitvector-for-each/int print #*11100 #*01110 #00111)
  ⇒ prints
100
110
111
011
001
Function: bitvector-value-for-each-index f bv val

{gauche.bitvector} bvの各ビットを最初から走査し、そのビットがvalとビットとして一致したものについて、 そのインデックスを引数にfを呼び出します。fの結果は捨てられます。

(bitvector-value-for-each-index print #*1101111010 #f)
 ⇒ prints
2
7
9

上のbitvector-value-map-index->listも参照。

プレフィクス、サフィックス、トリム、パディング

Function: bitvector-prefix-length bv1 bv2
Function: bitvector-suffix-length bv1 bv2

[SRFI-178]{gauche.bitvector} 二つのビットベクタbv1bv2に共通するプレフィクスまたはサフィックスの 長さを返します。

(bitvector-prefix-length #*1100101001 #*110001101) ⇒ 4
(bitvector-suffix-length #*1100101001 #*110001101) ⇒ 2
Function: bitvector-prefix? needle haystack
Function: bitvector-suffix? needle haystack

[SRFI-178]{gauche.bitvector} 引数はどちらもビットベクタでなければなりません。 needlehaystackのプレフィックスまたはサフィックスになっている時に #tを、そうでなければ#fを返します。

(bitvector-prefix? #*101 #*1010100) ⇒ #t
(bitvector-prefix? #*101 #*1000110) ⇒ #f
(bitvector-suffix? #*110 #*1000110) ⇒ #t
(bitvector-suffix? #*110 #*1010100) ⇒ #f
Function: bitvector-pad bit bv len
Function: bitvector-pad-right bit bv len

[SRFI-178]{gauche.bitvector} ビットベクタbvの長さがlen未満であれば、 長さがlenになるまでbvの先頭もしくは末尾にbitを付加した ビットベクタを作って返します。bvの長さがlenより大きな場合は 長さlenになるまでbvの先頭もしくは末尾のビットを削ったビットベクタを 作って返します。lenbvの長さと同じなら、bvのコピーが 返されます。

(bitvector-pad 1 #*00010 10) ⇒ #*1111100010
(bitvector-pad-right 1 #*00010 10) ⇒ #*0001011111

(bitvector-pad 1 #*0100011 3) ⇒ #*011
(bitvector-pad-right 1 #*0100011 3) ⇒ #*010
Function: bitvector-trim bit bv
Function: bitvector-trim-right bit bv
Function: bitvector-trim-both bit bv

[SRFI-178]{gauche.bitvector} ビットベクタbvの先頭、末尾、あるいは両方から、連続するbitをできる限り 除いたビットベクタを新たに作って返します。

(bitvector-trim 0 #*000101000) ⇒ #*101000
(bitvector-trim-right 0 #*000101000) ⇒ #*000101
(bitvector-trim-both 0 #*000101000) ⇒ #*101

破壊的変更

Function: bitvector-swap! bv i j

[SRFI-178]{gauche.bitvector} ビットベクタbvi番目とj番目のビットを入れ替えます。 戻り値は未定義です。 インデックスが範囲外であればエラーが投げられます。

Function: bitvector-reverse! bv :optional start end

[SRFI-178]{gauche.bitvector} ビットベクタbvのビット順を破壊的に反転します。 省略可能なstart/endが与えられた場合は、 それらのインデックスで指定される範囲内だけが変更対象となります。 戻り値は未定義です。

Function: bitvector-reverse-copy! to tstart from :optional start end

[SRFI-178]{gauche.bitvector} (bitvector-copy! to start (bitvector-reverse-copy from start end)) と意味的に同じですが、より効率が良いかもしれません。 戻り値は未定義です。

変換

Function: bitvector->list/int bv :optional start end
Function: bitvector->list/bool bv :optional start end
Function: reverse-bitvector->list/int bv :optional start end
Function: reverse-bitvector->list/bool bv :optional start end

[SRFI-178]{gauche.bitvector} ビットベクタbvの内容を整数0または1のリスト、あるいは真偽値のリストとして 返します。最初の2つの手続きは左から、reverse-のつく2つの手続きは 右からビットを取ります。省略可能なstart/end引数は 取り出すビットの範囲を指定します。

(bitvector->list/int #*010011000111 2 10)
 ⇒ (0 0 1 1 0 0 0 1)
(reverse-bitvector->list/int #*010011000111 2 10)
 ⇒ (1 0 0 0 1 1 0 0)
Function: reverse-list->bitvector lis

[SRFI-178]{gauche.bitvector} list->bitvector(ビットベクタ参照)と似ていますが、 ビットを右から左に詰めてゆきます。

(reverse-list->bitvector '(1 0 #f #f #t #t))
 ⇒ #*110001
Function: bitvector->vector/int bv :optional start end
Function: bitvector->vector/bool bv :optional start end
Function: revrese-bitvector->vector/int bv :optional start end
Function: reverse-bitvector->vector/bool bv :optional start end

[SRFI-178]{gauche.bitvector} ビットベクタbvの内容を整数0または1のベクタ、あるいは真偽値のベクタとして 返します。最初の2つの手続きは左から、reverse-のつく2つの手続きは 右からビットを取ります。省略可能なstart/end引数は 取り出すビットの範囲を指定します。

Function: vector->bitvetor vec :optional start end
Function: reverse-vector->bitvector vec :optional start end

[SRFI-178]{gauche.bitvector} ベクタvecを新たなビットベクタに変換します。vecの要素は 0、1、あるいは真偽値でなければなりません。 最初の手続きはビットを左から右に同じ順で、reverse-のつく手続きは 逆順で詰めてゆきます。 省略可能なstart/end引数はvecから取り出すビットの範囲を指定します。

(vector->bitvector #(0 0 1 1 #t #f #t #t) 2 7)
  ⇒ #*11101
(reverse-vector->bitvector #(0 0 1 1 #t #f #t #t) 2 7)
  ⇒ #*10111
Function: bitvector->integer bv
Function: integer->bitvector n :optional len

[SRFI-178]{gauche.bitvector} ビットベクタと正確な非負整数とを相互変換します。 bvの最初(最左)のビットは、整数の最下位のビットに対応することに注意してください。

(bitvector->integer #*1000) ⇒ 1
(bitvector->integer #*0001) ⇒ 8

SRFI-151のbits->list等は最下位ビットから順にビットをリストにするので、 それと一貫性があります(scheme.bitwise - R7RSビット演算参照)。

integer->bitvectorはさらに省略可能なlen引数で、 引数の整数nの最下位から何ビット目までを取るかを指定できます。 省略時は(integer-length n)の値が使われます (基本的なビット演算参照)。

(integer->bitvector 11)   ⇒ #*1101
(integer->bitvector 11 8) ⇒ #*11010000

ジェネレータ

Function: bitvector->int-generator bv :optional start end
Function: bitvector->bool-generator bv :optional start end

{gauche.bitvector} それぞれ、整数0か1を生成するジェネレータと真偽値を生成するジェネレータを返します。 値はビットベクタbvの左から右へと取られます。 省略可能なstart/end引数はvecから取り出すビットの範囲を指定します。

(generator->list (bitvector->int-generator #*10111000))
 ⇒ (1 0 1 1 1 0 0 0)

これらの名前はGaucheの名前付けと一貫性があります。 SRFI-178ではこれらを make-bitvector/int-generatorおよびmake-bitvector/bool-generator と呼んでいます。

ジェネレータについて詳しくはgauche.generator - ジェネレータを参照してください。

Function: make-bitvector/int-generator bv
Function: make-bitvector/bool-generator bv

[SRFI-178]{gauche.bitvector} これらは省略可能引数を取らないことを除いて、 それぞれbitvector->int-generatorおよびbitvector->bool-generator と同じです。SRFI-178で定義されました。

Function: bitvector->index-generator bv val :optional start end

{gauche.bitvector} ビットベクタbvのうち、値がvalと一致するビットのインデックスを 左から右への順番で生成するジェネレータを返します。 valは0, 1, #f, #tのいずれかでなければなりません。 省略可能なstart/end引数はvecから取り出すビットの範囲を指定します。

これは、ビットベクタをビットマップとして使い、 ビットがセットされている/されていない要素について何かする、といった場合に便利です。

(generator->list (bitvector->index-generator #*101110001 1))
 ⇒ (0 2 3 4 8)
Function: make-bitvector-accumulator

[SRFI-178]{gauche.bitvector} 与えられたビットを蓄積し、最後にビットベクタを作って返すアキュムレータを返します。

(let ((a (make-bitvector-accumulator)))
  (a 1)
  (a 0)
  (a 0)
  (a 1)
  (a 1)
  (a (eof-object)))
  ⇒ #*10011

アキュムレータについて詳しくはscheme.generator - R7RSジェネレータを参照してください。

ビット演算

Function: bitvector-not bv
Function: bitvector-not! bv

[SRFI-178]{gauche.bitvector} ビットベクタbvの各ビットを反転したビットベクタを返します。 線形更新版のbitvector-not!は、結果を作るために bvを破壊的に変更するかもしれません。

(bitvector-not #*10100) ⇒ #*01011
Function: bitvector-and bv1 bv2 bv …
Function: bitvector-and! bv1 bv2 bv …
Function: bitvector-ior bv1 bv2 bv …
Function: bitvector-ior! bv1 bv2 bv …
Function: bitvector-xor bv1 bv2 bv …
Function: bitvector-xor! bv1 bv2 bv …
Function: bitvector-eqv bv1 bv2 bv …
Function: bitvector-eqv! bv1 bv2 bv …

[SRFI-178]{gauche.bitvector} 与えられたビットベクタの各ビット間に指定の演算を施した結果を要素とするビットベクタを 返します。引数のビットベクタは全て同じ長さでなければなりません。 線形更新版(名前に!がついているもの)は、 結果を作るためにbv1を破壊的に変更するかもしれません。

3つ以上のビットベクタが与えられた場合、xorとeqv操作は左結合的に行われます。すなわち:

(bitvector-xor a b c)
 ≡ (bitvector-xor (bitvector-xor a b) c)
(bitvector-eqv a b c)
 ≡ (bitvector-eqv (bitvector-eqv a b) c)
Function: bitvector-nand bv1 bv2
Function: bitvector-nand! bv1 bv2
Function: bitvector-nor bv1 bv2
Function: bitvector-nor! bv1 bv2
Function: bitvector-andc1 bv1 bv2
Function: bitvector-andc1! bv1 bv2
Function: bitvector-andc2 bv1 bv2
Function: bitvector-andc2! bv1 bv2
Function: bitvector-orc1 bv1 bv2
Function: bitvector-orc1! bv1 bv2
Function: bitvector-orc2 bv1 bv2
Function: bitvector-orc2! bv1 bv2

[SRFI-178]{gauche.bitvector} bv1bv2の対応する各ビットに演算を施した結果をビットベクタにして返します。 bv1bv2は同じ長さでなければなりません。

nand  : (not (and bv1 bv2))
nor   : (not (or bv1 bv2)
andc1 : (and (not bv1) bv2)
andc2 : (and bv1 (not bv2))
orc1  : (or (not bv1) bv2)
orc2  : (or bv1 (not bv2))

線形更新版(名前に!がついているもの)は、 結果を作るためにbv1を破壊的に変更するかもしれません。

整数に準ずる演算

Function: bitvector-logical-shift bv count bit

[SRFI-178]{gauche.bitvector} bvを左にcountビットシフトした、bvと同じ長さのビットベクタを 返します。countが負の場合は-countビット右にシフトします。 あふれたビットは捨てられます。空き部分のビットはbitで埋められます。

(bitvector-logical-shift #*101100111000 4 1)
  ⇒ #*001110001111
(bitvector-logical-shift #*101100111000 -4 0)
  ⇒ #*000010110011
Function: bitvector-count bit bv

[SRFI-178]{gauche.bitvector} bv中のビットで、bitと一致するものの数を返します。

Function: bitvector-count-run bit bv start

[SRFI-178]{gauche.bitvector} bv中の、iビット目からbitがいくつ連続しているか、その数を返します。

(bitvector-count-run 1 #*11111111100 0)
 ⇒ 9
Function: bitvector-if bv-if bv-then bv-else

[SRFI-178]{gauche.bitvector} 各ビットベクタは同じ長さでなければなりません。 同じ長さのビットベクタを次のように構成して返します。

結果のkビット目は、bv-ifkビット目が#t(1)であれば bv-thenkビット目、そうでなければbv-elsekビット目と 同じになります。

Function: bitvector-first-bit bit bv

[SRFI-178]{gauche.bitvector} bv中で一番左にあるbitのインデックスを返します。 bv中にbitが無ければ-1を返します。

(bitvector-first-bit 1 #*0010011) ⇒ 2
(bitvector-first-bit 0 #*1111111) ⇒ -1

ビットフィールド操作

以下の手続きは、ビットベクタの startビット目(含む)からendビット目(含まない)までの部分について 操作するものです。

Function: bitvector-field-any? bv start end

[SRFI-178]{gauche.bitvector} ビットベクタbvstartビット目からendビット目までのいずれかに 1のビットがあれば#tを、そうでなければ#fを返します。

Gaucheの組み込み手続きを使って (bitvector-any-value? bv 1 start end)とした場合と同じです (ビットベクタ参照)。

Function: bitvector-field-every? bv start end

[SRFI-178]{gauche.bitvector} ビットベクタbvstartビット目からendビット目までのすべてが 1であれば#tを、そうでなければ#fを返します。

Gaucheの組み込み手続きを使って (bitvector-every-value? bv 1 start end)とした場合と同じです (ビットベクタ参照)。

Function: bitvector-field-clear bv start end
Function: bitvector-field-clear! bv start end
Function: bitvector-field-set bv start end
Function: bitvector-field-set! bv start end

[SRFI-178]{gauche.bitvector} ビットベクタbvの内容のうち、 startビット目からendビット目までのすべてがクリアされた、 あるいはセットされたビットベクタをそれぞれ返します。

線形更新版は結果を作るためにbvを破壊的に変更するかもしれません。

(bitvector-field-clear #*10010010101001 2 7)
 ⇒ #*10000000101001
(bitvector-field-set #*10010010101001 2 7)
 ⇒ #*10111110101001
Function: bitvector-field-replace to from start end
Function: bitvector-field-replace! to from start end

[SRFI-178]{gauche.bitvector} ビットベクタbvの内容のうち、 startビット目からendビット目までを、 from-bvの内容で置き換えたビットベクタを返します。

from-bvの長さは少なくともend-startだけなければなりません。 from-bvがそれより長い場合、余分なビットは無視されます。

線形更新版は結果を作るためにbvを破壊的に変更するかもしれません。

(bitvector-field-replace #*10010010101001 #*110011 2 8)
 ⇒ #*10110011101001

下のbitvector-field-replace-sameも参照のこと。

Function: bitvector-field-replace-same to-bv from-bv start end
Function: bitvector-field-replace-same! to-bv from-bv start end

[SRFI-178]{gauche.bitvector} ビットベクタbvの内容のうち、startビット目からendビット目までを、 from-bvstartビット目からendビット目までで置き換えたものを返します。

from-bvの長さはendより大きくなければなりません。

線形更新版は結果を作るためにbvを破壊的に変更するかもしれません。

(bitvector-field-replace-same #*10010010101001 #*11001100 2 8)
 ⇒ #*10001100101001

上のbitvector-field-replaceも参照のこと。

Function: bitvector-field-rotate bv count start end

[SRFI-178]{gauche.bitvector} ビットベクタbvの内容のうち、startビット目からendビット目までが countビットだけ右にローテートされた内容に置き換えられているものを返します。 countが負なら、その絶対値分だけ左にローテートします。

(bitvector-field-rotate #*001100110011 1 4 8)
 ⇒ #*001101100011
(bitvector-field-rotate #*001100110011 -1 4 8)
 ⇒ #*001110010011
Function: bitvector-field-flip bv start end
Function: bitvector-field-flip! bv start end

[SRFI-178]{gauche.bitvector} ビットベクタbvの内容のうち、startビット目からendビット目までの ビットが論理否定されているものを返します。

線形更新版は結果を作るためにbvを破壊的に変更するかもしれません。

(bitvector-field-flip #*001100110011 4 8)
 ⇒ #*001111000011

Next: , Previous: , Up: ライブラリモジュール - Gauche拡張モジュール   [Contents][Index]


For Development HEAD DRAFTSearch (procedure/syntax/module):
DRAFT