【剑指Offer面试题】 九度OJ1513:二进制中1的个数

题目链接地址:
http://ac.jobdu.com/problem.php?pid=1513

题目1513:二进制中1的个数

时间限制:1 秒内存限制:128 兆特殊判题:否提交:4217解决:1519
题目描述:
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
输入:
输入可能包含多个测试样例。
对于每个输入文件,第一行输入一个整数T,代表测试样例的数量。对于每个测试样例输入为一个整数。
。n保证是int范围内的一个整数。
输出:
对应每个测试案例,
输出一个整数,代表输入的那个数中1的个数。
样例输入:
3
4
5
-1
样例输出:
1
2
32

思路分析:

  • 可能死循环的解法

输入一个数n,然后将该数和1进行与操作,如果结果不为0,则表明整数的二进制最低位是1,再对n执行右移一位操作,每进行完一次右移操作就查看二进制数字的最低位是否为1。
弊端:
当输入负数事,右移一位,最高位是要补1的,这样的话进入死循环。

  • 常规解法

输入一个数n,然后将该数和1进行与操作,如果结果不为0,则表明整数的最低位是1,而后将1左移一位,再次与该数进行与操作,如果结果不为0,说明整数的次低位为1,依次类推,当1左移到变为0时,统计结束。
因为int是32位的,所以一共移位32次。

int NumberOf1(int n)
{
    int count = 0;
    int flag=1;
    while(flag)
    {
        if(n&flag)
            count++;
        flag=flag<<1;
    }
    return count;
}
  • 优化解法

    把一个整数 (无论正负或0)减去1,再和原整数做与运算,会把该整数最右边的一个1变为0。

    例如:101101000减1后变为101100111,二者进行与操作后,得到101100000,最后边的1变为了0,而前面的位都不变。    
    

    我们依次将整数的最右边的1变为0,当该整数的所有位为1的位均变为0之后,统计结束,同时可以计算该整数二进制中1的个数。
    时间复杂度O(log(n))
    空间复杂度O(1)

代码:

/********************************* 
----------------------------------- 
【剑指Offer面试题】 九度OJ1513:二进制中1的个数
----------------------------------- 
Author:牧之丶  Date:2015年
Email:bzhou84@163.com 
**********************************/ 
#include<stdio.h>
#include<stdlib.h> 
#include<string>
#include<stack>
#include <iostream>
using namespace std;

int NumberOf1(int n)
{
 int count = 0;
 while(n)
 { 
 count++;
 n = (n-1) & n;
 }
 return count;
}

int main()
{
 int n;
 while(scanf("%d",&n) != EOF)
 { 
 int *a=(int *)malloc(n*sizeof(int));
 int i;
 for(i=0;i<n;i++)
 { 
 scanf("%d",&a[i]);
 printf("%d\n",NumberOf1(a[i]));
 }
 }

 return 0;
}
/**************************************************************
 Problem: 1513
 Language: C++
 Result: Accepted
 Time:80 ms
 Memory:1912 kb
****************************************************************/

总结

n & (n- 1)则正好去掉x最低位的‘1’

    原文作者:牧之丶
    原文地址: https://blog.csdn.net/zhoubin1992/article/details/47106501
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