HN 日本語サマリー

← 一覧へ戻る
プログラミング

BASICにおけるビットシフト

Bit Shifting in Basic (subethasoftware.com)

57 pointsby efren66 コメント

要約

この記事では、レトロコンピューティングの文脈で、BASIC言語におけるビットシフトの概念と実装方法を解説しています。単純な乗算・除算によるシフトから、16ビット値の結合・分割、そしてCommodore VIC-20やCoCoといった古いマシンでのビット操作の実際的な応用までを、具体的なBASICコード例とともに紹介しています。

全文翻訳

BASICにおけるビットシフト

[画像: VIC-20のキャラクターブロック、ビットシフト]

最近、怠惰になってコンピューターに仕事を任せたいという衝動に駆られました。Commodore VIC-20の2文字ブロックの各オフセット位置に1つずつ、8×8のグラフィックキャラクターをデザインしていました(右の画像を参照)。

WindowsベースのCBM prg Studioのようなモダンなツールを使えば、手作業で簡単に編集して望む結果を得ることができましたが(実際にその画像を作成したのもそうでした)、1つのキャラクターをデザインして、他のシフトされたフレームを作成するプログラムを書く方が楽しいだろうと思いました。

C言語ではビットシフト演算子があるので、何度もビットシフトを行ってきましたが、BASICで意図的に行った記憶はありません。

ビットシフトの基本

ビットシフトとは、バイト(またはワード、ロングなど)内のすべてのビットを左または右に移動させることです。バイト値 00111100 を右にシフトする例を以下に示します。

Before: [ 0 0 1 1 1 1 0 0 ]
After : [ 0 0 0 1 1 1 1 0 ]

ビットが「端から落ちる」ことを気にせずにシフトしたいだけであれば、値を2倍または半分にするのと同じくらい簡単です。

これを実証するために、まずバイトをビットとして表示するプログラムが必要です。

0 REM bitsslow.bas
10 Z=&H00:GOSUB 500
20 Z=&HF0:GOSUB 500
30 Z=&H0F:GOSUB 500
40 Z=&HFF:GOSUB 500
50 END

500 REM PRINT BITS
510 FOR ZB=7 TO 0 STEP -1
520 IF Z AND 2^ZB THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 PRINT:RETURN

行500のルーチンは、変数Zの値をビットとして表示します。バイト(0〜255)のみを扱うようにハードコーディングされています。これを実行すると、次のように表示されます。

00000000
11110000
00001111
11111111

これらの行は、それぞれ &H00、&HF0、&H0F、&HFF に対応します。16進数で表示するのは、ビットパターンが見やすいからです(0=0000、F=1111)。

少し速く…

私のビット表示ルーチンは非常に遅いため、数字が1つずつ表示されるのを見ることができます。これは、各ビットチェックで行520で行われる計算のためです。速度を上げるために、それらの2のべき乗(1、2、4、8、16、32、64、128)の配列を事前に計算して使用することができます。

0 REM bitsfast.bas

5 GOSUB 1000

10 Z=&H00:GOSUB 500
20 Z=&HF0:GOSUB 500
30 Z=&H0F:GOSUB 500
40 Z=&HFF:GOSUB 500
50 END

500 REM PRINT BITS
510 FOR ZB=7 TO 0 STEP -1
520 IF Z AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 PRINT:RETURN

1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

行5は、2のべき乗の配列ZB()を設定する初期化ルーチンにGOSUBします。その後、ルーチン500は以前と同じように呼び出すことができますが、今度は非常に速く表示されるため、実際には表示されているのが見えないほどです。

これで、このルーチンを使用して、2倍または半分にすることによるビットシフトを実証しましょう。

0 REM bitshftl.bas
5 GOSUB 1000
10 Z=1 '00000001
20 FOR A=1 TO 8
30 GOSUB 500
35 REM *2 TO SHIFT LEFT
40 Z=Z*2:NEXT
50 END
500 REM PRINT BITS
510 FOR ZB=7 TO 0 STEP -1
520 IF Z AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 PRINT:RETURN
1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

