[答503] ２進法での１と０の個数

'


[答503] ２進法での１と０の個数


　1，10，11，100，101，……，1000000000 と、1 から 512 までの自然数を２進法で書くとき、

　書かれる数字「0」の個数と「1」の個数との差は？


[解答1]

　まず、２進法で９桁以下の数 1 から 511＝111111111₍₂₎ で考えます。

　511 ，1 と 510 ，2 と 509 ，…… ，255 と 256 のような

　和が 511 になる数を対にして(ただし 511 は単独で)、２進法で表せば、

　111111111 ，1 と 111111110 ，10 と 111111101 ，…… ，11111111 と 100000000 のように、

　各対に「1」が９個ずつあるから、「1」の個数は、9･256＝2304 です。

　使われる数字全部の個数は、

　１桁の数が 1 個、２桁の数が 2 個、３桁の数が 2² 個、…… だから、　

　1＋2･2＋3･2²＋……＋9･2⁸ で、直接計算しても求められますが、

　1＋2･2＋3･2²＋……＋n･2^n-1＝1－(n＋1)･2ⁿ＋n･2ⁿ⁺¹ より

　1＋2･2＋3･2²＋……＋9･2⁸＝1－10･2⁹＋9･2¹⁰＝4097 です。

　よって、「0」の個数は、4097－2304＝1793 となり、

　「0」の個数と「1」の個数との差は、2304－1793＝511 、

　512＝1000000000₍₂₎ は「0」が「1」より８個多いので、答は、511－8＝503 です。


[解答2]

　まず、２進法で９桁以下の数 1 から 511＝111111111₍₂₎ で考えます。

　例えば、２進法で４桁の数は、1000，1001，1010，1011，1100，1101，1110，1111 ですが、

　最高位の「1」を除けば、000，001，010，011，100，101，110，111 となって、

　000 と 111 ，001 と 110 ，010 と 101 ，011 と 100 を対応させることによって、

　「0」と「1」が同数であることがいえます。

　これは、２進法で表した何桁の数についてもいえることですので、

　２進法で９桁以下の数 1 から 511＝111111111₍₂₎ までで、

　最高位の「1」の 511 個だけ「1」の個数が多いことになります。

　512＝1000000000₍₂₎ は「0」が「1」より８個多いので、答は、511－8＝503 です。


[解答3]

　1，10，11，100，101，……，1000000000 を縦に並べ、各桁で「1」が「0」より何個多いかを求めます。

　１番右の桁は 101010……10 だから同数、

　右から２桁目は 2から始まり、110011001100…… と 4個ずつ 1100 を繰り返し、

　 512－1≡3 (mod 4) 、残りが 110 より 1個、

　右から３桁目は 4から始まり、512－3≡5 (mod 8) 、残りが 11110 より 3個、

　右から４桁目は 8から始まり、512－7≡9 (mod 16) 、残りが 111111110 より 7個、

　右から５桁目は 16から始まり、512－15≡17 (mod 32) 、残りが 11111111111111110 より 15個、

　同様にして、右から９桁目まで求め、右から10桁目は 1000000000 に 1個だから、

　0＋1＋3＋7＋15＋31＋63＋127＋255＋1＝503 個になります。


[参考]

　512 のような２の累乗のときは単純に計算できますが、

　一般の自然数ｎについて、1 ～ n を２進法で表すと「1」が「0」より何個多いかを求めるときは、

　[解答3]のように右の桁から順次個数を求めると、

　１番右の桁 ： n mod 2
　右から２桁目 ： n≧2 のとき　2－|{ (n－1) mod 4}－2|
　右から３桁目 ： n≧4 のとき　4－|{ (n－3) mod 8}－4|
　右から４桁目 ： n≧8 のとき　8－|{ (n－7) mod 16}－8|
　右から５桁目 ： n≧16 のとき　16－|{ (n－15) mod 32}－16|
　 　…………

　となって、

　右から(k＋1)桁目 ： n≧2^k のとき　2^k－|{ (n－2^k＋1) mod 2^k+1}－2^k|

　を加えていきます。

　n＝512 のとき、0＋1＋3＋7＋15＋31＋63＋127＋255＋1＝503 、

　n＝1000 のとき、0＋1＋3＋1＋7＋9＋41＋105＋233＋489＝889 になります。

.