本稿はCodeIQで2016年7月12日～2018年4月25日に出題された 【実力判定：Bランク】ビットカウント という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。

ビットカウント

【問題】

2つの整数値N, Mが与えられます。 0からNまでの各整数（10進数）について、2進表記したときに1の数がM個になるものを数えてください。 たとえば、9を2進表記すると1001ですので、1の数は2ということになります。

【入力】

標準入力から、半角スペースで区切られた2つの整数値N（0≦N≦100000）、M（0≦M≦17）が与えられます。

【出力】

0からNまでの整数の中で、2進表記したときに1の数がM個あるものの個数を出力してください。

【入出力サンプル】

Input

10 2

Output

5

※11, 101, 110, 1001, 1010の5つ

【解答方法】

[bitcount.zip]をダウンロードし、展開してください。中には以下のフォルダが含まれています。

• input: テストデータです
• output: 解答データです

テストデータを入力として、解答データと一致する出力になるようなプログラムを書いてください。

（解説は後日）