行10では、Zは1から始まり、これは00000001のビットパターンです。その後、ループで8回2倍され、各回でビットが左に1つシフトされます。出力は次のようになります。

00000001
00000010
00000100
00001000
00010000
00100000
01000000
10000000

右ビットシフト

そして、Zを128(ビットパターン10000000)から始めて2で割ると、右にシフトします。

0 REM bitshftr.bas
5 GOSUB 1000
10 Z=128 '10000000
20 FOR A=1 TO 8
30 GOSUB 500
35 REM /2 TO SHIFT RIGHT
40 Z=Z/2:NEXT
50 END
500 REM PRINT BITS
510 FOR ZB=7 TO 0 STEP -1
520 IF Z AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 PRINT:RETURN
1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

これは次のように表示されます。

10000000
01000000
00100000
00010000
00001000
00000100
00000010
00000001

非常にシンプルです。もしこれがやりたかったことのすべてなら、これで終わりです。

しかし、やりたかったことはそれだけではありませんでした。なので、まだ終わりではありません。

1つのバイトでビットを右にシフトし、シフトアウトしたビットが2番目のバイトにシフトインするようにしたかったのです。次のようになります。

    1st Byte  2nd Byte
1) [00001111][00000000]
2) [00000111][10000000]
3) [00000011][11000000]
4) [00000011][11100000]
5) [00000001][11110000]
6) [00000000][11111000]
...etc...

右にシフトされるビットを(ANDを使用して)取得し、それらを新しい変数に配置してから、16ビット値をシフトした場合に到達するであろう場所にそれらのビットをシフトしてから配置する方法を見つけるのに、あまりにも多くの時間を費やしました。

…その後、16ビット値をBASICで使用できることに気づき、それは愚かだと考えました!

BASICにおける16ビット

BASICが使用しているメモリ位置を表示するようなものを見たことがあるかもしれません。

PRINT PEEK(25)*256+PEEK(26)

Color BASICでは、メモリ位置25と26にBASICメモリの開始アドレスの16ビット値が含まれています。PEEKは単一のバイトしか扱えないため、2つのPEEKで16ビットアドレスを構成する2つのバイトを取得し、2つの8ビット値を1つの16ビット値に変換する計算が必要です。

私のXroarエミュレーター上の仮想CoCoでは、メモリ位置25には38(&H26)が含まれ、メモリ位置26には1(&h01)が含まれています。それらの2つの8ビット値を16ビットアドレスに変換するために、38/&H28を8回左にシフトして新しい16ビット値に入れ、その後1/&H01値を追加(またはOR)する必要があります。

C言語では、これを行う方法の1つはビットシフト演算子を使用することです。

uint16_t Result;
uint8_t  Byte1;
uint8_t  Byte2;
Byte1 = Peek(25); // メモリ値を取得するための架空の関数。
Byte2 = Peek(26);
Result = (Byte1 << 8) | Byte2; // Byte1を左に8ビットシフトし、
                               // Byte2をORする。
// または...
Result = (Byte1 << 8) + Byte2; // 右の8ビットが空なので、
                               // 加算しても同じ結果になる。

…しかし、これらと同じことを行う他の多くの方法があり、中にはこれらのアプローチよりもはるかに高速なものもあります。

BASICに戻る

左シフトは、値を2倍することで実行できます。1回シフトするには、次のようにします。

V = V * 2

2回シフトするには、次のようにします。

V = V * 2 * 2

…しかし、それは愚かに見えます。単に4倍するだけです。そして3回ビットシフトする(2 * 2 * 2)には、8倍することができます。パターンが見えますか?それらはすべて2のべき乗(2、4、8、16、32、64、128、256など)です。

したがって、8回左シフトするには、256倍します。したがって、前に示したCの例はBASICでは次のように表されます。

10 B1=PEEK(25)
20 B2=PEEK(26)
30 R=(B1*256)+B2

