ページ 11

ビット単位の入れ替え方

Posted: 2012年9月22日(土) 10:09
by きみどり
指定したビット同士を入れ替えをしてみたいです
&とか~とか^とか|とか>>を使って簡単に入れ替えできる式はないでしょうか?
コンパイラーはVC++2010EEです

Re: ビット単位の入れ替え方

Posted: 2012年9月22日(土) 10:35
by beatle
プログラムを考えなくて良いので,言葉でビット入れ替えのやり方を説明してみてください.
例えば,8ビットの数値の上下4ビットを入れ替えるには・・・
  • 8ビットの数値の名前を a とする.
    a=(b7, b6, b5, b4, b3, b2, b1, b0)
  • a を b にコピーする.
    a=(b7, b6, b5, b4, b3, b2, b1, b0)
    b=(b7, b6, b5, b4, b3, b2, b1, b0)
  • b の上位 4 ビットを 0 にする.
    a=(b7, b6, b5, b4, b3, b2, b1, b0)
    b=(0, 0, 0, 0, b3, b2, b1, b0)
  • b を左に 4 ビットシフトする.
    a=(b7, b6, b5, b4, b3, b2, b1, b0)
    b=(b3, b2, b1, b0, 0, 0, 0, 0)
  • a を右に 4 ビットシフトする.
    a=(0, 0, 0, 0, b7, b6, b5, b4)
    b=(b3, b2, b1, b0, 0, 0, 0, 0)
  • a と b のビット和を a に保存する.
    a=(b3, b2, b1, b0, b7, b6, b5, b4)
    b=(b3, b2, b1, b0, 0, 0, 0, 0)

Re: ビット単位の入れ替え方

Posted: 2012年9月22日(土) 12:10
by きみどり
beatle さんが書きました:プログラムを考えなくて良いので,言葉でビット入れ替えのやり方を説明してみてください.
言葉にすると
  • ビットの位置を指定し、8ビットの数値の名前を a とする.
  • aの一つ目に指定したビットをbにコピーする.
  • aの二つ目に指定したビットをcにコピーする.
  • b を二つ目に指定したビットシフトする.
  • c を一つ目に指定したビットシフトする.
  • aの指定したビットを0にする.
  • a と b とcのビット和を a に保存する.

Re: ビット単位の入れ替え方

Posted: 2012年9月22日(土) 12:42
by beatle
きみどりさんが書いたとおりにやってみますね.
一つ目に指定したビットを 0 ビットとします.
二つ目に指定したビットを 1 ビットとします.
0ビット目と1ビット目が入れ替われば成功ですね.
  • ビットの位置を指定し、8ビットの数値の名前を a とする.
    a=(0, 0, 0, 0, 0, 0, x, y)
  • aの一つ目に指定したビットをbにコピーする.
    a=(0, 0, 0, 0, 0, 0, x, y)
    b=(0, 0, 0, 0, 0, 0, 0, y)
  • aの二つ目に指定したビットをcにコピーする.
    a=(0, 0, 0, 0, 0, 0, x, y)
    b=(0, 0, 0, 0, 0, 0, 0, y)
    c=(0, 0, 0, 0, 0, 0, x, 0)
  • b を二つ目に指定したビットシフトする.
    どちら向きにシフトするか書かれていませんので適当に.(どうせ0ビットなのでシフトしませんが)
    a=(0, 0, 0, 0, 0, 0, x, y)
    b=(0, 0, 0, 0, 0, 0, 0, y)
    c=(0, 0, 0, 0, 0, 0, x, 0)
  • c を一つ目に指定したビットシフトする.
    どちら向きにシフトするか書かれていませんので適当に.(右シフトにしました)
    a=(0, 0, 0, 0, 0, 0, x, y)
    b=(0, 0, 0, 0, 0, 0, 0, y)
    c=(0, 0, 0, 0, 0, 0, 0, x)
  • aの指定したビットを0にする.
    a=(0, 0, 0, 0, 0, 0, 0, 0)
    b=(0, 0, 0, 0, 0, 0, 0, y)
    c=(0, 0, 0, 0, 0, 0, 0, x)
  • a と b とcのビット和を a に保存する.
    a=(0, 0, 0, 0, 0, 0, 0, x|y)
    b=(0, 0, 0, 0, 0, 0, 0, y)
    c=(0, 0, 0, 0, 0, 0, 0, x)
うーん,入れ替わりませんでした.

プログラムにだんだんと近づけるために,指定したビットをコピーする,というのはどうやるんだろう,ということを考えてみましょう.
何ビット目をコピーするかは固定ではなく,変数 n (0 ≦ n ≦ 7)で表されるとします.

8ビット整数 a の n ビット目を取り出したい!
例えば (0, 0, 0, 0, 0, 0, 0, 1) を n ビットだけ左シフトしたらどうなるでしょう.
0 ビットだけ左シフト (0, 0, 0, 0, 0, 0, 0, 1)
1 ビットだけ左シフト (0, 0, 0, 0, 0, 0, 1, 0)
2 ビットだけ左シフト (0, 0, 0, 0, 0, 1, 0, 0)

