• 参考:「ADIのMUGENメモ」様の「bit演算のメモ」

■bit演算

演算子の基本については該当ページを参照。
演算子の中でbit演算の仕様と応用を簡単に解説。

■bitとは?

大雑把に言うとデータの最小単位のこと。
コンピューター内部のあらゆる情報は0or1の並びで管理されている。
特に数値情報は0,1のまま2進法として記録されている。
bit演算とはその0,1自体を比較する演算である。

MUGENでは整数は32bit-Int型という形式で管理され、
小数を含む場合はFlaot型と呼ばれる特殊な形式になっている。
bit演算が可能なのはInt型に限られる。

なお利用する際は数式の優先度に注意。演算子のページを参照。
優先度はやや低いため、計算の順番を見誤ったりしないように。

+ ■2進法・bit数値の読み方・32bit-Int型について

■2進法・bit数値の読み方

2進法は使う数字が0と1しかないため1+1で一桁上がり10となる。
十進法での2が10、4が100、8が1000、16が10000、32が100000、
64なら1000000、128=10000000、256=100000000、512=1000000000、
1024=10000000000、2048=100000000000、~という具合。
コンピューターではこれらを組み合わせることで大きな数値を記録します。
bit情報 十進法 例えば55はbit数値だと110111になるがそれは
0100000 32
0010000 16
0000000 -- 0のため無し
0000100 4
0000010 2
0000001 1
0110111 55 上記の数値を組み合わせて表されているということ。

■bitの動き

33+4=37という計算をbitで見ると以下のようになる。
100001 33
000100 +4
100101 37
足した桁が0であればそのまま1が入る。1の場合は
010010 18
000010 +2
010100 20
合わさった箇所の桁が1つ上がる。
もちろん上がったbit桁の部分1ならさらに繰り上がりが発生する。
反対に89-24=65という計算のbitを見ると以下のように。
01011001 89
00011000 24
01000001 65
マイナスなので丁度bitの重なる桁は0になっている。
0の部分をマイナスした場合は、
1100001 97
0000011 -3
1011110 94
上側の一番近い1の桁を0にしその1つ下の桁からマイナスした桁まで1にする。
なお、上側に1がない場合は特別な状態となる。

■32bit-Int型について

32bitの内、31bitまでは通常のbit演算だが、
bitの32桁目は-2147483648という数値になっている。
32bit全てが1の場合は、2147483647-2147483648となり-1の数値になる。
11111111111111111111111111111111 -1 32bit-Int型の全て1の場合
- - -
00000000000000000000000000101101 45 この数から
00000000000000000000000010000000 128 この数を引いた場合、
11111111111111111111111110101101 -83 引いた数から上の桁が全て1に。
bitの32桁目は-2147483648のため、31桁目までの2147483565と合わせ
2147483565-2147483648=-83という状態として処理される。
ならもし31bitまで1の数値、2147483647に+1したら?
01111111111111111111111111111111 2147483647
00000000000000000000000000000001 +1
10000000000000000000000000000000 -2147483648
オーバーフローを起こし、マイナス数値に転じてしまう。
なお最初から最大値を超過している場合は、最大値まで補正される
オーバーフローが起きるのは計算によって超えた場合のみ。
ちなみに-1へ+1すると0になる。
11111111111111111111111111111111 -1
00000000000000000000000000000001 +1
00000000000000000000000000000000 0
なお過度のオーバーフローはシステム上なるべく避けたほうが良い。
バグなどを引き起こす可能性もある

■2の冪(べき)

