Number of 1 Bits(32ビットの2進数の中で1のを求めます)
3259 ワード
<span style="font-size:24px;">
</span>1.テーマ:
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation
00000000000000000000000000001011 , so the function should return 3. 2.ビット演算を熟知している:
1,&(ビットごとに)概念的には,演算に関与する2つの成分に対応する各ビットを論理と演算し,両者が真(1に等しい)であれば結果が真(1に等しい)となる.そうでなければ、すべて偽(0に等しい)です.すなわち、1&1=1、1&0=0、0&1=0、0&0=0ここではまず、7&8=0000 0111&0000 1000=0000=0 7&6=0000 0111&0000 0110=6の8ビットバイナリの例を見てみましょう.
2、|(ビットまたは)は、演算に参加する各成分に対応する各ビットを論理または演算する、すなわち、両者が偽(0)の場合、偽(0)であり、そうでなければ真である.すなわち、0|0=0、1|0=1、0|1=1、1|1=1の8ビットバイナリの例を見ると、7|8=0000 0111|0000 1000=0000 1111=15 7|6=0000 0111|0000 0111=7
3、^(ビット別OR)は、演算に参加する各成分に対応する各ビットを異或演算する、すなわち、両者は同じ偽であり、真ではない.すなわち、0|0=0、1|0=1、0|1=1、1|1=0以下の例を見ると、7^8=0000 0111^0000 1000=0000 0111=7 7 7^6=0000 0111^0000 0100=0000 0011=3
4,~(ビットごとに逆をとる)すなわち,バイナリビットの各ビットを逆をとる演算を行い,簡単に言えば1が0になり,0が1になる.直接例:~7=~0000 0111=1111 1000=248
5>(ビットを右に移動)バイナリビット全体を右に移動します.7>>1=0000 0111>=1=0000 0011=3 7>>2=0000 0111>>2=0000 0001=1ここで右シフトは2を除いたN次数に等しく、Nは右シフトの桁数である.
6<<(左シフト)ここでは詳しくは述べないが,右シフトとは逆である.
3.uint 8_についてt,uint16_t,uint32_t等
<span style="font-size:24px;">int hammingWeight(uint32_t n)
{
int weight = 0;
while (n)
{
if ((n & 1) == 1)
{
weight++;
}
n = n >> 1;
}
return weight;
}</span>アルゴリズムの説明:考えやすいが、効率が低い
したがって,n&(n−1)反復のたびに右端の非ゼロ位置を常にゼロにすることで効率を向上させる非ゼロビットを見つけて比較したいだけである.
奇数(nのバイナリ表現の末尾は1):n:xxxxxxx 1 n-1:xxxxx 0 n&(n-1):xxxxxxx 0は右端の1を削除することに相当する.nが偶数で0に等しくない(nのバイナリ表現の末尾は0):n:xxxxx 1000 n-1:xxxxx 0111 n&(n 1-):xxxxx 0000も右端を除く1に相当する.
<span style="font-size:24px;">int sparse_popcnt(unsigned int n)
{
int count = 0;
while (n)
{
++count;
n &= (n - 1);
}
return count;
}</span>5.具体的な実装で発生する可能性のある問題:
cout<<"DEC:"<<dec<<n<<endl; //
cout<<"OCT:"<<oct<<n<<endl;//
cout<<"HEX:"<<hex<<n<<endl;// cout << hex<<n << endl;
cout.unsetf(ios::hex);