面试现场

小夕：我先来说一下我的解法：

• 1、先将数字转换成二进制字符串
• 2、用String.split()函数存入一个数组中
• 3、遍历数组跟1比较，同时计数
• 4、输出计数值

public class Solution { 
    public int NumberOf1(int n) { 
        String s=Integer.toBinaryString(n); 
        String[] split=s.split(""); 
        int a=0; 
        for(int i = 0; i < split.length; i++) { 
            if (split[i].equals("1")) 
           { a++; }
        } 
        return a; 
    } 
}

一个例子

助教：对于一个数12，求它的二进制中有几个1。count代表它里面有几个1。 然后我将n和n-1的按位相与：

n是12，n-1是11，两者按位相与，n&n-1 = 8，n&n-1 它的二进制是1000。

到这里我们发现减1的结果是把最右边的一个1开始的所有位都取反了。也就是下图所示，全都取反了！

这个时候如果我们再把原来的整数和减去1之后的结果做与运算（也就是n&n-1），从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000。也就是如下图所示： 也就是说，把一个整数减去1，再和原整数做与运算（也就是n&n-1），会把该整数最右边一个1变成0.也就是如下图所示，n=12变成了n&n-1也就是变成8,12是1100,8是1000，12的二进制中最右边的1变成了0也就是成为了8。 那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。好的接下来，让n=n&n-1,也就是n=8了，那么n-1是7，来继续求n&n-1。 n继续和n-1按位相与得到的结果是0： 最后由于结果为0，所以结束，一共进行了两次这样的操作，所以12二进制中有两个1。

动画演示

动画.GIF

五种语言实现

Java

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

Python

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0;
        if n < 0:
            n = n & 0xffffffff
        while (n != 0):
            count += 1
            n = (n - 1) & n
        return count;

C++

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

PHP

<?php

function NumberOf1($n)
{
     $count = 0;
     if($n < 0){ // 处理负数
       $n = $n&0x7FFFFFFF;
       ++$count;
     }
     while($n != 0){
      $count++;
      $n = $n & ($n-1);
     }
     return $count;
}

JS

function NumberOf1(n)
{
    // write code here
    var count = 0;
    while (n != 0) {
        count++;
        n = (n - 1) & n;
    }
    return count;
}

【助教解释一下】n = n & 0xffffffff，在Python中，数的大小是可以无限扩大的，不会像Java或c++中，数超过32位会溢出，而是继续扩张，所以对于一个负数而言，进行了这个操作，实际上是提取了负数的后32位（在计算机中以补码形式存在），前面的任意位呢，则变成了0，比如说 -1，一开始是 111.....(n个1)...11111111，进行与运算之后，得到，00....(n个0)....111111111（32个1），变成了含32个1的正数，然后就不用担心负数陷入死循环。