2進法の性質上bitの全ての桁は2の累乗数を表している。
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192…という具合。
その為2倍にするとbitの桁が全て1つ上がり
(1桁目を除き)2で割るとbit桁が全て1下がるという性質を持つ。
例えば、29で比較してみると
0000011101 29 ここから倍にすると
0000111010 58 1の場所が1つ上の桁にズレる。
0001110100 116 さらに2倍しても同様。
0011101000 232 倍にするとbit桁は繰り上がる。
0111010000 464
この仕組みは2の累乗数でかけた場合も同様に、
対応するbitの桁数分増える。
000001101 13 13を
000100000 32 2の5乗である32を乗算すると
110100000 416 32のbit桁まで13のbitがスライドする
この2の5乗で乗算するということは、5回分2倍にするのと同じ計算になる。
そして、掛け算は同じ数の割り算で戻す事ができるように、
bitでも、2で割れば1桁下がり・2の累乗数で割ればその分bitは下の桁へスライドする
1110000 112 bitの一桁目(1)が無ければ、2で割ることができ、
0111000 56
0011100 28
0001110 14
0000111 7 bitの一桁目(1)が出るまで、計算できる。
:|
1101100000000 6912 こんな大きな数値でも下の桁が0で
0000100000000 256 対応する2の累乗数で割れば
0000000011011 27 bitの数値をそのまま下の桁まで下ろせる。
:|
ただしMUGENでは小数が出た場合はbit管理はbit演算の使えないFloat型に切り替わるため、
bit用の割り算には2の累乗数以外を使ってはならないし、
用いる数値のbit桁未満の数値が存在しないことがMUGEN内では前提となる。
一応、小数が出てもT-/Floor()などで切り捨てれば、
1未満になった桁を省くことはできるが、数値そのものが不安定になるので避けるべき。

■剰余と切り捨て

剰余(割り算の余り計算・MUGENでは演算子「%」)を用いると、
110110110 438 ここから
001000000 %64 2の累乗数を割ると、
000110110 54 対応する桁以上を全て消せる。

Floor()と%剰余演算を組み合わせれば
特定した桁範囲のbitのみを取り出す」こともできるが、
そうした計算はbit演算子を用いるほうが確実である。
1101101101011101 56157 この数値から
0000000100000000 /256 をした上でFloor()で囲って小数を消し
0000000011011011 219 その後2で剰余計算をすると
0000000000000001 1 指定したbitの桁が1か0かを確認できる。
のだが
1101101101011101 56157 この数値から
0000000100000000 &256 &「どちらも1」のbit演算を行うと
0000000100000000 256 そのまま指定bitの有無を確認できる。
Float型になると細かい数値が浮動する危険もあるので可能な限りInt型の方が良い。
次の項でbit演算についてを解説する。

+ ■bit演算の読み方

■bit演算の読み方

bit演算とはbitの0,1自体を比較する演算であるわけだが、
mugenで使用出来る演算子は3種類。
「 & 」「 | 」「 ^ 」

基本的に計算式のように左右に数値を置いて使うのだが、
  • 「 & 」ANDは「同じ桁のbitが1であればその桁は1、片方でも0なら0
  • 「 | 」ORは「同じ桁のbitがどちらかでも1ならその桁は1に、両方0なら0
  • 「 ^ 」XORは「同じ桁のbitの片方だけ1ならその桁は1、両方が同じなら0
    • 0&0=0 1&0=0 1&1=1、6&5=4
    • 0|0=0 1|0=1 1|1=1、6|5=7
    • 0^0=0 1^0=1 1^1=0、6^5=3
0110 6 # 0110 6 # 0110 6
0101 &5 # 0101 |5 # 0101 ^5
0100 =4 # 0111 =7 # 0011 =3
基本的には|orと&andしか使わないが、^も応用方法はある。


+ ■32bit-Int型の表

■32bit-Int型の表

