アルゴリズム学習ノート(5)------ビット演算のtips

コンピュータにはすべてのデータがバイナリ形式で格納されています.ビット演算は、メモリ内のバイナリデータを直接操作するため、データの処理速度が非常に速い.
実際のプログラミングでは、ビット操作を巧みに運用すれば、四両千斤の効果を完全に達成することができ、ビット操作のこれらの利点だけに、ビット操作は各IT会社の筆記試験の面接でずっとホットな問題である.
以下、位置演算のコツをまとめて自分で勉強します.ほとんどはネット上から来ています.

は2つの整数を交換する(注意:コンパイラではdoubleまたはfloatに対するビット演算がエラーを報告する)

int swap(int &a, int &b)
{
	if (a != b)
	{
		a ^= b;
		b ^= a;
		a ^= b;
	}
	return 0;
}

第1のステップa=a^b、第2のステップb=a^b=(a^b)^b=a^(b^b)=a;ステップ3:a=a^b=(a^b)^a=(a^a)^b=b、交換済み、よく理解していない場合は自分で数のバイナリを書いてテストできます.

変換記号------変換記号は、1つの数を正数から負数に、負数から整数に、例えば、8-----000000,000,000に、その数を逆にする、11110111+1------111000------8

である.

int SignReversal(int a)
{
	return (~a + 1);
}

    絶対値を求める
まず、この数が負数であるか否かを判断し、31ビット右にシフトして符号ビットを得、符号ビットが−1であれば負数、符号ビットが0であれば正数とする.交換シンボルから,負数が整数に特化するとビットが逆+1になることが分かった.

int abs(int a)
{
	int flag = (a >> 31);
	return (flag == 0) ? a: (~a + 1);
}

以上の方法コードを最適化することもでき,いずれの数も0に等しいか,−1,すなわち0 XFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFしたがって、コードは以下のように書くことができます.

int myAbs(int a)
{
	int flag = (a >> 31);
	return ((a^flag) - flag);
}

高低位交換-------
この数の上位8桁を「高位」、後8桁を「低位」と呼び、この数の「高位」を「低位」に、「低位」を「高位」に変換することを要求する符号なしの16桁を与える.この数の16ビットがx 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 y 1 y 2 y 3 y 4 y 5 y 6 y 7 y 8であると仮定し、そのビットを8ビット右にシフトすると、高位は自動的に0を補い、結果として00000000 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8となり、そのビットを左に8ビットシフトし、その低位は自動的に0を補い、y 1 y 2 y 3 y 4 y 5 y 6 y 8 00000000となり、この2つの結果も高低ビットを交換することができ、コードは以下の通りである.

#include<iostream>
#include<string>
using namespace std;
template <class T> 
void printBinary(T a)
{
	for (int i=sizeof(a)*8-1; i>=0; i--)
	{
		if ((a >> i) == 1)
			cout <<'1';
		else 
			cout << '0';
		if (i == (sizeof(a)*8-1)/2+1)
			cout <<' ';
	}
	cout << endl;
}

int main()
{
	unsigned short a;
	unsigned short b;
	cin >> a;
	b = ((a>>8)|(a<<8));
	printBinary(a);
	printBinary(b);
	return 0;
}