つまり,n ビットだけ左シフトすると n ビット目だけが 1 で,他が 0 となります.
これと変数 a のビット積を計算すると,a の n ビット目だけが取り出せますね!
その数値を目的の変数にコピーすれば完了です.

Re: ビット単位の入れ替え方

Posted: 2012年9月22日(土) 23:29
by きみどり
いろいろ試していたらできました

コード:

unsigned char bitCange( unsigned char a, unsigned char bit1, unsigned char bit2 ){
	unsigned char keep = a;					// コピーする
	a&=~(1<<bit2);							// bit2のビットを0にする
	a|= ( a&(1<<bit1) )>>(bit1-bit2);		// bit1とaの積を右にシフトしたものをaとの和をaに入れる
	a&=~(1<<bit1);							// bit1のビットを0にする
	a|= ( keep&(1<<bit2) )<<(bit1-bit2);	// bit2とkeepの積を左にシフトしたものをaとの和をaに入れる
	return date;
}
beatleさん参考になりましたありがとうございます

Re: ビット単位の入れ替え方

Posted: 2012年9月23日(日) 03:07
by かずま
きみどり さんが書きました:いろいろ試していたらできました
本当ですか?
bitCange(0x08, 1, 3) はいくつになりますか?

return a & ~(1<<b1 | 1<<b2) | (a>>b1 & 1)<<b2 | (a>>b2 & 1)<<b1;

Re: ビット単位の入れ替え方

Posted: 2012年9月23日(日) 08:21
by みけCAT
変数dateはどこから出てきたのですか?

Re: ビット単位の入れ替え方

Posted: 2012年9月23日(日) 09:47
by きみどり
かずま さんが書きました:本当ですか?bitCange(0x08, 1, 3) はいくつになりますか?
0になってました確かに入れ替えできてません
bit1はbit2より小さくしないといけないみたいですね
bti1-bit2でマイナスになっててシフトできなかったのが原因かも
みけCAT さんが書きました:変数dateはどこから出てきたのですか?
すみません書き間違いました

プログラム書き直しました

コード:

unsigned char bitCange( unsigned char a, unsigned char bit1, unsigned char bit2 ){
	unsigned char keep;
	// bit1がbit2より小さいなら入れ替える
	if( bit1 < bit2 ){
		keep = bit1;
		bit1 = bit2;
		bit2 = keep;
	}
	keep = a;								// コピーする
	a&=~(1<<bit2);							// bit2のビットを0にする
	a|= ( a&(1<<bit1) )>>(bit1-bit2);		// bit1とaの積を右にシフトしたものをaとの和をaに入れる
	a&=~(1<<bit1);							// bit1のビットを0にする
	a|= ( keep&(1<<bit2) )<<(bit1-bit2);	// bit2とkeepの積を左にシフトしたものをaとの和をaに入れる

	return a;
}
かずまさんみけCATさんご指摘ありがとうございます

Re: ビット単位の入れ替え方

Posted: 2012年9月23日(日) 10:46
by かずま
きみどり さんが書きました:&とか~とか^とか|とか>>を使って簡単に入れ替えできる式はないでしょうか?

コード:

unsigned bitSwap(unsigned a, int b1, int b2)
{
    return a & ~(1<<b1 | 1<<b2) | (a>>b1 & 1)<<b2 | (a>>b2 & 1)<<b1;
}
または

コード:

unsigned bitSwap(unsigned a, int b1, int b2)
{
    return (a>>b1 & 1) ? (a>>b2 & 1) ? a : a & ~(1<<b1) | 1<<b2
                       : (a>>b2 & 1) ? a & ~(1<<b2) | 1<<b1 : a;
}

Re: ビット単位の入れ替え方

Posted: 2012年9月23日(日) 22:04
by かずま
こんなのも考えられます。

コード:

unsigned bitSwap(unsigned a, int b1, int b2)
{
    return -((a>>b1 ^ a>>b2) & 1) & (1<<b2 | 1<<b1) ^ a;
}

Re: ビット単位の入れ替え方

Posted: 2012年9月24日(月) 19:27
by きみどり
いろいろとやり方があるのですね
式がすごく短くなったことに驚いています。
かずまさんいろいろとありがとうございした

Re: ビット単位の入れ替え方

Posted: 2012年9月25日(火) 04:02
by かずま
gcc だと次のように書いたほうが、最適化によりオブジェクトコードは短くなります。
ただし、gcc のバージョンによって長さは変わるようですが。

コード:

unsigned bitSwap(unsigned a, int b1, int b2)
{
    unsigned c = (a>>b1 ^ a>>b2) & 1;
    return (c<<b1 | c<<b2) ^ a;
}
VC++ 2008 では、次のように書かないと、c をメモリ上にとって、オブジェクトが
長くなってしまいました。

コード:

unsigned bitSwap(unsigned a, int b1, int b2)
{
    #define c ((a>>b1 ^ a>>b2) & 1)
    return (c<<b1 | c<<b2) ^ a;
}