数値 21098765432109876543210987654321 桁数 数値・bit桁の住所数値
-2147483648 10000000000000000000000000000000 32 (-2147483648 )
1073741824 01000000000000000000000000000000 31 ( 1073741824 )
536870912 00100000000000000000000000000000 30 ( 536870912 )
268435456 00010000000000000000000000000000 29 ( 268435456 )
134217728 00001000000000000000000000000000 28 ( 134217728 )
67108864 00000100000000000000000000000000 27 ( 67108864 )
33554432 00000010000000000000000000000000 26 ( 33554432 )
16777216 00000001000000000000000000000000 25 ( 16777216 )
8388608 00000000100000000000000000000000 24 ( 8388608 )
4194304 00000000010000000000000000000000 23 ( 4194304 )
2097152 00000000001000000000000000000000 22 ( 2097152 )
1048576 00000000000100000000000000000000 21 ( 1048576 )
524288 00000000000010000000000000000000 20 ( 524288 )
262144 00000000000001000000000000000000 19 ( 262144 )
131072 00000000000000100000000000000000 18 ( 131072 )
65536 00000000000000010000000000000000 17 ( 65536 )
32768 00000000000000001000000000000000 16 ( 32768 )
16384 00000000000000000100000000000000 15 ( 16384 )
8192 00000000000000000010000000000000 14 ( 8192 )
4096 00000000000000000001000000000000 13 ( 4096 )
2048 00000000000000000000100000000000 12 ( 2048 )
1024 00000000000000000000010000000000 11 ( 1024 )
512 00000000000000000000001000000000 10 ( 512 )
256 00000000000000000000000100000000 9 ( 256 )
128 00000000000000000000000010000000 8 ( 128 )
64 00000000000000000000000001000000 7 ( 64 )
32 00000000000000000000000000100000 6 ( 32 )
16 00000000000000000000000000010000 5 ( 16 )
8 00000000000000000000000000001000 4 ( 8 )
4 00000000000000000000000000000100 3 ( 4 )
2 00000000000000000000000000000010 2 ( 2 )
1 00000000000000000000000000000001 1 ( 1 )
0 00000000000000000000000000000000 - ( 0 )
数値 21098765432109876543210987654321 情報 bit住所数値
2147483647 01111111111111111111111111111111 最大値
-2147483648 10000000000000000000000000000000 最小値
-1 11111111111111111111111111111111 全て1
後述するものには不可欠なもの。
単一の基本値であればFloor(2.0** xbit桁数-1x )でbit住所の代用は可能。
基本的には十進法と2進法との互換性を持った電卓ソフトを併用する。


+ ■Var-桁数分割方式について
bit演算はvarの分割管理に有用なのだが、少し補足。

■桁数分割管理について。

T-/Var()に入れる情報を桁数で分割して
単一のVarに複数の情報を入れられるようにすることを
Varの分割管理、桁数分割管理などと呼ぶ。Var圧縮とも。
代表例はT-/Floor()・/・%を用いて十進法の桁数を分割管理する通常の桁数分割管理。

■Var-bit桁数分割方式について

入れる情報をbitの桁数で分割してより無駄なく使うのがbit桁数分割方式。
原理としてはbit桁数で別々に管理するようにする方式で、
bitを1~10・11~20・21~30桁目と分ければ10bit(0~1023)の情報を3つ記録できる
もちろん10bitずつだけでなく5bit×2と20bitといった組分せも可能。

とはいえ1bitずつフラグ管理に使われるのが主。
大量Varでフラグ管理をしていてVarの余りが少なくなるような場合は必須。

■通常の桁数分割とbit桁数分割の違い

「1か0」のフラグ管理は通常の桁数分割だと10+1個までしか管理できないが、
bitには「1か0」を記憶する桁が31+1個あるのでおよそ3倍もの数を管理ができる。
また0~1000までの数値も桁数分割では2個しかはいらないが、bitなら3個も入る。
:|
とは言え桁数分割の方の10分割は0か1が1個+0~9が9個それぞれの情報量は多く、
2分割なら0~9999まで+0~213747までの数値と、かなりロスが出ているのだが。
特に通常の桁数分割方式の場合、0~4までを9個・0,1(5)を10個・+-という分割も可能で、
この場合、bitに換算すると3bitクラス×9+1bit×11と38bit分もの情報である。
(0~4の管理に3bitでは5~7のロスが生じ、それが9個重なり、6bitの差となっている。)

fvar、Float型とbit演算

Float型は32bit-Int型と同じ32bitの情報だが形式は全く異なり、
  • 1フラグの他小数数値や乗算用の数値で分かれており小数を扱える反面bit計算に適さない。
その為、基本的にFvarでbit演算を行うことはない。
なおFloat型・Fvarでも2の冪であれば、2の31乗まで確実に記録することができる。

+ ■Var-bit桁数分割方式・使い方

■Var-bit桁数分割方式・使い方

何もにも考えずに使いたい場合用・0,1フラグ管理
  • 代入・1にする
    • Var(xx) := ( Var(xx) | (Floor( 2.0**(使う桁-1) )) )
  • 代入・0にする
    • Var(xx) := ( Var(xx) & (Floor( 2.0**(使う桁-1) )^-1) )
  • 代入・フラグ条件式
    • Var(xx) := ( Var(xx) & (Floor( 2.0**(使う桁-1) )^-1) ) + (Floor( 2.0*(使う桁-1) ))*(条件式)
  • 確認/0or1式
    • !( !(Var(xx)&(Floor( 2.0**(使う桁-1) ))) )
  • 使える桁数は1~32まで。
