ビット演算まとめ

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

# 前提

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

# ビット演算

## 基本編

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

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

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

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

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

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

> ```c
> #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にする

```c
v |= (1 << N);
```
> これもイベント処理で使われる事があります。

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

### Nビット目を0にする

```c
v &= ~(1 << N);
```

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

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

### Nビット目を反転する

```c
v ^= (1 << N);
```

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

```c
v = ~v;
```
又は

```c
v = v ^ (~0);
```

### 2のN乗倍する

```c
v <<= N;
```

### 2のN乗で割る

```c
v >>= N;
```


### ビットマスクを生成する

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

```c
v = (1 << N) - 1;
```

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

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

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


## 応用編

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

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

```c
v = 1 << (sizeof(unsigned int)*8 - 1);
```
又は

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

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

```c
v = -v & v;
```


### 奇数かどうか判定する

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

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

```c
int x, y;

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


## おまけ編

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

### 絶対値を取得する
```c
unsigned int abs( int num )
{
        return ( num^(num>>31) ) - ( num>>31 );
}
```

### 値を交換する
```c
void swap( unsigned int *a, unsigned int *b )
{
  *a = *a ^ *b;
  *b = *b ^ *a;
  *a = *a ^ *b;
}
```

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

```c
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);
}
```

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

```c
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であるビットの個数をカウントする

```c
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