程序员社区

剑指Offer系列(java版,详细解析)15.二进制中1的个数

题目描述

剑指 Offer 15. 二进制中1的个数

难度简单90

请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

测试用例

  • 正数(包括边界值1、0x7FFFFFFF)
  • 负数(包括边界值0x80000000、0xFFFFFFFF)
  • 0

题目考点

  • 考察应聘者对二进制及位运算的理解。

解题思路

常规解法

首先把n和1做与运算,判断n的最低位是不是为1,接着把1左移一位得到2,再和n做运算,就能判断n的次低位是不是1…这样反复左移,每次都能判断n的其中一位是不是1。

常规解法

我们基于这样一个事实:把一个整数减去1之后再后原来的整数做位与运算,得到的结果相当于把整数的二进制表示中最右边的1变成0。例子如下:

n       : 10110100
n-1     : 10110011
n&(n-1) : 10110000

那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。

image-20210311182855266

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

自带API解法

Integer.bitCount(n);

补充

位运算只有5中运算:与、或、异或、左移和右移。

与、或、异或运算就是简单的真值表。

左移运算符 m<<n 表示把 m 左移 n 位。在左移 n 位的时候,最左边的 n 位将被丢弃,同时在最右边补上 n 个0.

右移运算符 m>>n 表示把 m 右移 n位。在右移 n 位的时候,最右边的 n 位将被丢弃,但右移时处理最左边位情形有两种情况,如果数字是无符号数字,则用0填补最左边的 n 位;如果数字是一个有符号数值,则用数字的符号位填补最左边的 n 位。也就是说,如果数字原先是一个正数,则右移之后再最左边填补 n 个0;如果数字原先是负数,则右移之后在最左边补 n 个1。

负数的二进制表示(计算机用补码表示负数)

  1. 变成原码:将绝对值转换成二进制数,然后在最高位补1
  2. 变成反码:对原码除符号位外各位取反
  3. 变成补码:在反码最后一位加1

问题: 把整数右移一位和把整数除以2在数学上是等价的吗?

不是,除法的效率比一位运算效率低得多,在实际编程中应尽可能得用一位运算符代替乘除法。

值得注意的地方:

把一个整数减去1之后再后原来的整数做位与运算,得到的结果相当于把整数的二进制表示中最右边的1变成0。 很多二进制问题都可以用这种思路解决。

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 剑指Offer系列(java版,详细解析)15.二进制中1的个数

一个分享Java & Python知识的社区