剑指offer系列之十:二进制中1的个数

简介:
+关注继续查看

题目描述:

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。比如输入9,9的二进制表示是1001,1的个数是2,所以输出2。

这有一个重要结论:一个数与该数减一的结果进行与运算,会把该数右边(低位)第一个1变为0,而该位左边保持不变(高位)。可以举一个简单的例子进行证明:比如1100(对应十进制是12),减去1之后的结果是1011(也就是十进制的11),两个数进行与运算之后,我们发现最后的结果是1000(对应十进制的8,当然这个8与后面没有关系,可以略过)。这样我们每进行一次的与运算就消去一个1,这样消到最后肯定是0了,所以我们可以在代码中以这个为循环的终止条件。

基于以上分析,可以写出如下的代码(已被牛客AC):

package com.rhwayfun.offer;

public class NumberOf1 {

    public int numberOf1(int n) {
        int sum = 0;
        while(n != 0){
            sum++;
            n = n & (n - 1);
        }
        return sum;
    }

    public static void main(String[] args) {
        int count = new NumberOf1().numberOf1(9);
        System.out.println(count);
    }
}
目录
相关文章
|
3月前
剑指Offer - 面试题15:二进制中1的个数
剑指Offer - 面试题15:二进制中1的个数
29 0
|
3月前
|
机器学习/深度学习 C++
剑指offer 14. 二进制中1的个数
剑指offer 14. 二进制中1的个数
18 0
|
3月前
剑指Offer_编程题_数组中只出现一次的数字
剑指Offer_编程题_数组中只出现一次的数字
24 0
|
3月前
|
算法 C语言
编程之美求二进制数中1的个数
编程之美求二进制数中1的个数
35 0
|
8月前
|
算法
求两个数对应二进制位不同的个数(深度剖析+补充例题)
求两个数对应二进制位不同的个数(深度剖析+补充例题)
74 0
求两个数对应二进制位不同的个数(深度剖析+补充例题)
|
11月前
|
算法
数据结构与算法系列一之整数、数组及字符串
系统的学习一下数据结构与算法,主要是通过学习专项突破版的剑指Offer每一部分的典型题目,将每一部分相关的基础内容尽量掌握一下。由于没有太多时间将看过的基础内容都总结整理起来,因此先将题目根据书中的讲解和自己的理解整理一下,后续有时间再系统整理一下每一部分的基础知识,每一行代码都经过本人测试通过。
数据结构与算法系列一之整数、数组及字符串
K-进制数(简洁 图解)
根据题意,要知道 N 位K 进制并且 不能有连续两个0出现 还有首位不能为0 的限制条件。 本着由简到难的思想 : 假设是让你求 1位 K 进制的满足条件的数,那么满足条件的数则有 1,2,3.....K-1 一共K-1个数对吧, 我们记作 res_1=K-1,那么不满足条件的数 只有 0 ,一共1个数 ,我们记作res_0=1。 假设是让你求 2位 K 进制的满足条件的数,那么先考虑首位(也就是第2位),可以填的数为除去0的其他数,
253 1
K-进制数(简洁 图解)
|
存储 算法
LeetCode 7. 整数反转 | 算法-从菜鸟开始
本文是《算法-从菜鸟开始》系列文章的第8篇,欢迎收藏、留言、点赞。 话不多说,让我们继续我们的算法之旅。
|
算法
数据结构与算法题目集(中文) - 7-21 求前缀表达式的值(25 分)
数据结构与算法题目集(中文) - 7-21 求前缀表达式的值(25 分)
163 0
相关产品
机器翻译
推荐文章
更多