暇つぶしのプログラミング

今日は暇だったので　CodeIQ で解いた問題について書いてみます。

どういう問題かというと…

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個あるものの個数を出力してください。

例としては、入力に　10 2　と与えたとしましょう。

その場合の出力は５になります　なぜなら 0　から　10　までの数を全て2進数に変換してその中で１が二つ含まれるのは　「11, 101, 110, 1001, 1010」の5つだからです。

とまぁこんな感じなんですがこの問題言語に指定はありません。最初はCで書こうかなって思ったんですが2ビットのカウント方法を1から書かなければならなさそうなのでjavaの方がいいかな～と思いjavaにしました。

というわけでソースを張ります

import java.io.*;

import java.util.Scanner;

public class codeIQtest {

public static void main(String args[]){

Scanner scan = new Scanner(System.in);


int N = Integer.valueOf(scan.next());

int M = Integer.valueOf(scan.next());


if(0>N || 100000<N){System.out.println("error"); return;}

if(M<0 || 17<M){System.out.println("error"); return;}


bitCount(N,M);


}


static void bitCount(int N,int M){

int counter;

int Tcounter=0;

for(int i=0;i<=N;i++){

  counter = Integer.bitCount(i);

  if(counter == M) Tcounter = Tcounter+1;

  }

System.out.println(Tcounter);

 }

}

なんでMarkdown上手く表示されないんだろう…　コードが見づらい…

これで正解が貰えました。 で、上記のソースの最後らへんに counter = Intger.bitCount(i); という部分があるんですがこのbitCountメソッドがなんとint型の数字を渡すとその数字を2進数に変換し１の数をカウントしてくれるという便利なものです。　これのおかげで後は入力条件の設定とメソッドの定義、出力処理ぐらいだけで済みました。超便利ですね。

ちょっと調べてみた結果、RubyとかCだとbitCountっぽいやつは自作しなきゃなさそう？ Cでは一応有名な美しいアルゴリズムとして存在してるっぽいですね　一応載せておきます

int numofbits3(int bits) {

int num = 0;

for( ; bits != 0 ; bits &= bits - 1 ){ 

num++ ;

 }

return num;

}

綺麗ですね…　もう少し冗長なものになるのかと思ってましたがここまで簡潔に書けるとは…

では今日はここら辺で

また気が向いたらこういう暇つぶしについても書いてみようかなと思います。