[答503] 2進法での1と0の個数
'
[答503] 2進法での1と0の個数
1,10,11,100,101,……,1000000000 と、1 から 512 までの自然数を2進法で書くとき、
書かれる数字「0」の個数と「1」の個数との差は?
[解答1]
まず、2進法で9桁以下の数 1 から 511=111111111(2) で考えます。
511 ,1 と 510 ,2 と 509 ,…… ,255 と 256 のような
和が 511 になる数を対にして(ただし 511 は単独で)、2進法で表せば、
111111111 ,1 と 111111110 ,10 と 111111101 ,…… ,11111111 と 100000000 のように、
各対に「1」が9個ずつあるから、「1」の個数は、9・256=2304 です。
使われる数字全部の個数は、
1桁の数が 1 個、2桁の数が 2 個、3桁の数が 22 個、…… だから、
1+2・2+3・22+……+9・28 で、直接計算しても求められますが、
1+2・2+3・22+……+n・2n-1=1-(n+1)・2n+n・2n+1 より
1+2・2+3・22+……+9・28=1-10・29+9・210=4097 です。
よって、「0」の個数は、4097-2304=1793 となり、
「0」の個数と「1」の個数との差は、2304-1793=511 、
512=1000000000(2) は「0」が「1」より8個多いので、答は、511-8=503 です。
[解答2]
まず、2進法で9桁以下の数 1 から 511=111111111(2) で考えます。
例えば、2進法で4桁の数は、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」が同数であることがいえます。
これは、2進法で表した何桁の数についてもいえることですので、
2進法で9桁以下の数 1 から 511=111111111(2) までで、
最高位の「1」の 511 個だけ「1」の個数が多いことになります。
512=1000000000(2) は「0」が「1」より8個多いので、答は、511-8=503 です。
[解答3]
1,10,11,100,101,……,1000000000 を縦に並べ、各桁で「1」が「0」より何個多いかを求めます。
1番右の桁は 101010……10 だから同数、
右から2桁目は 2から始まり、110011001100…… と 4個ずつ 1100 を繰り返し、
512-1≡3 (mod 4) 、残りが 110 より 1個、
右から3桁目は 4から始まり、512-3≡5 (mod 8) 、残りが 11110 より 3個、
右から4桁目は 8から始まり、512-7≡9 (mod 16) 、残りが 111111110 より 7個、
右から5桁目は 16から始まり、512-15≡17 (mod 32) 、残りが 11111111111111110 より 15個、
同様にして、右から9桁目まで求め、右から10桁目は 1000000000 に 1個だから、
0+1+3+7+15+31+63+127+255+1=503 個になります。
[参考]
512 のような2の累乗のときは単純に計算できますが、
一般の自然数nについて、1 ~ n を2進法で表すと「1」が「0」より何個多いかを求めるときは、
[解答3]のように右の桁から順次個数を求めると、
1番右の桁 : n mod 2
右から2桁目 : n≧2 のとき 2-|{ (n-1) mod 4}-2|
右から3桁目 : n≧4 のとき 4-|{ (n-3) mod 8}-4|
右から4桁目 : n≧8 のとき 8-|{ (n-7) mod 16}-8|
右から5桁目 : n≧16 のとき 16-|{ (n-15) mod 32}-16|
…………
となって、
右から(k+1)桁目 : n≧2k のとき 2k-|{ (n-2k+1) mod 2k+1}-2k|
を加えていきます。
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 になります。
.