剑指Offer CountOneInBinary 计算二进制中1的个数

谁借莪１个温暖的怀抱￠ 2022-06-11 22:58 131阅读 0赞

方法1：根据除2取余的方法判断1的个数

原理：一个数除以2相当于右移一位 如果除的过程中有与 表示当前位置有一个1

以10 100 010为例：

第一次除以2 商是1 010 001 余数是0  
第二次除以2 商是 101 000 余数是1

代码实现：

public static int countByDivide(int num) {
            int count = 0;
            while (num != 0) {
                if (num % 2 == 1) {
                    count++;
                }
                num = num / 2;
            }
            return count;
        }

方法二：使用位运算

当一个数进行无符号右移时 会丢弃最后一位 所以只要在右移过程中判断最后一位是否是1 来统计1的个数  
要判断最后一位是否是1 只需要和0000 0001进行与运算即可

代码实现

public static int countByMove(int num) {
            int count = 0;
            while (num != 0) {
                count += num & 0x01;
                num = num >> 1;
            }
            return count;
     }

方法三：优化算法复杂度 让算法复杂度只和1的个数有关

public static int countByOne(int num) {
            int count = 0;
            while (num != 0) {
                num &= (num - 1);
                count++;
            }
            return count;
    }

方法四：一般的与运算

public int NumberOf1(int n) {
        int count = 0;
         for (int t = 31; t >= 0; t--) {
             if ((n & 1) == 1) {
                 count++;
             }
             n = n >> 1;
         }
         return count;
    }

ps:  
如果是负数 只有最好两种方法符合

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer - 二进制中1的个数

public class Solution { public int NumberOf1(int n) {

ゝ一世哀愁。/ 2022年09月25日 01:27/ 0 赞/ 125 阅读

相关剑指Offer CountOneInBinary 计算二进制中1的个数

方法1：根据除2取余的方法判断1的个数原理：一个数除以2相当于右移一位如果除的过程中有与表示当前位置有一个1 以10 100 010为例：第一次除以2 商是1 0

谁借莪１个温暖的怀抱￠/ 2022年06月11日 22:58/ 0 赞/ 132 阅读

相关【剑指offer】二进制中1的个数

题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。 -------------------- 解：使用 1 不断左移，然后与 n 相与，得到的

野性酷女/ 2022年06月09日 13:48/ 0 赞/ 85 阅读

相关剑指Offer-二进制中1的个数

题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。初步解题思路：一开始看到题目直接想到的是将数转化为二进制，将二进制压入堆栈。然后将负数从堆栈

小鱼儿/ 2022年03月01日 12:40/ 0 赞/ 215 阅读

相关剑指offer-二进制中1的个数

题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。实现思想如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么

妖狐艹你老母/ 2022年02月16日 13:13/ 0 赞/ 223 阅读

相关【剑指offer】二进制中1的个数

题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。【思路】把一个数减去1之后，再和这个数本身相与，就可以把这个数最右边的1变成0。举例来说：1

我就是我/ 2022年01月31日 00:37/ 0 赞/ 232 阅读

相关【剑指Offer】二进制中1的个数

题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。【解题思路】因为n有可能是负数，所以不能让n右移，因为最高位1为符号位，不能算作是n本身。所

超、凢脫俗/ 2021年11月17日 13:16/ 0 赞/ 291 阅读

相关【剑指offer】二进制中1的个数

题目描述：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。解题思路：看到这题的第一反应其实是直接调用java的方法将整数变成二进制字符串，即调用In

客官°小女子只卖身不卖艺/ 2021年11月08日 22:54/ 0 赞/ 292 阅读

相关剑指offer-二进制中1的个数

题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。分析：方法1：缺点：如果输入的是负数，整数一直做右移运算，会陷入死循环。 /

红太狼/ 2021年10月24日 02:18/ 0 赞/ 314 阅读

相关剑指offer：二进制中1的个数

试题：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。代码： [原码, 反码, 补码详解二进制][_ _ _] 简单方法，对于正数，每次通过与操

冷不防/ 2021年09月16日 09:46/ 0 赞/ 321 阅读