Mitzyuki's Blog

C言語のビット演算

はじめに

かつてメモリーが非常に高価な時代に 1 ビットで表現できる 「オン」か「オフ」などの状態はビットによる状態保持がほぼ常識となっていました。 プロセッサにビット演算の機能が搭載されていて ビット演算が非常に高速だった事も普及に拍車をかけていたと思います。 しかし、メモリを含むコンピュータリソースが安価になり、 プロセッサの処理性能が高速になった今の時代に敢えてビットで状態を保持する意味はあまりないと思いますが、 ビット演算について学ぶのは良いことだと思います。

ビット演算

ビット演算はデータをビット単位で操作するための演算方法です。 他にもいくつか種類がありますがここでは C 言語に演算子が用意されているビット演算を紹介します。

ビット演算子

論理積

論理積は AND と呼ばれる演算です。 2 つのビットで双方が 1 の場合のみ 1 となります。
特定のビットの状態を検査する時に多く利用されます。

C 言語の演算子は & で示されます。

  11 & 1 = 1
  20 & 1 = 0
  31 & 0 = 0
  40 & 0 = 0
                    

論理和

論理和は OR と呼ばれる演算です。 2 つのビットのどちらかが 1 の場合に 1 となります。
特定のビットを 1 にする場合に多く利用されます。

C言語の演算子は | で示されます。

  11 | 1 = 1
  21 | 0 = 1
  30 | 1 = 1
  40 | 0 = 0 
                    

排他的論理和

排他的論理和は XOR と呼ばれる演算です。 2つのビットが異なる場合に 1 となります。
ビットの違いを検出する場合に多く利用されます。

C言語の演算子は ^ で示されます。

  11 ^ 1 = 0
  21 ^ 0 = 1
  30 ^ 1 = 1
  40 ^ 0 = 0
                    

否定

反転演算子は NOT と呼ばれる演算です。 ビットの状態を反転させます。 1 なら0、0なら1となります。

C言語の演算子は ~ で示されます。

  1~ 1 = 0
  2~ 0 = 1
                    

シフト

ビット列を左右に移動させます。 左シフトは指定された数だけビット列を左に移動、 右シフトは指定された数だけビット列を右に移動します。 移動してできたスペースには 0 か 1 が挿入されます。 2 のべき乗の乗算、除算に多く利用されます。

C言語の演算子は << 、>> で示されます。

  11 << 2 = 4
  21 << 4 = 16
  34 >> 2 = 1
  416 >> 4 = 1
                    

ビットマスク

ビットマスクは、ビット演算を使って特定のビットを操作するための方法です。 ビットマスクを使用することで、データの特定のビットを効率的に抽出、設定、 またはクリアすることができます。

実際の演算

実際に C 言語で行うビット演算のスニペットです。

ここでは 8 ビットの変数 flags に対してのビット操作を例として示します。

変数 flags の右から 2 番目のビットを 1 にしたい場合。

右から 2 番目のビットは 2 進数で 0000 0010 と表現されます。 これは 16 進数では 0x02 と表現できるのでビットマスクは 0x02 となります。 ビットを 1 にするには論理和 (|) を取ればいいので以下のスニペットになります。

  1/* 変数 flags の右から 2 番目のビットを 1 にする */
  2flags = flags | 0x02;
            

C 言語では演算した結果を変数に戻す場合は 演算子 + = という記法が利用できるので 以下の様に |= と短く記述できます。
また 0x02 のような定数 (多くの場合マジックナンバーと呼ばれます) をプログラム中に直接書くのは有害な事とみなされ (considered harmful) ていますので、 同じく C 言語のマクロ機能で名称を付与するのが良い方法といえるでしょう。

  1#define     MASK        0x02
  2
  3flags |= MASK;
            

元の変数 flags の値がどの様な値であっても 右から 2 番目のビットが 1 になる以外の影響はありません。 右から 2 番目のビットが元々 1 の場合は何も変化はありません。

変数 flags の右から2番目のビットが 1 か確認したい場合。

ビットが 1 かを確認するためには論理積 (&) を取ればいいのでビットマスクと論理積を取ります。 ビットマスクは右から 2 番目のビットだけが 1 なので 変数 flags の右から2番目のビットが 1の場合は 1 となります。 他のビットはビットマスクが 0 なので 0 となります。

  1/* 変数 flags の右から2番目のビットが 1 か確認する */
  2if((flags & MASK) != 0) {
  3    /* 右から 2 番目のビットは 1 */
  4}
            

