查看原文
其他

剑指offer:二进制中1的个数

帅地 苦逼的码农 2019-03-29

前言

本来是打算次条每天更新面试题和算法刷题的,加上头条一共要三篇文章,实在更不来,而且两篇都看的人也不多,所以我就算法刷题和面试题论着更新,更新的时候多更新几道。

题目描述

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

点击左下角的阅读原文即可跳到原题,可以提交代码

解答

方法1

让 n 和 000….001,相与判断第一位是不是 1 ,然后和 00….010相与判断第二位是不是 1,以此类推。代码如下:

1    public int NumberOf1(int n) {
2        int count = 0;
3        int k = 1;
4        while (k != 0) {
5            if ((n & k) != 0) {
6                count++;
7            }
8            k = k << 1;
9        }
10        return count;
11    }

方法2

这个方法就比较牛逼了,可以说是最优解,直接看代码,如果不懂的可以自己找几个数字演示下,就能够理解了。

1    public int NumberOf12(int n) {
2        int count = 0;
3        int k = 1;
4        while (n != 0) {
5            count++;
6            n = (n - 1) & n;
7        }
8        return count;
9    }

其实有很多题是可以利用位的异或来解决的,大家可以思考下平时遇到哪些题是用这种方法解决的,我后面会给出几道题,这些题都可以用异或位运算巧妙解决。发的另一道题也用到了位运算。

其实我是想跟大家说,做题的时候,有时候想想是否可以用位运算来解决。

往期

剑指offer:重建二叉树

剑指offer:二维数组中的查找


                关注我 ,每天进步一点点                  

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存