あまり考えずに使いたい場合用・範囲数値管理
  • まず1~32のどこからどこまでを使用するか決める。
    • 使用する桁範囲の一番小さい桁(場所)と、使用する桁数(範囲)を決める。
    • 仮に5~8桁目を使うとしたら、場所が5、5,6,7,8なので4桁の範囲
  • 代入
    • Var(xx) := ( Var(xx) & (((Floor( 2.0**(範囲) )-1)*Floor( 2.0**(場所-1) ))^-1) ) + ( 代入する数値 )*(Floor( 2.0**(場所-1) )-1)
    • 範囲以上の数値を代入すると上側の桁にはみ出してしまうのて注意
    • 必要なら、予め代入する数値を上限値に制限したりすること
    • Ifelse((Floor( 2.0**(範囲) )-1)>代入予定値,代入予定値,(Floor( 2.0**(範囲) )-1))
  • 確認
    • ( Var(xx) & ((Floor( 2.0**(範囲) )-1)*Floor( 2.0**(場所-1) )) ) / Floor( 2.0**(場所-1) )
※注意点
  • ※桁数がかぶっていたりすると上手く処理されない。
  • ※32bitのため、bitに32桁より大きい桁は存在しない。
  • ※範囲桁数以上の数値を代入してはいけない。
  • Floor内の2.0はMUGENでの冪乗計算を安定させるために必須

■上記の解説

フラグ管理の項目
  • まず目的のbit桁の住所数値はFloor( 2.0**(x-1) )で指定している。
    • 「-1」なのは2.0分を減算しないと1つ上の桁になってしまうため。
    • bitの住所数値については上記の「32bit-Int型の表」を参照。
  • そのbit住所の数値を|ORや&ANDで埋めたり確認したりしている。
  • 0にする際の「^-1」はbitの全ての桁の0と1を反転させるbit演算。
    • 内容は「11111111111111111111111111111111」との^XOR
    • 指定したbit桁のみ1^1の=0となりそれ以外は全て1になる。
    • そしてその数値と&ANDをすることで目的の桁のみを0にできる。
  • なお「^XOR」を使わない除外方法は
    Var(xx) := ( Var(xx) | (Floor( 2.0**(使う桁-1) )) ) - (Floor( 2.0**(使う桁-1) ))
    • 「|or」で埋めてから減算を行うというもの。
範囲数値管理の項目
  • 場所と範囲は必ず決めておかないといけない。
    • 場所は指定の桁まで*で上げる・指定の桁から/で下げることに使用。
    • 範囲は(Floor( 2.0**(範囲) )-1)と、使用する桁数の1つ上の桁を1にして-1。
    • 範囲8桁なら2の8乗である「256(100000000)」から-1の「255(11111111)」と
      • (2の(指定桁数)乗)-1により、指定桁数分1の並んだbit数値を算出できる。
  • 代入する際は「(範囲*場所)^-1」で&AND演算して指定桁数を空に、
    そこへ「代入数値*場所」を加算して代入する。
  • 確認する際は「(範囲*場所)」で&AND演算して指定桁数以外を空に、
    その数値を/場所で桁を下ろすことで数値を確認する。

■数値の直打ちについて

  • なおFloor()の部分は上記の「32bit-Int型の表」の対応数値を書いても構わない。
  • 15桁目であればbit住所は16384なので( var(xx) & 16384 )みたいな具合。
    • 単純な記述のしやすさは上記の方が上だが、記述の単純さは数値を直に入力する方が楽。
  • 範囲指定の数値では桁数15,範囲5では( var(xx) & ((16-1)*(16384)) )/(16384)となるが、
    • ()内の計算をまとめ( var(xx) & 245760 )/(16384)と記述しても良い。
  • と言うより要領がわかっているならそうした数値を直に入力する方が良い。
    • 少々面倒ではあるが表を作り桁数と範囲の数値を併記しておけば非常に楽。

  • 実際に使用する数値を作りたい場合
    • 基本的には「32bit-Int型の表」の対応数値を利用する。
    • 範囲*場所用の数値も(範囲桁数+1の対応数値)-1に、
      場所の対応数値を掛けた数値を予め用意しておくと良い。
    • ただしbitの32桁目がマイナス数値なので通常の電卓では算出できない。
      「-2147483648」を直接計算すること。
      • 不安であれば32bit目を使わないか、個別の1bitフラグとして利用しよう。