C言語の if 文は言語仕様として 0 か 0 以外かの判定なので短く書くこともできます。

  1/* 変数 flags の左から 2 番目のビットが 1 か確認する */
  2if(flags & MASK) {
  3    /* 左から 2 番目のビットは 1 */
  4}
            

変数 flags の右から 2 番目のビットを 0 にしたい場合。

ビットを 0 にする場合は少しだけ複雑になります。 他のビットに影響を与えずに右から 2 番目のビットを 0 にする場合は 0000 0010 の反転した値 1111 1101 と論理積を取ることで実現できます。

変数 flags の値	1010 1010
ビットマスクを反転した値	1111 1101
論理積の結果	1010 1000

  1/* 変数 flags の右から 2 番目のビットを 0 にする */
  2flags &= ~MASK;
            

シフト演算

左シフト演算は乗算に利用できます。 左に 1 シフトすると溢れがなければ元の値が 2 倍になります。 一番右側には 0 が挿入されます。右シフト演算は除算に利用できます。 右に 1 シフトすると元の値が 1/2 になります。 一番左側は符号付きの場合は符号桁が継承され(算術シフト)、 符号なしの場合は 0 が挿入され(論理シフト)ます。 かつてはプロセッサの乗算、除算能力が極端に低い場合があったので、 2 のべき乗の演算にはよく利用されましたが、桁溢れの処理が煩雑になる事やコードが直感的ではない事、 プロセッサの性能向上などにより最近では推奨されない使い方になっているようです。 現在では後述の可搬性のあるビットマスク生成のために利用される事が多いです。

変数 i と j の値を入れ替える。

以前は高速でメモリ使用量を極小にしたまま変数の値を入れ替える事ができると言われていたアルゴリズムです。 2 つの変数に排他的論理和を 3 度繰り返す事で他の変数を使用する事なく値を入れ替える事ができます。

このアルゴリズムは i 、j において (i XOR j) XOR j = i が成立する 排他的論理和の対称差という性質を利用したものです。

現代では却って遅くなる場合があると言われていますし、 浮動小数点型の変数では利用できません。 そもそも処理内容が見た瞬間には判りずらいので推奨されていません。

  1int     i,
  2        j;
  3
  4i ^= j;
  5j ^= i;
  6i ^= j;
            

ちなみに値が十分に小さい整数の場合は以下の四則演算でも同様の結果となりますが、 値が大きくなると算術オーバーフローが発生するおそれがあるのでこちらも強く非推奨です。

  1int     i,
  2        j
  3
  4i = i + j;      /* i += j */
  5j = i - j;
  6i = i - j;     /* i -= j */
            

ビットマスクについて

上の例では変数 flags を 8 ビットと仮定して C 言語のコードを記載しましたが、 C 言語では変数の実際のサイズは厳密に定められていません。 例えば char 型の変数は最低 8 ビット必要、 int 型の変数は最低 16 ビット必要としか規格では定まっていません (現在世の中にある C 言語の処理系で char が 8 ビットではない、 int が 32 ビットでない処理系は多分存在しないと思いますが...)。
ただし最近の 64 ビット CPU では int が 32 ビットではなく 64 ビットとなっている場合があるので要注意です。

ですので int 型変数の一番左のビットを操作するためのビットマスクとして 32 ビットを仮定して 0x80000000 を指定すると想定とは異なった挙動となってしまう可能性があります。

  1#define     MASK        0x80000000
  2
  3unsigned    long    flags;
  4
  5/* 変数 flags の一番左のビットを 1 にする */
  6flags |= MASK;
        

この様に処理系依存の数値でも正しく動作するためには、 ヘッダーファイル limits.h で定義されているマクロを利用します。 たとえば unsigned long 型の変数に格納できる最大の数値は マクロ ULONG_MAX に格納されているので、 unsigned long の変数に対するビットマスクでは以下の方法で指定するのが可搬性があり安全な方法です。

  1#include    <limits.h>
  2
  3#define     MASK        ~(ULONG_MAX >> 1)
  4
  5unsigned    long    flags;
  6
  7/* 変数 flags の一番左のビットを1にする */
  8flags |= MASK;
        

ちなみにC99 (ISO/IEC 9899:1999) では変数については以下の項目しか規定されていません。

• 整数として表現できる範囲の大きさは以下の関係

singed char ≦ short int ≦ int ≦ long int ≦ long long int

• singed char の大きさは 8 ビット以上
• short int の大きさは 16 ビット以上
• int の大きさは 16 ビット以上
• long int の大きさは 32 ビット以上
• long long int の大きさは 64 ビット以上

規格として char を符号付きか符号無しか規定していません。

未定義なので鼻から悪魔を出しても(nasal demons) 仕様には反していません。