面试题10:
题目描述:
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
输入:
输入可能包含多个测试样例。
对于每个输入文件,第一行输入一个整数T,代表测试样例的数量。对于每个测试样例输入为一个整数。
。n保证是int范围内的一个整数。
输出:
对应每个测试案例,
输出一个整数,代表输入的那个数中1的个数。
样例输入:
3
4
5
-1
样例输出:
1
2
32

第一种思路,直接转换成2进制数,统计1的个数。时间复杂度最差O(32);直接将数据n右移。(负数可能出错,需要先处理负数的符号位)
第二种思路,和第一种类似,时间复杂度仍然为O(32),使用无符号数从1开始左移,然后与原数n进行与运算。统计个数;
/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月09日 星期一 11:27:18
File Name     :1513.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

int NumberOf1( int n ){
	int count = 0;
	unsigned flag = 1;
	while( flag ){
		if( n& flag )
			count++;
		flag <<= 1;
	}
	return count;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	int n,temp;
	while( scanf( "%d", &n ) != EOF ){
		while( n-- ){
			scanf( "%d", &temp );
			int res = NumberOf1( temp );
			printf( "%d\n", res );
		}
	}	
    return 0;
}

 

第三种思路,时间复杂度根据原数n中的1的个数来定。每次n与n-1进行与运算,直到变为0.统计需要执行多少次,就是1的个数。因为每次n-1后,从右向左到其第一位为1的数都将变为原数的相反数。那么这样就相当于找到了一个数字为1的数。再进行与运算。则该位到最后一位数(自左向右),由于与运算,都将变为0.而其之前的数都不会改变。原数与原数的与值还是不会变。
eg. sum = 1, n:1011 n-1:1010 n&(n-1):1010; 
 sum = 2, n:1010 n-1:1001 n&(n-1):1000;
 sum = 3, n:1000 n-1:0111 n&(n-1):0000;
/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月09日 星期一 11:35:47
File Name     :1513a.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

int NumberOf1( int n ){
	int count = 0;
	while( n ){
		count++;
		n = ( n - 1 ) & n;
	}
	return count;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
   	int n, temp;
   	while( scanf( "%d", &n ) != EOF ){
		while( n-- ){
			scanf( "%d", &temp );
			int pos = NumberOf1( temp );
			printf( "%d\n", pos );
		}
	}	
    return 0;
}