美文网首页
剑指 offer 笔记 11 | 二进制中1的个数

剑指 offer 笔记 11 | 二进制中1的个数

作者: ProudLin | 来源:发表于2019-06-12 10:51 被阅读0次

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

    思路分析
    计算出,一个整数二进制形式下 1 的个数有多少,例如 2 ==》0010 那么 2 的二进制 1 个数为 1 个。

    这道题花了一个早上去理解,涉及位运算知识点,废话少说,直接上代码,虽然是大神的代码。

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

    其中 n = n & (n - 1); 最为巧妙了, & 是(与运算符)位运算,针对二进制,只要有一个为 0,就为 0

    举个例子, 2 ===》 0010; 1 ===》 0001

    那么 2&1 ,得出来为 0 ;既是 0010 & 0001 结果为 0000 (二进制结果);

    引用大佬的话 :一个二进制数 1100,从右边数起第三位是处于最右边的一个 1。减去 1 后,第三位变成 0,它后面的两位 0 变成了 1,而前面的 1 保持不变。因此得到的结果是 1011。

    我们发现减 1 的结果是把最右边的一个 1 开始的所有位都取反了。这个时候如果我们再把原来的整数和减去 1 之后的结果做与运算,从原来整数最右边一个1那一位开始所有位都会变成 0。

    如 1100&1011=1000 .也就是说,把一个整数减去 1,再和原整数做与运算,会把该整数最右边一个 1 变成 0。那么一个整数的二进制有多少个 1,就可以进行多少次这样的操作。

    参考文献:https://www.nowcoder.com/profile/562667/codeBookDetail?submissionId=1520125

    相关文章

      网友评论

          本文标题:剑指 offer 笔记 11 | 二进制中1的个数

          本文链接:https://www.haomeiwen.com/subject/vwjkfctx.html