剑指office--------二进制中1的个数

题目描述

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

思路1：常规解法，位运算

 1 class Solution {
 2 public:
 3      int  NumberOf1(int n) {
 4          int ans=0;
 5          int index=1;
 6          while (index!=0){
 7              if (n&index)    ans++;
 8              index<<=1;
 9          }
10          return ans;
11      }
12 };

思路2：利用二进制特点

 1 class Solution {
 2 public:
 3      int  NumberOf1(int n) {
 4          int count=0;
 5          while (n){
 6              count++;
 7              n=(n-1)&n;
 8          }
 9          return count;
10      }
11 };

n-1是将二进制n中的最右的1变成0的操作，例如 101000 减去1 的 100111

（n-1）&n 则是消除最右边的1的操作 101000 & 100111　　=　　100000

即每操作一次就可以消除一个1。

用这个方法也可解下列问题

问题1：判定一个整数是否是2的整数次方

　　　　如果是2的整数次方，那么其的二进制只有一个1，即：if（（n-1）&n==0）　　printf("YES ");

问题2：两个整数n与m，问最少要改变多少个数字（对其二进制操作），可以使n与m相等。

　　　　先对n与m取异或。在统计有多少个1即可。