サイトトップ
Director Flash 書籍 業務内容 プロフィール

Adobe Flash非公式テクニカルノート

2進数のビット演算を試してみる − 奇数と偶数の扱い

ID: FN1111004 Product: Flash CS4 and above Platform: All Version: 10 and above/ActionScript 3.0

整数を2進数として計算するとき、ビット演算を用います[*1]。ビット単位の演算子は、なじみがないとどう使ってよいのか思いつきませんし、初めは意味もわかりにくいでしょう。本稿はその手始めとして、ビット単位の演算で偶数と奇数を扱ってみます。お題は、連番整数を偶数と奇数のふたつに分けるというものです。

[*1] ビット(bit)は、コンピュータが扱う最小の単位で、2値つまりふたつの状態のうちのひとつを示します。2値を0か1とすれば、2進数の1桁が1ビットになります。ビット演算は、2進数をビットつまり1桁ごとに処理します。

01 剰余演算子%と切捨ての関数で偶数と奇数を分ける
0から9までの連番整数をforループで偶数と奇数に分け、ふたつのVectorオブジェクトにそれぞれ納めます。まずは、ビット演算を使わない、ごく普通のやり方です。カウンタ変数を2の剰余(割った余り)で奇数と偶数に分け、それぞれのVectorオブジェクトに加えればよいでしょう。なお、小数点以下切捨てはMath.floor()メソッドよりint()関数の方が扱いは速いです(「ActionScript 3.0におけるパフォーマンス向上のヒント」06「数値の演算」の「Mathクラスの数値演算」の項参照)。

スクリプト001■2の剰余で奇数・偶数を分けて配列アクセス演算子でVectorオブジェクトに加える
    // フレームアクション
  1. var count:uint = 5;
  2. var amount:uint = count * 2;
  3. var odd:Vector.<uint> = new Vector.<uint>(count);
  4. var even:Vector.<uint> = new Vector.<uint>(count);
  5. for (var i:uint = 0; i < amount; i++) {
  6.   if (i % 2 == 1) {
  7.     odd[uint(i / 2)] = i;
  8.   } else {
  9.     even[uint(i / 2)] = i;
  10.   }
  11. }
  12. trace(odd);   // 出力: 1,3,5,7,9
  13. trace(even);   // 出力: 0,2,4,6,8

ふたつ補足します。第1は、スクリプト001第3〜4行目の右辺で、Vectorクラスのコンストラクタメソッドに引数の整数を渡していることです。Vectorインスタンスをつくるときには、予め引数で長さを定めた方が速く扱われるからです(F-site「Vectorインスタンスには長さを定めた方がよい」参照)。

第2に、スクリプト001第7および9行目で、Vectorエレメントのインデックスに渡す数値をuint()関数で切捨てています。関数int()でなくuint()を使ったのは、数値を切捨てるだけでなく、Vectorエレメントのデータ型uintにキャストするためです。やはり、扱いが速まります(F-site「配列のインデックスを式で計算したときはuint型で渡す」)。


02 ビット演算で偶数と奇数を分ける
前掲スクリプト001の中からふたつの処理を、ビット演算に替えてみます。第1は、偶数か奇数かの切り分けです。スクリプト001第6行目は、剰余演算子%で2の剰余を確かめました。第2は、小数値以下の切捨てです。スクリプト001第7および9行目は、uint()関数を使っています。

第1の偶数か奇数かは、簡単なビット演算でわかります。まず10進法の場合なら、下ひと桁が0なら10で割切れます。同じように、2進法で表された整数は、下ひと桁が0なら2で割切れる、つまり偶数なのです。2進数からある桁の数字を取出すには、ビット単位の論理積(演算子&)を用います。

ビット単位の論理演算子は、ふたつの整数を2進数の各桁ごとに計算します。ビット単位の論理積演算子&の演算結果は次表001のとおりです。つまり、ふたつの整数の対応する桁がともに1のときのみ1、そうでない桁は0になるのです。

表001■ビット単位の論理積演算子&の演算結果
ビット単位の論理和演算 結果の2進数
0 & 0 0
0 & 1
1 & 0 		0
1 & 1 1

この計算結果は、別の見方もできます。ビット単位の論理積演算をするふたつの数字の一方の桁が1なら、もう一方の桁の数字がそのまま結果になります。ところが一方の数字の桁が0であれば、もう一方の数字に拘らず演算結果は0になるのです。

0 & 1 → 0 そのまま
1 1
0 & 0 → 0 つねに0
1 0

そうであれば、2進数の整数から下ひと桁の数字(0か1)を取出すには、1との論理積を求めればよいのです。なぜなら1はひと桁なので、対象の整数の下ひと桁と論理積が求められ、その整数の下ひと桁がそのまま演算結果になります。そして、ひと桁の2進数のふた桁目以上の数字はないので、0とみなされます。したがって、対象となる整数のふた桁目以上との演算結果は0となり、すべて除かれてしまうのです。

整数 & 1 → 0なら偶数、1は奇数

第2の切捨ては、もっと簡単です。ビット単位の右シフト(演算子>>)を使います。ビット単位の右シフト演算は、2進数で表された整数から演算子>>に定められた桁数を下から削除します。2進数は桁が増えるたびに2倍になるのですから、桁を減らすというのは2で割って小数値を切捨てるのと同じです(前出「ActionScript 3.0におけるパフォーマンス向上のヒント」06「数値の演算」の「ビット演算」の項参照)。前掲スクリプト001第7および9行目は、2で割って小数値を切捨てていました。したがって、ビット単位の右シフトをひと桁行えばよいのです[*2]。

前掲スクリプト001のふたつのビット演算で書替えたのがつぎのスクリプト002です。第6行と第7および9行目にビット演算を用いました。

スクリプト002■2進数の下ひと桁で奇数・偶数を分けてビット単位の右シフトでインデックス計算
    // フレームアクション
  1. var count:uint = 5;
  2. var amount:uint = count * 2;
  3. var odd:Vector.<uint> = new Vector.<uint>(count);
  4. var even:Vector.<uint> = new Vector.<uint>(count);
  5. for (var i:uint = 0; i < amount; i++) {
  6.   if (i & 1 == 1) {
  7.     odd[i >> 1] = i;
  8.   } else {
  9.     even[i >> 1] = i;
  10.   }
  11. }
  12. trace(odd);   // 出力: 1,3,5,7,9
  13. trace(even);   // 出力: 0,2,4,6,8

比べてみると、2の剰余よりビット単位の論理積で下ひと桁を取出す方がずっと速いようです。他方で、ビット単位の右シフト演算はuint()関数と明らかな差は認められませんでした。テスト用のスクリプトをwonderflに公開しています。

Comparing % and uint() vs bitwise (& and >>) - wonderfl build flash online


[*2] 2の割り算をせずに小数値をそのまま切捨てるには、ビット単位の右シフト演算子>>に桁数0を指定します。ビット演算は整数に対して行われるため、右シフトをまったくしなくても結果は整数となり、小数値が切捨てられます。

作成者: 野中文雄
作成日: 2011年11月15日
Copyright © 2001-2011 Fumio Nonaka.  All rights reserved.