やった!最初に「X=PEEK(Y)*PEEK(Z)」のようなものを見たとき、なぜそれが機能するのか理解できませんでした。ただ機能することは知っていました。そして、CoCoがそのようになっている理由も混乱しました。なぜなら、VIC-20では「X=PEEK(Y)+256*PEEK(Z)」となっていたからです。違いが見えますか?CoCoの6809プロセッサでは、16ビット値はYYZZですが、VIC-20の6502プロセッサでは逆のZZYYとして格納されます。したがって、私のVICでは、2番目の場所を取得して256倍し、最初の場所を追加する必要があります。

しかし、話が逸れました。

もう少し…

前の例は、バイト(B1)を効果的に左に8ビットシフトして、新しい16ビット値の上位8ビットに配置する方法を示しています。そのようなことは、8ビット値を2つの文字(2バイト)の異なる位置にシフトするのに非常に役立つでしょう。

私のアプローチは次のようになります。

  • Rは結果、16ビット(2バイト、範囲0〜65535)を表す値になります。
  • この例では右にシフトしているので、最初のステップは8ビットソース値をR結果変数の上位8ビット(最も左のビット)に取得することです。
  • 次に、R変数全体を右にシフトし、左と右の8ビットを別々の変数として抽出します。これが私の出力値になります。

抽出?それは、私たちがちょうど行ったことの逆になります。C言語では、16ビット値を2つの8ビット値に次のように変換できます。

uint16_t Source;
uint8_t  Byte1;
uint8_t  Byte2;
Source = 0x1234;           // 何らかの16ビット値。
Byte1 = (Source >> 8);     // 左に8ビット右シフトする。
Byte2 = (Source & 0x00ff); // 上位8ビットをマスクする。

…ただし、これには他の多くの(より高速/より良い)方法があります。しかし、BASICでも同じように行うことができます。

左シフトが256倍である場合、右シフトは256で割る必要があります。

10 R=&H1234
20 B1=(R/256)
30 B2=(R AND &HFF)

重要事項: この記事の後の段階で、このアプローチに大きな問題があることを発見しました。もしあなたがすでに知らなかったなら(私は知りませんでした)、すぐに説明します…書くとき、私は通常書きながら学んでおり、この思考の流れをそのまま残すことにしました。

これはBASICで初めてそのように行った方法です(C言語のやり方を模倣しています)。BASICで一般的に見られる方法は次のとおりです。

10 R=&H1234
20 B1=INT(R/256)
30 B2=R-(B1*256)

簡単なテストプログラムを次に示します。

0 REM split1.bas
10 S1=&H12
20 S2=&H34
30 R=S1*256+S2
40 PRINT HEX$(S1)" "HEX$(S2)" -> "HEX$(R)
50 D1=INT(R/256)
60 D2=R-(D1*256)
70 PRINT HEX$(R)" -> "HEX$(D1)" "HEX$(D2)

[画像: BASICを使用して16ビット値を分割したり、2つの8ビット値を結合したりする]

ベンチマークの脱線

1980年代から間違っていたのでしょうか?C言語スタイルの方法(ANDを使用)は、BASICの方法(INTを使用)よりも高速でしょうか?信頼できるベンチマークプログラムで試してみましょう。

0 REM split2.bas
5 DIM TE,TM,B,A,TT
6 R=&H1234
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=42 THEN 100
40 B1=R/256
50 B2=R AND &HFF
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

これは1143を示しています。(もちろん、16進数を使用したり、スペースを削除したりすることで、さらに高速化できますが、これは2番目のバージョンとの比較のためだけです。)

そして、従来のBASICで試してみましょう。

0 REM split3.bas
5 DIM TE,TM,B,A,TT
6 R=&H1234
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=42 THEN 100
40 B1=INT(R/256)
50 B2=R-B1*256
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

このバージョンは1498を報告します!まあ、驚きました…INTと除算と減算と乗算は、除算とANDよりも遅いのです。まあ、そのように書き出すと、理にかなっているようです。

C言語で学んだことをBASICに適用することが、成果を上げているようです。

しかし、話が逸れました。

もう終わりですか?

元のタスクに戻ると、8ビット値を結合し、16ビット値を分割し、好きなようにシフトできるはずです。

まず、ビット表示ルーチンを16ビット値を扱えるように変更しましょう。

重要事項: ここが先ほど言及したビットです…

