面接問題10:バイナリのうち1の個数


タイトル説明:Online Judge
整数を入力し、その数のバイナリ表現の1つの数を出力します.ここで負数は補数で表される.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各入力ファイルについて、最初の行には、テストサンプルの数を表す整数Tが入力されます.テストサンプルごとに整数として入力します.nはint範囲内の整数であることを保証する.
出力:
各テストケースに対応して、入力した数の1つを表す整数を出力します.
サンプル入力:
3
4
5
-1

サンプル出力:
1
2
32

問題解決の考え方:
整数バイナリ表現の一番右が1かどうかを判断し、入力した整数を整数全体が0になるまで右にシフトします.
JAvaコード:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;


public class Problem_10 {

	public static void main(String[] args) throws IOException {
		BufferedReader bu = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer str = new StreamTokenizer(bu);		
//		while(str.nextToken() != StreamTokenizer.TT_EOL	){
		str.nextToken();
			int n =(int) str.nval;
			int[] input = new int[n];
			for(int i = 0; i < n; i ++){
				str.nextToken();
				input[i] = (int) str.nval;
			}//end for
			for(int i = 0; i < n; i++){
				int count = 0;
				int temp = input[i];
				while(temp != 0){							
					count++;				
					temp = temp&(temp -1);
				}//end while
				System.out.println(count);
			}
//		}//end while
	}
}

C++コード:
#include <iostream>
#include <stdio.h>
 
using namespace std;
 
int main() 
{
    int T;
    cin >> T;
    int num;
    while(T--)
    {
        scanf("%d", &num);
         
        int count = 0;
        while(num != 0)
        {
                        ++count;
            num &= (num - 1);
        }
        printf("%d
", count); } return 0; }

C言語:
#include <stdio.h>
int getNumber(int test);
int main(){
    int n,i,test;
    while(scanf("%d",&n)!=EOF && n > 0){
        for(i=0 ; i<n ; i++){
            scanf("%d",&test);
            printf("%d
",getNumber(test)); } } return 0; } int getNumber(int test){ int sum = 0,i; for(i=0;i<32;i++){ sum+= (test&1); test = test>>1; } return sum; }

テスト例:
正数(境界値1、0 x 7 FFFFFFFを含む)
負数(境界値0 x 8000000、0 xFFFFFFFFを含む)
0.
体得:問題ではシフト時の記号問題に注意し,負数のシフトには特に注意する必要がある.この問題は主にバイナリのビット演算を考察する.