1つの整数nのバイナリ表現の中の1の個数のいくつかの解法を統計します
整数nのバイナリ表現の1の個数を統計する.
分析:この問題にはいろいろな解法がある.
1.2を除いて余剰を取る方法:1つの整数の2進数の表示を求めるのはで、使う方法は2を除いて余剰を取るのです.本題については、余数1の個数を数えるだけです.
2.ビットモード法+シフト:1の変種で、シフトで2を除去し、この方法はより効率的である.ビットパターンを用いて,1と対応付け,1ビットを取得する.
3.モードビット法:n=n&(n-1);nとn-1のバイナリ表現を考慮すると,両者相&,n-1は常にnの最低位の1を0に置くことができる.
4.分而治之法:分析,nのバイナリは中位が1のビットのうち1を表し,そのビットの1の個数が1であることを表すこともできる.このカウントの性質に基づいて.
1つのnビットの整数のバイナリの表現の中で1の個数を要求します:
(1).nが1であれば、そのビットの値を返す.すなわち、そのビット上の1の個数である.
(2)n>1の場合、その前n/2ビットのうち1の個数+後n/2ビットのうち1の個数に等しい.
拡張問題1:整数nが2のべき乗であるかどうかを判断しますか?(tip: if(n && (n & (n-1)) == 0 ) return 1;)すなわち、そのバイナリ表現には1つしかない.
拡張問題2:整数nが4のべき乗であるかどうかを判断しますか?
解析:1つの整数が4のべき乗である場合、この数は2のべき乗であり、拡張問題によって知ると、そのバイナリ表現には1つしかない.
一方、1つの数が2のべき乗は必ずしも4のべき乗ではない.1つの数は4のべき乗であり、その数を満たす4進数表現のうち1つしかない.
すなわち、その数のバイナリの表現には1つしかない、その1はその数のバイナリが2 bitグループ(4進)を表す下位にしか現れず、
コードは次のように実装されます.
以上の拡張問題1,2により,整数nが2であるか否かを判断するk次べき乗p(p=2^k)のべき乗を設計することができる.
2のk乗のp(p=2^k)の整数乗のnに対して、nは以下を満たす.
『1』nの2進数表現のうち1桁だけが1であり、すなわち、nは2のべき乗である.
「2」nのp進数表現のうち1桁のみが1である、すなわち、nのバイナリ表現では、bitsをkビットでグループ化し、kビットグループの最下位ビットが1つのみである.
具体的な実装コードとそのテストは以下の通りです.
分析:この問題にはいろいろな解法がある.
1.2を除いて余剰を取る方法:1つの整数の2進数の表示を求めるのはで、使う方法は2を除いて余剰を取るのです.本題については、余数1の個数を数えるだけです.
2.ビットモード法+シフト:1の変種で、シフトで2を除去し、この方法はより効率的である.ビットパターンを用いて,1と対応付け,1ビットを取得する.
3.モードビット法:n=n&(n-1);nとn-1のバイナリ表現を考慮すると,両者相&,n-1は常にnの最低位の1を0に置くことができる.
4.分而治之法:分析,nのバイナリは中位が1のビットのうち1を表し,そのビットの1の個数が1であることを表すこともできる.このカウントの性質に基づいて.
1つのnビットの整数のバイナリの表現の中で1の個数を要求します:
(1).nが1であれば、そのビットの値を返す.すなわち、そのビット上の1の個数である.
(2)n>1の場合、その前n/2ビットのうち1の個数+後n/2ビットのうち1の個数に等しい.
拡張問題1:整数nが2のべき乗であるかどうかを判断しますか?(tip: if(n && (n & (n-1)) == 0 ) return 1;)すなわち、そのバイナリ表現には1つしかない.
int isPowerOf2(unsigned int n) {
if(n && (n & (n-1)）== 0) return 1;
return 0;
}拡張問題2:整数nが4のべき乗であるかどうかを判断しますか?
解析:1つの整数が4のべき乗である場合、この数は2のべき乗であり、拡張問題によって知ると、そのバイナリ表現には1つしかない.
一方、1つの数が2のべき乗は必ずしも4のべき乗ではない.1つの数は4のべき乗であり、その数を満たす4進数表現のうち1つしかない.
すなわち、その数のバイナリの表現には1つしかない、その1はその数のバイナリが2 bitグループ(4進)を表す下位にしか現れず、
コードは次のように実装されます.
int isPowerOf4(unsigned int n) {
if(n == 0) return 0;
if(n & (n-1) ) return 0; // 2 ；
return n & 0x55555555; //1 4 2bit
}以上の拡張問題1,2により,整数nが2であるか否かを判断するk次べき乗p(p=2^k)のべき乗を設計することができる.
2のk乗のp(p=2^k)の整数乗のnに対して、nは以下を満たす.
『1』nの2進数表現のうち1桁だけが1であり、すなわち、nは2のべき乗である.
「2」nのp進数表現のうち1桁のみが1である、すなわち、nのバイナリ表現では、bitsをkビットでグループ化し、kビットグループの最下位ビットが1つのみである.
具体的な実装コードとそのテストは以下の通りです.
#include
#include
int countBitsOf1(int n);
int numOfOnes_0(int n);
int numOfOnes_1(int n);
int numOfOnes_2(int n);
int numOfOnesInDecimalN(int n);
int main(int argc, char *argv[]) {
// printf("%d
", countBitsOf1(-1));
// printf("%d
", countBitsOf1(1));
// printf("%d
", countBitsOf1(0));
// printf("%d
", countBitsOf1(15));
char i;
for(i = 1; i; ++i) {
assert(numOfOnes_0(i) == countBitsOf1(i));
assert(numOfOnes_1(i) == countBitsOf1(i));
assert(numOfOnes_2(i) == countBitsOf1(i));
printf("number of 1 bit in %d is %d
", i, countBitsOf1(i));
}
return 0;
}
// n 1
int numOfOnesInDecimalN(int n) {
unsigned m = n > 0 ? n : -n;
int count = 0;
while(m) {
if(m%10 == 1) ++count;
m /= 10;
}
return count;
}
// n 1 : 2
int numOfOnes_0(int n) {
unsigned m = (unsigned)n;
int count = 0;
while(m) {
if(m%2) ++count;
m /= 2;
}
return count;
}
// n 1 : 2 ， +
int numOfOnes_1(int n) {
unsigned m = (unsigned)n;
int count = 0;
while(m) {
if(m & 1) ++count;
m >>= 1;
}
return count;
}
// n 1 : ：n&(n-1) n 1 0;
int numOfOnes_2(int n) {
int count = 0;
while(n) {
++count;
n = n & (n-1);
}
return count;
}
// n 1 bits
int countBitsOf1(int n) {
n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1); //2bits ， 2bit 2bit 1
n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2); //4bits
n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4); //8bits
n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8); //16bits
n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16); //32bits
return n;
}
number of 1 bit in 1 is 1
number of 1 bit in 2 is 1
number of 1 bit in 3 is 2
number of 1 bit in 4 is 1
number of 1 bit in 5 is 2
number of 1 bit in 6 is 2
number of 1 bit in 7 is 3
number of 1 bit in 8 is 1
number of 1 bit in 9 is 2
number of 1 bit in 10 is 2
number of 1 bit in 11 is 3
number of 1 bit in 12 is 2
number of 1 bit in 13 is 3
number of 1 bit in 14 is 3
number of 1 bit in 15 is 4
number of 1 bit in 16 is 1
number of 1 bit in 17 is 2
number of 1 bit in 18 is 2
number of 1 bit in 19 is 3
number of 1 bit in 20 is 2
number of 1 bit in 21 is 3
number of 1 bit in 22 is 3
number of 1 bit in 23 is 4
number of 1 bit in 24 is 2
number of 1 bit in 25 is 3
number of 1 bit in 26 is 3
number of 1 bit in 27 is 4
number of 1 bit in 28 is 3
number of 1 bit in 29 is 4
number of 1 bit in 30 is 4
number of 1 bit in 31 is 5
number of 1 bit in 32 is 1
number of 1 bit in 33 is 2
number of 1 bit in 34 is 2
number of 1 bit in 35 is 3
number of 1 bit in 36 is 2
number of 1 bit in 37 is 3
number of 1 bit in 38 is 3
number of 1 bit in 39 is 4
number of 1 bit in 40 is 2
number of 1 bit in 41 is 3
number of 1 bit in 42 is 3
number of 1 bit in 43 is 4
number of 1 bit in 44 is 3
number of 1 bit in 45 is 4
number of 1 bit in 46 is 4
number of 1 bit in 47 is 5
number of 1 bit in 48 is 2
number of 1 bit in 49 is 3
number of 1 bit in 50 is 3
number of 1 bit in 51 is 4
number of 1 bit in 52 is 3
number of 1 bit in 53 is 4
number of 1 bit in 54 is 4
number of 1 bit in 55 is 5
number of 1 bit in 56 is 3
number of 1 bit in 57 is 4
number of 1 bit in 58 is 4
number of 1 bit in 59 is 5
number of 1 bit in 60 is 4
number of 1 bit in 61 is 5
number of 1 bit in 62 is 5
number of 1 bit in 63 is 6
number of 1 bit in 64 is 1
number of 1 bit in 65 is 2
number of 1 bit in 66 is 2
number of 1 bit in 67 is 3
number of 1 bit in 68 is 2
number of 1 bit in 69 is 3
number of 1 bit in 70 is 3
number of 1 bit in 71 is 4
number of 1 bit in 72 is 2
number of 1 bit in 73 is 3
number of 1 bit in 74 is 3
number of 1 bit in 75 is 4
number of 1 bit in 76 is 3
number of 1 bit in 77 is 4
number of 1 bit in 78 is 4
number of 1 bit in 79 is 5
number of 1 bit in 80 is 2
number of 1 bit in 81 is 3
number of 1 bit in 82 is 3
number of 1 bit in 83 is 4
number of 1 bit in 84 is 3
number of 1 bit in 85 is 4
number of 1 bit in 86 is 4
number of 1 bit in 87 is 5
number of 1 bit in 88 is 3
number of 1 bit in 89 is 4
number of 1 bit in 90 is 4
number of 1 bit in 91 is 5
number of 1 bit in 92 is 4
number of 1 bit in 93 is 5
number of 1 bit in 94 is 5
number of 1 bit in 95 is 6
number of 1 bit in 96 is 2
number of 1 bit in 97 is 3
number of 1 bit in 98 is 3
number of 1 bit in 99 is 4
number of 1 bit in 100 is 3
number of 1 bit in 101 is 4
number of 1 bit in 102 is 4
number of 1 bit in 103 is 5
number of 1 bit in 104 is 3
number of 1 bit in 105 is 4
number of 1 bit in 106 is 4
number of 1 bit in 107 is 5
number of 1 bit in 108 is 4
number of 1 bit in 109 is 5
number of 1 bit in 110 is 5
number of 1 bit in 111 is 6
number of 1 bit in 112 is 3
number of 1 bit in 113 is 4
number of 1 bit in 114 is 4
number of 1 bit in 115 is 5
number of 1 bit in 116 is 4
number of 1 bit in 117 is 5
number of 1 bit in 118 is 5
number of 1 bit in 119 is 6
number of 1 bit in 120 is 4
number of 1 bit in 121 is 5
number of 1 bit in 122 is 5
number of 1 bit in 123 is 6
number of 1 bit in 124 is 5
number of 1 bit in 125 is 6
number of 1 bit in 126 is 6
number of 1 bit in 127 is 7
number of 1 bit in -128 is 25
number of 1 bit in -127 is 26
number of 1 bit in -126 is 26
number of 1 bit in -125 is 27
number of 1 bit in -124 is 26
number of 1 bit in -123 is 27
number of 1 bit in -122 is 27
number of 1 bit in -121 is 28
number of 1 bit in -120 is 26
number of 1 bit in -119 is 27
number of 1 bit in -118 is 27
number of 1 bit in -117 is 28
number of 1 bit in -116 is 27
number of 1 bit in -115 is 28
number of 1 bit in -114 is 28
number of 1 bit in -113 is 29
number of 1 bit in -112 is 26
number of 1 bit in -111 is 27
number of 1 bit in -110 is 27
number of 1 bit in -109 is 28
number of 1 bit in -108 is 27
number of 1 bit in -107 is 28
number of 1 bit in -106 is 28
number of 1 bit in -105 is 29
number of 1 bit in -104 is 27
number of 1 bit in -103 is 28
number of 1 bit in -102 is 28
number of 1 bit in -101 is 29
number of 1 bit in -100 is 28
number of 1 bit in -99 is 29
number of 1 bit in -98 is 29
number of 1 bit in -97 is 30
number of 1 bit in -96 is 26
number of 1 bit in -95 is 27
number of 1 bit in -94 is 27
number of 1 bit in -93 is 28
number of 1 bit in -92 is 27
number of 1 bit in -91 is 28
number of 1 bit in -90 is 28
number of 1 bit in -89 is 29
number of 1 bit in -88 is 27
number of 1 bit in -87 is 28
number of 1 bit in -86 is 28
number of 1 bit in -85 is 29
number of 1 bit in -84 is 28
number of 1 bit in -83 is 29
number of 1 bit in -82 is 29
number of 1 bit in -81 is 30
number of 1 bit in -80 is 27
number of 1 bit in -79 is 28
number of 1 bit in -78 is 28
number of 1 bit in -77 is 29
number of 1 bit in -76 is 28
number of 1 bit in -75 is 29
number of 1 bit in -74 is 29
number of 1 bit in -73 is 30
number of 1 bit in -72 is 28
number of 1 bit in -71 is 29
number of 1 bit in -70 is 29
number of 1 bit in -69 is 30
number of 1 bit in -68 is 29
number of 1 bit in -67 is 30
number of 1 bit in -66 is 30
number of 1 bit in -65 is 31
number of 1 bit in -64 is 26
number of 1 bit in -63 is 27
number of 1 bit in -62 is 27
number of 1 bit in -61 is 28
number of 1 bit in -60 is 27
number of 1 bit in -59 is 28
number of 1 bit in -58 is 28
number of 1 bit in -57 is 29
number of 1 bit in -56 is 27
number of 1 bit in -55 is 28
number of 1 bit in -54 is 28
number of 1 bit in -53 is 29
number of 1 bit in -52 is 28
number of 1 bit in -51 is 29
number of 1 bit in -50 is 29
number of 1 bit in -49 is 30
number of 1 bit in -48 is 27
number of 1 bit in -47 is 28
number of 1 bit in -46 is 28
number of 1 bit in -45 is 29
number of 1 bit in -44 is 28
number of 1 bit in -43 is 29
number of 1 bit in -42 is 29
number of 1 bit in -41 is 30
number of 1 bit in -40 is 28
number of 1 bit in -39 is 29
number of 1 bit in -38 is 29
number of 1 bit in -37 is 30
number of 1 bit in -36 is 29
number of 1 bit in -35 is 30
number of 1 bit in -34 is 30
number of 1 bit in -33 is 31
number of 1 bit in -32 is 27
number of 1 bit in -31 is 28
number of 1 bit in -30 is 28
number of 1 bit in -29 is 29
number of 1 bit in -28 is 28
number of 1 bit in -27 is 29
number of 1 bit in -26 is 29
number of 1 bit in -25 is 30
number of 1 bit in -24 is 28
number of 1 bit in -23 is 29
number of 1 bit in -22 is 29
number of 1 bit in -21 is 30
number of 1 bit in -20 is 29
number of 1 bit in -19 is 30
number of 1 bit in -18 is 30
number of 1 bit in -17 is 31
number of 1 bit in -16 is 28
number of 1 bit in -15 is 29
number of 1 bit in -14 is 29
number of 1 bit in -13 is 30
number of 1 bit in -12 is 29
number of 1 bit in -11 is 30
number of 1 bit in -10 is 30
number of 1 bit in -9 is 31
number of 1 bit in -8 is 29
number of 1 bit in -7 is 30
number of 1 bit in -6 is 30
number of 1 bit in -5 is 31
number of 1 bit in -4 is 30
number of 1 bit in -3 is 31
number of 1 bit in -2 is 31
number of 1 bit in -1 is 32