191. Number of 1 Bits二进制中1的个数

本文主要是介绍191. Number of 1 Bits二进制中1的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

解答

错误的，可能引起死循环解法

　　先判断整数二进制表示中最右边一位是不是1。接着把输入的整数右移一位，此时原来处于右边起的第二位被移到最右边，再判断它是不是1。这样每次移动一位，直到整个整数变成0为止。
　　那么如何判断一个整数的最右边是不是1。只要把整数和1做按位与运算，看结果是否为0就可以判断。1除了最右边的一位以外，所有的位都是0。如果一个整数与1做按位与运算的结果是1，表示该整数最右边一位是1，否则是0。

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

除法的效率要比位移运算低得多，在实际编程中应尽可能用位移运算代替除法。

对于上面的方法，如果输入是一个负数，例如0x80000000时，将负数 0x80000000右移一位的时候，并不是简单把最高位的1移到第二位变成0x40000000，而是 0xC0000000。这是因为移位前是个负数，以为后仍然要是负数，所以移位后最高位会置为1。如果一直做右移运算，最终这个数字会变成0xFFFFFFFF,是算法陷入死循环。

常规解法

　　为了避免死循环，我们可以不右移输入的数字n。首先把n和1做按位与运算，判断n的最低位是不是1。接着把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1……这样反复左移，每次都能判断n的其中一位是不是1。
　　

class Solution {
public:int  NumberOf1(int n) {int flag = 1;int count = 0;while(flag){if(n&flag)++count;flag  = flag<<1;}return count;}
};

优化的解法

　　首先分析一个数减去１的情况。如果一个整数不等于０，那么该整数的二进制表示中至少有一位是１。
　　先假设这个数的最右边一位是１，那么减去１时，最右边一位变成０，而其他所有位都保持不变。也就是说最右边一位相当于做了取反操作，由１变成了０。
　　下面假设最后一位不是１的情况。如果该整数的二进制表示中最右边的１位于第ｍ位，那么减去１时，第ｍ位由１变成０，而第ｍ位之后的所有０都变成１，ｍ位之前的所有位都保持不变。
　　在上面两种情况中，我们发现一个整数减去１，都会把其二进制表示中最右边的１变成０。如果最右边的１的右边还有０的话，则都会变成１，而它左边的所有位都保持不变。
　　最后，我们把一个整数和它减去1的结果做位于运算，相当于把它最右边的1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的运算。
　　

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

这篇关于191. Number of 1 Bits二进制中1的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---