0から7を0から15に変更すれば16ビットすべてをカバーできると思ったのですが、?FC ERROR(関数呼び出し)が発生しました。少しテストしたところ、ANDは0から32767(&H7FFF)までの値にしか機能しないことがわかりました。これは16ビット符号付き整数の最大値であり、数値に15ビット、符号(+または-)に1ビットを使用します。

しまった!なので、15ビットしか簡単に表示できず、余分なビットが本当に必要でした。

自分へのメモ: Color BASIC Unravelled という本を見て、なぜそうなるのかを確認する。

したがって、16ビット値の各バイトを個別に表示するように、8ビット表示ルーチンを変更する必要があるようです。この記事の早い段階でそれをどのように行うかを学んだのは幸いでした!

16ビットビット表示

ルーチンを次のように変更する必要がありました。

0 REM bits16.bas

5 GOSUB 1000

10 Z=&H0000:GOSUB 500
20 Z=&HFF00:GOSUB 500
30 Z=&H00FF:GOSUB 500
40 Z=&HFFFF:GOSUB 500
50 END

500 REM PRINT BITS
501 ZZ=INT(Z/256):GOSUB 510
502 ZZ=Z-ZZ*256:GOSUB 510
503 PRINT:RETURN
510 FOR ZB=7 TO 0 STEP -1
520 IF ZZ AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 RETURN

1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

ふう!これで動作し、次のように表示されます。

0000000000000000
1111111100000000
0000000011111111
1111111111111111

さて、素晴らしいスピードアップは発見できませんでしたが(少なくとも32767を超える値を使用したい場合)、動作させることができました。

最後にとっておきのビットを…

これで、8ビット値から始めて、それを16ビット値の左側にシフトし、1ビットずつ右にシフトを開始し、各ステップで結果の2バイトを分割できるかどうかを確認する小さなテストを試すことができます。テストバイトとして&HFF(11111111)を使用します。

0 REM shift16.bas

5 GOSUB 1000

10 Z=&HFF  '11111111
15 Z=Z*256 '1111111100000000
20 FOR A=1 TO 8
25 REM SPLIT INTO TWO BYTES
26 B1=INT(Z/256)
27 B2=Z-(B1*256)
28 PRINT HEX$(B1)TAB(3)HEX$(B2)TAB(5)" = ";
30 GOSUB 500
35 REM /2 TO SHIFT RIGHT
40 Z=Z/2:NEXT
50 END

500 REM PRINT BITS
501 ZZ=INT(Z/256):GOSUB 510
502 ZZ=Z-ZZ*256:GOSUB 510
503 PRINT:RETURN
510 FOR ZB=7 TO 0 STEP -1
520 IF ZZ AND ZB(ZB) THEN PRINT"1"; ELSE PRINT "0";
530 NEXT
540 RETURN

1000 REM INIT BIT ARRAY
1010 FOR ZB=0 TO 7
1020 ZB(ZB)=2^ZB
1030 NEXT
1040 RETURN

そして、次のように表示されます。

[画像: Color BASICで16ビット値をシフトし、2つの8ビット値に分割する]

成功!

これで、そのルーチンをコードに組み込み、1つの8×8文字のデータ(この記事の冒頭で示した塗りつぶされた円のようなもの)を取得して、2×1文字ブロックの各位置を表す16個の8×8文字を得ることができます。

2010 DATA 60,126,255,255,255,255,126,60

結論として…

うわー。256倍して2で割ることを示すために、ずいぶん遠回りしましたね。でも、これらの例にはいくつかの便利なルーチンがあるかもしれません。

そして今度は私があなたに尋ねる番です。

  • 16ビット値をバイナリで表示する、より良い/より速い方法を知っていますか?
  • 2つの8ビット値を16ビット値に結合したり、16ビット値を2つの8ビット値に分割したりする、より速い方法を知っていますか?
  • 2のべき乗を掛けたり割ったりするよりも、ビットシフトの良い/速い方法がありますか?

コメントで教えてください。もしかしたら、このトピックのパート2があるかもしれません。

次回まで…

Like this:
Related