テスト整数(バイナリ)は1個の数を含む
引用:中国のあるウイルス対策ソフト会社の2010年3月の筆記試験問題
出力結果はいくらですか?
答えは:8
最初はテーマを見ていたが、私はできなかった.自分はビット操作にあまり慣れていないので、これが1を含む個数を求めていることを知っていても、まだ納得していない.
どうしてn=n&(n-1)で1の個数を求めることができるのか.
後で分析して、少し分かりました.
説明は以下のとおりです.
例えばあるバイナリ数n=1 xxxについて...100
ではn-1=1 xxx...011
ではn&(n-1)=1 xx...000
これにより,n&(n−1)演算を行うたびにnの末尾1が消去され,これにより毎回1が消去され,最後にnが0となり,nにどれだけの1が含まれているかが分かる.
添付:
ある面接問題では、整数が2のn次であるかどうかを1つの式で判断するように要求されていますが、実質的には、その整数が1を含む個数が0であるかどうかを判断すればいいのです.式は次のように表されます.
!(n & (n-1) )
本当なら説明します.
#include <iostream>
using namespace std;
int func(int n)
{
int nCount = 0;
while( n )
{
nCount++;
n = n & (n-1);
}
return nCount;
}
int main(int argc, char *argv[])
{
cout << func( 9999 ) << endl;
return 0;
}
出力結果はいくらですか?
答えは:8
最初はテーマを見ていたが、私はできなかった.自分はビット操作にあまり慣れていないので、これが1を含む個数を求めていることを知っていても、まだ納得していない.
どうしてn=n&(n-1)で1の個数を求めることができるのか.
後で分析して、少し分かりました.
説明は以下のとおりです.
例えばあるバイナリ数n=1 xxxについて...100
ではn-1=1 xxx...011
ではn&(n-1)=1 xx...000
これにより,n&(n−1)演算を行うたびにnの末尾1が消去され,これにより毎回1が消去され,最後にnが0となり,nにどれだけの1が含まれているかが分かる.
添付:
ある面接問題では、整数が2のn次であるかどうかを1つの式で判断するように要求されていますが、実質的には、その整数が1を含む個数が0であるかどうかを判断すればいいのです.式は次のように表されます.
!(n & (n-1) )
本当なら説明します.
#include <stdio.h>
int GetOneCountsByDiv( int x )/* */
{
int n=0;
while( x )
{
if( x%2 ) n++;
x /=2 ;
}
return n;
}
int GetOneCountsByMoveR( int x )/* */
{
int n=0;
while( x )
{
if( x&1 ) n++;
x = x>>1;
}
return n;
}
int GetOneCountsByAnd( int x )/*n (n-1) */
{
int n=0;
while( x )
{
x &= (x-1);
n++;
}
return n;
}
int main(int argc, char *argv[])
{
printf( "%d", GetOneCountsByAnd(9) );
return 0;
}