【动漫】作业帮面试题:求一个数的二进制中1的个数

二进制中1的个数

http://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8

面试现场


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

  • 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的正数,然后就不用担心负数陷入死循环。

全部评论

相关推荐

Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务