技術者のためのビット演算のまとめ


#技術者のためのビット演算のまとめ
個人的にビット演算をまとめた。

言語はｃ言語とCASLⅡを想定している。
シフトは論理シフト（符号なしのシフト）を想定している。

（注意）
本資料は考え方を示したもので、未定義動作については各自で考えてください。


##基本演算
###AND
 A & 0 = 0, A & 1 = A

＜使用例＞
nビット目を0にする

```c
	x & ~(1U << n);
```
(注意）「1U」は、unsignedの定数1であることを表す。

＜使用例＞
スウィッチがPORTAの4ビット目に割り当てられており、
負論理（0でONと考える）のとき、次のように実装する。

```c
#define BIT4 (0x10)

	if ((PORTA & BIT4) == 0) {
		// スウィッチがONのときの処理を行う
	}
```

＜使用例＞
変数ｘの偶数・奇数を判定する。
AND演算を使った方法であるが、CASLⅡでは有用である。

```c
#define BIT0 (0x01)		// LSB

	if ((x & BIT0) == 0) {
		// 偶数のときの処理を行う
	} else {
		// 奇数のときの処理を行う
	}
```

＜使用例＞
変数ｘの16（2の4乗）で割った余りを求める。
AND演算を使った方法であるが、CASLⅡでは有用である。
ただし、2の累乗で割った余りしか求めることができない。

```c
	x & 0x0f;
```


###OR
 A | 0 = A, A | 1 = 1

＜使用例＞
nビット目を1にする

```c
	x | (1U << n);
```
(注意）「1U」は、unsignedの定数1であることを表す。

###XOR
 A ^ 0 = A, A ^ 1 = ~A
 A ^ A = 0
 A ^ B = B ^ A

＜使用例＞
nビット目を反転する

```c
	x ^ (1U << n);
```
(注意）「1U」は、unsignedの定数1であることを表す。
	
＜使用例＞
汎用レジスタGR1をゼロにする。

〇CASLⅡの場合
```
;XORを使って、GR1をゼロにする
MAIN   START                
        LAD     GR1,#A5A5
        XOR     GR1,GR1		; #A5A5がゼロになる
        RET
        END 
```

＜使用例＞
xを反転する

〇CASLⅡの場合
```
MAIN	START
		LD	GR1,=#A55A
		XOR	GR1,=#FFFF	; GR1を反転する（#A55Aが#5AA5になる）
		RET
		END
```

＜使用例＞
共通鍵暗号方式のように暗号化、復号ができる。

〇CASLⅡの場合
```
;XOR暗号
MAIN    START
        LAD     GR1,#1234       ;送りたいデータ
        LAD     GR2,#ABCD       ;共通鍵
;
        XOR     GR1,GR2         ;送信側は、暗号化したデータ#B9F9を送る
;
        XOR     GR1,GR2         ;受信側は、複号化して#1234を得る
        RET
        END
```

＜使用例＞
xとyを交換するマクロ

〇C言語の場合

```c
#include <stdio.h>

#define swap(x, y) (x^=y, y^=x, x^=y)

/*
<実行結果>
作業用の変数を使わずに、変数aと変数bの中身を交換します。
x = 5a5a5a5a  y = a5a5a5a5
x = a5a5a5a5  y = 5a5a5a5a
*/

int main(void)
{
    unsigned int    x = 0x5a5a5a5a, y = 0xa5a5a5a5;

    printf("作業用の変数を使わずに、変数aと変数bの中身を交換します。\n");
    printf("x = %x  y = %x \n", x, y);

    swap(x,y);
	
    printf("x = %x  y = %x \n", x, y);
	return 0;
}
```

＜解説＞
x(x)、x(y)を、それぞれxの中身はx、xの中身はyを表すこととする。

最初x(x)、y(y)である。
「x」 <-- x^y, 「y」 <-- y^x, 「x」 <-- x^yを順に実行すると
「x(x^y)」                            　<-- x(x)   ^ y(y)
「y(y^x^y) = y(y^y^x) = y(0^x) = y(x)」 <-- y(y)   ^ x(x^y)
「x(x^y^x) = x(x^x^y) = x(0^y) = x(y)」 <-- x(x^y) ^ y(x) 
となり、 最終的にy(x)、x(y)となる。

〇CASLⅡの場合
XOR演算を使った交換はCASLⅡでも使える。
文法的に正しくても、RAMやROMがたった1バイト足りなくても
コンパイルエラーのなる場合がある。

だから、個人的な意見ですが、この交換は実用性はあると思う。

```
;作業用の汎用レジスタを使わずに、GR1とGR2の中身を交換します。
MAIN    START
    LAD GR1,#5A5A
    LAD GR2,#A5A5
;
    XOR GR2,GR1
    XOR GR1,GR2
    XOR GR2,GR1
    RET
    END

```


###NOT

＜使用例＞
	すべて1のビット列を生成する。

〇C言語の場合
```c
	~0U;
```

(注意）「0U」は、unsignedの定数0であることを表す。

###シフト
シフト演算には、論理シフトと算術シフトがある。
論理シフトは符号なしのシフト、算術シフトは符号つきのシフト
と考えればよい。

この資料では、論理シフトを想定している。


###二の補数
2の補数には、2通りの求め方がある。
　-x は ~x + 1　
  または
　-x は ~(x - 1)
である。
  
＜解説＞
　-x = ~x + 1に、x = x - 1を代入する
　-(x - 1) = ~(x - 1) + 1
　-x + 1 = ~(x - 1) + 1
　∴ -x = ~(x - 1)

##ループの代わりに、シフト演算を用いるビット操作

###１になっているビットの数を数える

```c
#include <stdio.h>

//ビット列で、1の数を数える
//
//＜実行結果＞
//ビット列は8ビットとする。
//ビット列= b7
//1の数は6です。

int main(void) 
{
    unsigned char x = 0xb7; //2進数で(1011 0111)である。
    
    printf("ビット列は8ビットとする。\n");
    printf("ビット列 = %x\n", x);
    
    x = (x & 0x55) + ((x & 0xaa) >> 1);
    x = (x & 0x33) + ((x & 0xcc) >> 2);
    x = (x & 0x0f) + ((x & 0xf0) >> 4);
    
    printf("1の数は%dです。\n", x);
    return 0;
}
```


###ビット列を逆転する

```c
#include <stdio.h>

//ビット列を逆転させる
//
//＜実行結果＞
//ビット列は8ビットとする。
//逆転する前のビット列 = 0xb7
//逆転した後のビット列 = 0xed

int main(void) 
{
    unsigned char x = 0xb7; //　2進数1011 0111 -> 1110 1101
    
    printf("ビット列は8ビットとする。\n");
    printf("逆転する前のビット列 = 0x%x\n", x);
    
    x = ((x & 0x55) << 1) | ((x & 0xaa) >> 1);
    x = ((x & 0x33) << 2) | ((x & 0xcc) >> 2);
    x = ((x & 0x0f) << 4) | ((x & 0xf0) >> 4);
    
    printf("逆転した後のビット列 = 0x%x\n", x);
    
    return 0;
}
```


###「1になっている一番上(左)の桁」を求める

```c
#include <stdio.h>

//1である最も下位のビットを抽出する
//
//＜実行結果＞
//ビット列は8ビットとする。
//対象のビット列  = 0xb8
//抽出したビット列 = 0x08
//
int main(void) 
{
    unsigned char x = 0x4b; //2進数0010 1011
    
    printf("ビット列は8ビットとする。\n");
    printf("対象のビット列   = 0x%02x\n", x);
    
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x ^ (x >> 1);
    
    printf("抽出したビット列 = 0x%02x\n", x);
    return 0;
}
```

##グレイコードを作る

```c
#include <stdio.h>

/*
グレイコードを出力する

＜実行結果＞
ビット数: 3
* 3ビットのグレイコード *
000
001
011
010
110
111
101
100
*/

//ビット列を表示する
//uiBits:ビット列, iNoBits:表示するビット数
void display_bits( unsigned int uiBits , int    iNoBits)
{
    unsigned int uiMask;
    int          i = 0;
    
    iNoBits = (iNoBits < (sizeof(unsigned int) * 8)) ? iNoBits : (sizeof(unsigned int) * 8);
    uiMask  = 1 << (iNoBits - 1);
  
    do {
        printf( "%1d", ((uiBits & uiMask) != 0) ? 1 : 0 );
        
        if ( ((iNoBits - ++i) % 4) == 0 ) //4ビットずつスペースを入れる
            printf(" ");
        
    } while ( uiMask >>= 1 );
    
    printf("\n");
}

int main(void) 
{
    int             iNoBits;
    unsigned int    i, uiGreyCode;
    
    printf("ビット数: ", iNoBits);
    scanf("%d", &iNoBits);
    printf("* %dビットのグレイコード *\n", iNoBits);
    
    for ( i = 0; i <= (unsigned int)((2 << (iNoBits - 1)) - 1); i++) {
        uiGreyCode = i ^ (i >> 1);
        display_bits(uiGreyCode, iNoBits);
    }
    
    return 0;
}
```

##最も右のビットに関する操作

###最も右の0を抽出する

```c
	~x & (x + 1);
```

###最も右の1を抽出する

```c
	x & (-x);
	または
	(x ^ (x - 1)) & x;
```

###最も右の1を削除する

```c
	x & (x - 1);
```
	
##ビット列の操作
###maskbits
```c
#include <stdio.h>
/*
＜実行結果＞
mask_bits( 2,  3) = 0x0000001c
mask_bits( 0, 31) = 0x7fffffff
mask_bits( 0, 32) = 0xffffffff
mask_bits( 0,  1) = 0x00000001
*/

/*
マスクビット列を生成するマクロ
p :　ビット位置 0～
n :　ビット長（ビット位置からMSBの向きに数える）1～　（注意）0は不可である。
(例)
maskbits( 2,  3)
2ビット目の位置からMSBの向きに、3ビット分"1"を立てたマスクビット列を生成する。
(2ビット目, 3ビット目, 4ビット目が"1"となり、マスクビット列は0x1cとなる。）
*/
#define	maskbits(p, n) ((~(~0U << (n))) << (p))

void main(void)
{
	printf("mask_bits( 2,  3) = 0x%08x\n", maskbits(2,  3));
	printf("mask_bits( 0, 31) = 0x%08x\n", maskbits(0, 31));
	printf("mask_bits( 0, 32) = 0x%08x\n", maskbits(0, 32));
	printf("mask_bits( 0,  1) = 0x%08x\n", maskbits(0,  1));
}
```


###getbits
```c
#include <stdio.h>
typedef unsigned int uint;
#define	maskbits(p, n) ((~(~0U << (n))) << (p))
/*
ビット列を取り出す
x :　対象のビット列
p :　ビット位置
n :　ビット長（ビット位置からMSBの向きに数える）
(例)
getbits(0x5aa5, 2, 5);
0x5aa5のビット列から、2ビット目の位置からMSBの向きに、5ビット分取り出す。
getbitsの戻り値は、9となる。
*/

uint getbits(uint x, uint p, uint n) {
	return (x & maskbits(p, n)) >> p;
}

void main(void)
{
	printf("getbits = 0x%04x\n", getbits(0x5aa5, 2, 5));
}
```


###setbits
```c
#include <stdio.h>
typedef unsigned int uint;
#define	maskbits(p, n) ((~(~0U << (n))) << (p))

/*
ビット列ｘにビット列ｙをセットする
x :　対象のビット列
p :　ビット位置
n :　ビット長（ビット位置からMSBの向きに数える）
y :　セットするビット列

(例)
setbits(0x5aa5, 2, 5, 0x13) = 0x5acd
0x5aa5のビット列から、2ビット目の位置からMSBの向きに5ビット分の領域に、0x13をセットする。
*/

uint setbits(uint x, uint p, uint n, uint y){ 
	return (x & ~maskbits(p, n)) | ((y << p) & maskbits(p, n)); 
} 

void main(void)
{
	
	printf("setbits(0x5aa5, 2, 5, 0x13) = 0x%04x\n", setbits(0x5aa5, 2, 5, 0x13));
}
```
##SPECIAL THANKS

『The Art of Computer Programming Volume 4, 
Fascicle 1 Bitwise Tricks & Techniques;
Binary Decision Diagarms 日本語版 』
Donald E. Knuth (著) ; アスキー・メディアワークス

『ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか』
ヘンリー・S. ウォーレン,ジュニア (著) ; エスアイビーアクセス

  [明日使えないすごいビット演算](https://www.slideshare.net/KMC_JP/slide-www/)

  [プログラムを高速化する話](https://www.slideshare.net/KMC_JP/ss-45855264/)