1バイトをビット単位で反転する
2126 ワード
長い間C言語のビット操作をしたことがなくて、今日再び温めて、そして前に自分で同僚と話したことがある1つの問題をして、1つのバイトをビットごとに反転して、例えば、バイナリ数(10010011)があって、反転した後に(11001001)になります.
この問題はやはり簡単で、C言語を学んだことがある人はすべて解決することができると信じて、簡単に言えば、1つの循環をすればいいですが、もっと高い効率を得るためには、多くの研究があります.
まず1バイトの場合を見ないでください.1バイトが長すぎるからです.2つのバイナリビットしかない場合、どうなっているか見てみましょう.
仮に2制数a=01 Bがあるとする、反転後は10 Bであり、同様に、元が10 Bである、反転後は01 Bである.もう一度やってみると、元が11 Bか00 Bであれば、反転後は変わらないことがわかります.このとき、2つのバイナリ数の反転アルゴリズムを以下のように書くことができます.
if( a == 01B || a == 10B )
a ^= 11B;
else
a = a;
ご存知のように、あるバイナリ数のあるビットに1つずつ、それを逆にすることができるので、上のa^=11 Bは実際にaをビットで逆にする、すなわち01 Bから10 Bに、あるいは10 Bから01 Bに変えることで、彼らが反転を実現していることがわかります.
広くなると、1バイトを反転する、実は0位と7位を交換し、1位と6位を交換するなどしている.では、上の式は広くできるのでしょうか.実は可能です.
a=10001100 Bが設けられている.
a^=1000001 Bを実行します.
このとき、aのバイナリ数は00001101 Bで、0位と7位が入れ替わりました!普及すると、a^=01000010 Bは交換1位と6位、a^=00100100 Bは2位と5位など…….
では、私たちはこの問題の解法を実現しましたか?いいえ!私たちはさっき0位と7位が等しいとき、1位と6位が等しいときなどを考えていなかったからです.2つの対応ビットが等しい場合、上記の反転アルゴリズムに基づいて、異或演算を実行すべきではないので、現在の任務は対応ビットが等しいかどうかを弁明することである.
2つのビットが等しいかどうかを見分ける良い方法はありますか?
振り返ってみると、ヒントを与えてくれるのは2ビットのバイナリ数aだけで、a=11 Bと仮定すると、この数にはどんな特徴があるのでしょうか.(a|11 B)==aである、a=01 B,10 B,00 Bの場合、このようなことは起こらないことが分かった.このようにして11 Bの特殊な状況を認識すると、a=00 Bという状況もありますが、何が特別なのでしょうか.よく考えてみると、賢い読者はa=00 Bの場合、(a^11 B)=(a|11 B)、a=01 B、10 B、11 Bの場合、この式は成立しないことに気づいているかもしれません.そうすれば、00 Bの特殊な状況を認識することができます.
上記のように2ビットバイナリから8ビットバイナリに広める方法を行い、上の識別アルゴリズムも8ビットに広げた後、プログラムを書くのは以下の通りである.
これでバイトをビット単位で反転するプログラムが出てきましたが、勉強好きな読者は満足しないと信じていますが、それを最適化するアルゴリズムはありますか?頭を働かせて、もちろんあります!
引用:[url]http://lanphaday.bokee.com/3788582.html[/url]
この問題はやはり簡単で、C言語を学んだことがある人はすべて解決することができると信じて、簡単に言えば、1つの循環をすればいいですが、もっと高い効率を得るためには、多くの研究があります.
まず1バイトの場合を見ないでください.1バイトが長すぎるからです.2つのバイナリビットしかない場合、どうなっているか見てみましょう.
仮に2制数a=01 Bがあるとする、反転後は10 Bであり、同様に、元が10 Bである、反転後は01 Bである.もう一度やってみると、元が11 Bか00 Bであれば、反転後は変わらないことがわかります.このとき、2つのバイナリ数の反転アルゴリズムを以下のように書くことができます.
if( a == 01B || a == 10B )
a ^= 11B;
else
a = a;
ご存知のように、あるバイナリ数のあるビットに1つずつ、それを逆にすることができるので、上のa^=11 Bは実際にaをビットで逆にする、すなわち01 Bから10 Bに、あるいは10 Bから01 Bに変えることで、彼らが反転を実現していることがわかります.
広くなると、1バイトを反転する、実は0位と7位を交換し、1位と6位を交換するなどしている.では、上の式は広くできるのでしょうか.実は可能です.
a=10001100 Bが設けられている.
a^=1000001 Bを実行します.
このとき、aのバイナリ数は00001101 Bで、0位と7位が入れ替わりました!普及すると、a^=01000010 Bは交換1位と6位、a^=00100100 Bは2位と5位など…….
では、私たちはこの問題の解法を実現しましたか?いいえ!私たちはさっき0位と7位が等しいとき、1位と6位が等しいときなどを考えていなかったからです.2つの対応ビットが等しい場合、上記の反転アルゴリズムに基づいて、異或演算を実行すべきではないので、現在の任務は対応ビットが等しいかどうかを弁明することである.
2つのビットが等しいかどうかを見分ける良い方法はありますか?
振り返ってみると、ヒントを与えてくれるのは2ビットのバイナリ数aだけで、a=11 Bと仮定すると、この数にはどんな特徴があるのでしょうか.(a|11 B)==aである、a=01 B,10 B,00 Bの場合、このようなことは起こらないことが分かった.このようにして11 Bの特殊な状況を認識すると、a=00 Bという状況もありますが、何が特別なのでしょうか.よく考えてみると、賢い読者はa=00 Bの場合、(a^11 B)=(a|11 B)、a=01 B、10 B、11 Bの場合、この式は成立しないことに気づいているかもしれません.そうすれば、00 Bの特殊な状況を認識することができます.
上記のように2ビットバイナリから8ビットバイナリに広める方法を行い、上の識別アルゴリズムも8ビットに広げた後、プログラムを書くのは以下の通りである.
#include "stdafx.h"
int main(int argc, char* argv[])
{
unsigned char a, b, c;
a = 17;
if( ( b = a | 0x81 ) != a
&& ( c = a^0x81 ) != b )
a = c;
if( ( b = a | 0x42 ) != a
&& ( c = a^0x42 ) != b )
a = c;
if( ( b = a | 0x24 ) !=
&& ( c = a^0x24 ) != b )
a = c;
if( ( b = a | 0x18 ) != a
&& ( c = a^0x18 ) != b )
a = c;
printf("%d
", a );
return 0;
}
これでバイトをビット単位で反転するプログラムが出てきましたが、勉強好きな読者は満足しないと信じていますが、それを最適化するアルゴリズムはありますか?頭を働かせて、もちろんあります!
引用:[url]http://lanphaday.bokee.com/3788582.html[/url]