■bitの動きの例

フラグ管理
1にする
00000000000000001100010101110101 50549 この数値に対して12桁目を入れる。
00000000000000000000100000000000 2048 Floor( 2.0 ** (12-1) )の数値をORすると
00000000000000001100110101110101 52597 こうなる。ORなので指定桁が1なら変化無し。
0にする
00000000000110110101110110100110 1793446 この数値から15桁目を削る
00000000000000000100000000000000 16384 Floor( 2.0 ** (15-1) )から~
11111111111111111111111111111111 -1 -1のXORで
11111111111111111011111111111111 -16385 指定行のみ0にする。
00000000000110110101110110100110 1793446 元数値と
11111111111111111011111111111111 -16385 指定桁数値^-1数値とANDで
00000000000110110001110110100110 1777062 指定桁のみを0にできる。
なお、&ANDなので0なら0のまま。
00000000000000000100000000000000 16384 条件式は*条件で指定桁数値を加算。
確認する
000000000-1100101110010110001101 3335565 この数値から17桁目を調査したいなら
00000000000000010000000000000000 65536 Floor( 2.0 ** (17-1) )とANDをして
00000000000000000000000000000000 0 存在するかどうかを確認。
対象桁があるならANDにつかった数値に。
なお記述例では!を2回重ねることで
存在するならAND値→0→1に変換。
存在しないなら0→1→0と変換している。
範囲数値
処理の基本・範囲と場所
00000000001100101110010110001101 3335565 ここの12桁目から7桁分を使うなら
00000000000000000000000010000000 128 まず範囲のためにFloor( 2.0**7 )から
00000000000000000000000001111111 127 -1をして7桁の範囲数値に
00000000000000000000100000000000 2048 場所の12桁目Floor( 2.0 ** (12-1) )を
00000000000000111111100000000000 260096 範囲*場所の数値を作る。
代入する
00000000000000111111100000000000 260096 範囲*場所を-1とXORして
11111111111111000000011111111111 -260097 範囲*場所の反転を作り
00000000001100101110010110001101 3335565 元数値とANDをかけて
00000000001100000000010110001101 3335565 範囲数値を0にする
00000000000000000000000001001000 72 この数値を入れるとして
00000000000000000000100000000000 2048 場所値で掛けて
00000000000000100100000000000000 147456 代入する数値にし、
00000000001100000000010110001101 3335565 範囲数値を0にした元へ
00000000001100100100010110001101 3294605 加算して代入を完了
参照する・上記の加算後から数値を取り出す。
00000000001100100100010110001101 3294605 ここから
00000000000000111111100000000000 260096 範囲*場所とANDで
00000000000000100100000000000000 147456 範囲以外を0にしたあと
00000000000000000000100000000000 2048 場所値で割り
00000000000000000000000001001000 72 数値を取り出す。

+ ■bit分割Var用Var表・txtファイル用

■bit分割Var用Var表・txtファイル用

;Var表用の32bit分割表 bit住所値付き
;Var(**)1 =(1) =
;--bit--2 =(2) =
;--bit--3 =(4) =
;--bit--4 =(8) =
;--bit--5 =(16) =
;--bit--6 =(32) =
;--bit--7 =(64) =
;--bit--8 =(128) =
;--bit--9 =(256) =
;--bit-10 =(512) =
;--bit-11 =(1024) =
;--bit-12 =(2048) =
;--bit-13 =(4096) =
;--bit-14 =(8192) =
;--bit-15 =(16384) =
;--bit-16 =(32768) =
;--bit-17 =(65536) =
;--bit-18 =(131072) =
;--bit-19 =(262144) =
;--bit-20 =(524288) =
;--bit-21 =(1048576) =
;--bit-22 =(2097152) =
;--bit-23 =(4194304) =
;--bit-24 =(8388608) =
;--bit-25 =(16777216) =
;--bit-26 =(33554432) =
;--bit-27 =(67108864) =
;--bit-28 =(134217728) =
;--bit-29 =(268435456) =
;--bit-30 =(536870912) =
;--bit-31 =(1073741824)=
;--bit-32(-2147483648)=
;範囲用
;-bit-xx-xx=(&x範囲値x)/x場所値x=



最終更新:2018年06月06日 13:22