LoginSignup
1
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@aocyan

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

Last updated at Posted at 2022-01-03

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

個人的にビット演算をまとめた。

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

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

基本演算

AND

A & 0 = 0, A & 1 = A

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

	x & ~(1U << n);

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

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

# define BIT4 (0x10)

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

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

# define BIT0 (0x01)		// LSB

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

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

	x & 0x0f;

OR

A | 0 = A, A | 1 = 1

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

	x | (1U << n);

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

XOR

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

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

	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言語の場合

# 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言語の場合

	~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)

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

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

# 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;
}

ビット列を逆転する

# 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になっている一番上(左)の桁」を求める

# 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;
}

グレイコードを作る

# 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を抽出する

	~x & (x + 1);

最も右の1を抽出する

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

最も右の1を削除する

	x & (x - 1);

ビット列の操作

maskbits

# 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

# 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

# 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. ウォーレン,ジュニア (著) ; エスアイビーアクセス

明日使えないすごいビット演算

プログラムを高速化する話

1
5
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?