FC2ブログ

Welcome to my blog

[答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 になります。

.

スポンサーサイト



Comments 20

There are no comments yet.
ニリンソウ  
No title

紅葉の時期に真っ赤なサルビア?
夏の花だと思ったらそちらではまだ咲いてるんですね

ナイス

ひとりしずか  
No title

地区の老人クラブの花壇で市花のサルビアとマリーゴールド
今も咲いています
太陽の光を浴びて~夏の名残を感じます~
ナイス☆

こっこちゃん  
No title

おはようございます

サルビアは いつまでも元気で好きな花です

花咲を取ってやると 又花が元気に咲いてくれるエコなので
好きなんですね (笑) ナイス

Yasuko  
No title

☆。◕‿◕。)ノ♡☆,。・:*:・゚おはよ~☆彡
真っ赤なサルビアこの時期に嬉しいです゜+.ヽ(❀ฺ◕ฺ‿ฺ◕ฺ)ノ.+゜
元気をいただけそうです♪
゚・:,。★\(^ω^ )♪ありがと♪( ^ω^)ノ★,。・:・゚ございます♪

ナイス!

アキチャン  
No title

おはようございます。
真っ赤なお花で、朝から、元気になりました!(笑)ナイス!

uch*n*an  
No title

これは,2進法を理解していれば規則性を調べれば分かる問題で,解法はいろいろとあるでしょう。
私の解法は二つ。(解法1)が[解答2],(解法2)が[解答3]でした。
[参考]は式がなかなかすごいですが,要は,n を2進法で表して数えればいいですね。

たけちゃん  
No title

面白い問題でした.私は[解答2]でした.

[参考]の記事の中で,
「右から(k+1)桁目 : n≧2^k のとき 2^k-|{ (n-2^(k+1)+1) mod 2^k}-2^k|」
とあるのは,
「右から(k+1)桁目 : n≧2^k のとき 2^k-|{ (n-2^k+1) mod 2^(k+1)}-2^k|」
が正しいと思います.

スモークマン  
No title

グーテンアーベント ^^
わたしも解法2でしたけど...
1000=1024-16-8 から計算できないのか知らん...^^;
まだやってないけど...Orz...

ヤドカリ  
No title

古い人さん、早速のコメントとナイス!を有難う御座います。
長期にわたって赤い花が咲き、暖かさを感じます。
秋の気温が下がって来る時期に嬉しい花です。

ヤドカリ  
No title

樹ちゃん、早速のコメントとナイス!を有難う御座います。
私も、この花を見るたび、♪いつもいつも想ってた~と、頭の中で歌が始まります。
赤い色が熱い気持ちを表しているようですね。

ヤドカリ  
No title

ニリンソウさん、早速のコメントとナイス!を有難う御座います。
この花は、夏から秋にかけての花で、秋の方が色鮮やかに見えます。
写真は少し前に撮ったものですが、まだ咲いています。

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!を有難う御座います。
マリーゴールドもサルビアも花期が長い花ですね。
夏の暑い時期はあまり有難さを感じませんが、寒くなって咲いていると暖かさを感じます。

ヤドカリ  
No title

こっこちゃんさん、早速のコメントとナイス!を有難う御座います。
エコな花であることは、私は見るだけの人なので分からなかったのですが、
いつまでも赤い鮮やかな色を見せてくれるのは嬉しいことです。

ヤドカリ  
No title

yasukoさん、早速のコメントとナイス!を有難う御座います。
真っ赤な花は暖かく感じますね。
特に赤が目立つ写真を使いました。

ヤドカリ  
No title

アキチャンさん、早速のコメントとナイス!を有難う御座います。
情熱を感じるような赤い花ですね。
元気を与えられたらサルビアも嬉しいことでしょう。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
参考は、512のような2の累乗にならない場合の数え方として記しました。
この問題はどのみち2進法をイメージして数えるだけです。

ヤドカリ  
No title

たけちゃんさん、コメントとミスの指摘を有難う御座います。
早速訂正しました。
「2^k」をタグを使って本文に書くのに「2<SUP>k</SUP>」としています。
それで、コピペをし、最後に「+1」をつけたのですが、位置を間違えました。
かなり長い式になるからです。
これからも、このようなミスがあると思いますので、また教えて頂きたいと思います。

ヤドカリ  
No title

スモークマンさん、コメントを有難う御座います。
1000=1024-16-8 からも計算できるでしょう。
ただ、逆に除いて行く時は細心の注意が必要と思います。

さっちゃんこ  
No title

こんばんは
陽の光をいっぱい受けたサルビア
燃えるような真っ赤な色が大好きです ナイス☆

ヤドカリ  
No title

さっちゃんこさん、コメントとナイス!を有難う御座います。
陽の光を浴びた真っ赤なサルビア、秋になっても夏を彷彿とさせます。
静しい時には元気が出ます。