面试题15:二进制中1的个数

题目

请实现一个函数，输入一个整数，输出该树二进制表示中1的个数。例如:把9表示成二进制是1001，有2位是1.因此如果输入9，则该函数输出2.

解题思路

1. 先判断整数二进制表示的最右边一位是不是1，接着把输入的整数右移一位，再次判断知道整个整数变成0为止。让一个整数与1做与运算结果为1则整数最右边一位为1，否则为0.
2. (1)方法的弊端是当整数为负数时容易陷入死循环。可以不右移输入的数字n。首先把n和1做与运算，判断n的最低位是不是1，接着把1左移得到2，再和n做与运算.....这样反复左移，每次都可判断n的其中一位是不是1
3. (2)方法的弊端是需要移动32位，还有一种更快的方式整数中有几位为1就移动几次。首先把整数减去1，再和原整数做与运算，会把该整数最右边的1变成0.那么一个整数的二进制表示中有多少个1，就可以进行多少次这种操作

代码

• 方法一

int numOf1_1(int n)
        {
            int count = 0;
            while(n)
            {
                if(n & 1)
                {
                    count++;
                    n = n >> 1;
                }
            }
            return count;
        }

• 方法二
  该方法flag会运行32次(循环的次数等于整数二进制的位数)，因为int型最大为32位数。直到flag为空时才跳出循环，依然很浪费时间。

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

• 方法三

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

延伸

• 用一条语句判断一个整数是不是2的整数次方
  如果一个整数是2的整数次方，那么它的二进制表示中有且只有一位为1，而其他所有为都是0.所以可以把该整数减去1之后和自己相与，这个整数中唯一的1就会变成0
  -代码

int numOf2(int n)
        {
            return (n-1)&n;
            
        }

• 输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制表示为1010,13的二进制表示为1101，需要改变1010中的三位才能得到1101.通过两步解决这个问题:1) 求这两个数的异或，2) 统计异或结果中1的位数。
• 代码

int numMtoN(int m,int n)
        {
            int sum = m^n;
            int count = 0;
            while(sum)
            {
                if(sum)
                {
                    count++;
                    sum = (sum-1)∑
                }
            }
            return count;
        }

完整代码见Github