この記事について

組み込み等でよく使われるビット演算手法について記載します。

前提

各変数は特に断りがない場合、unsigned int型(uint32_t)を想定しています。
「N」はunsigned int型の定数です
文法はC/C++に従っています
- 数値は2の補数で表現されているとします
- 右シフトでは符号ビットの値がコピーされるとします

ビット演算

基本編

よく見かけると思われるテクニックです。

Nビット目のビット値(0 or 1)を取得

x = (v >> N) & 1; // x == 0 or 1

または、Nビット目のみが1の定数を使って論理積を取る方法もあります。
この場合、Nビット目の値が0であれば0、1であれば非0で判断します。

#define BIT_N (1<<N)
x = v & BIT_N; // x == 0 or Not-zero

後者はイベント判定などで使われます。イベントをビット位置で表現します。

#define EVENT_0   (0x01)  /* bit 0 */
#define EVENT_1   (0x02)  /* bit 1 */
#define EVENT_2   (0x04)  /* bit 2 */
#define EVENT_3   (0x08)  /* bit 3 */

if( v & (EVENT_1 | EVENT_2) )
{
        /* EVENT_1, EVENT_2のどちらかが発生した場合の処理 */
}
else if( v & EVENT_3 )
{
        /* EVENT_3が発生した場合の処理 */
}
else
{
        /* どのイベントも発生しなかった場合の処理 */
}

Nビット目を1にする

v |= (1 << N);

これもイベント処理で使われる事があります。

v |= EVENT_0;  // EVENT_0が発生したことを示す

Nビット目を0にする

v &= ~(1 << N);

イベント処理で使われる場合は、イベント発生情報をクリアする処理として使われます。

v &= ~EVENT_0;  // EVENT_0を処理済みとして発生情報をクリアする

Nビット目を反転する

v ^= (1 << N);

すべてのビットを反転する

v = ~v;

又は

v = v ^ (~0);

2のN乗倍する

v <<= N;

2のN乗で割る

v >>= N;

ビットマスクを生成する

0ビット目からN-1ビット目までがすべて1である値を生成します。 (N-1ビットまでのマスク生成)

v = (1 << N) - 1;

0～2^N-1の間で値を循環させる(2^Nの剰余を取得する)

v++;
v &= (1 << N) - 1;

任意の数の剰余は除算を使うため演算負荷が高いですが、2^Nに限定するとビット演算で求めることができるため高速に処理することができます。

応用編

たまに見かけるテクニックです。

最上位ビットのみが1である値を作成する

v = 1 << (sizeof(unsigned int)*8 - 1);

又は

v = ~(~0U >> 1);

最も下位に1が立っているビットのみ残した値を抽出する

v = -v & v;

奇数かどうか判定する

if ( v & 1 )
{
        /* 奇数 */
}
else
{
        /* 偶数 or 0 */
}

int x, yの値が≧0かどうか判定する

int x, y;

if( (~(x | y)) >> 31 )
{
        /*  すべての値が0以上 */
}
else
{
        /* どれかが0以下 */
}

おまけ編

使う場合は必ずコメントで説明が必要です。

絶対値を取得する

unsigned int abs( int num )
{
        return ( num^(num>>31) ) - ( num>>31 );
}

値を交換する

void swap( unsigned int *a, unsigned int *b )
{
  *a = *a ^ *b;
  *b = *b ^ *a;
  *a = *a ^ *b;
}

最も上位にある1であるビットのみを残した値を取得する

unsigned int bits_msb( unsigned int v )
{
  v = v | (v >>  1);
  v = v | (v >>  2);
  v = v | (v >>  4);
  v = v | (v >>  8);
  v = v | (v >> 16);
  return v ^ (v >> 1);
}

ビットを逆順に並べ替える

unsigned int bits_reverse( unsigned int v )
{
  v = (v & 0x55555555) <<  1 | (v >>  1 & 0x55555555);
  v = (v & 0x33333333) <<  2 | (v >>  2 & 0x33333333);
  v = (v & 0x0f0f0f0f) <<  4 | (v >>  4 & 0x0f0f0f0f);
  v = (v & 0x00ff00ff) <<  8 | (v >>  8 & 0x00ff00ff);
  v = (v & 0x0000ffff) << 16 | (v >> 16 & 0x0000ffff);
  return v;
}

1であるビットの個数をカウントする

unsigned int bits_count( unsigned int v )
{
  v = (v & 0x55555555) + (v >>  1 & 0x55555555);
  v = (v & 0x33333333) + (v >>  2 & 0x33333333);
  v = (v & 0x0f0f0f0f) + (v >>  4 & 0x0f0f0f0f);
  v = (v & 0x00ff00ff) + (v >>  8 & 0x00ff00ff);
  v = (v & 0x0000ffff) + (v >> 16 & 0x0000ffff);
  return v;
}

参考文献

hackersdelight
http://www.hackersdelight.org/hdcodetxt/pop.c.txt
http://www.hackersdelight.org/hdcodetxt/reverse.c.txt