191-位1的个数-简单但是很巧妙

作者: 华雨欣 | 来源:发表于2020-07-09 15:22 被阅读0次

题目

思路

这道题看上去是真的很简单,就是类似于进行十进制与二进制转换的笔算方法。不过要注意负数的问题,题目的下边给了这样一点解释:


示例三传入的n = -3,而编译器记录时记录的是11111111111111111111111111111101,以补码形式存储,所以进行有符号移位运算会造成一定的错误,那么选择>>>无符号右移即可。我想到的思路是获取最后一位是否为1,加到结果中,然后将n无符号右移直至最终n = 0结束循环即可。

代码

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            res += (n & 1);
            n = n >>> 1;
        }
        return res;
    }
}

分析

无符号右移保证最后一定会移位变为0从而结束循环,这是一个比较细节的点。另外,由于java中int类型为32位,所以只要想办法遍历每一位,很容易就可以得到最终的结果,类似的方法,通过不同的位运算得到结果可以看这里,每一种方法都是很巧妙的。最后,官方给出了一种优化的位运算:方法 2:位操作的小技巧。代码如下:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            n &= (n - 1);
            res++;
        }
        return res;
    }
}

表面上与遍历每一位的思路一样,但是通过n &= (n - 1)使得每次循环都会使的最靠后的一个1变为0,所以循环的次数只与1的个数有关,最优复杂度得到了优化。
这里的n &= (n - 1)操作可以通过两个例子来理解:
3和28和7

  1. 首先考虑3和2这一对,即11 和 10,他们进行与运算后可以得到结果10,将最后一位置为0
  2. 然后来看第二组8和7,即1000和0111,这两个数进行与运算得到0000刚好把最高位的1变成0
    当然单纯通过例子不一定很好理解原理,其实可以这样想:nn - 1要大一,也就是 n = (n - 1) + 1,而n - 1的末尾要么是1,要么是0,是0的情况加一变为1,那么在进行与操作,末尾一个是1一个是0,就会得到最后一位变为0的结果;而末尾是1的情况,加一肯定要进行进位,进位后又会重复这一步骤,即倒数第二位加一,直到第一种情况为止,也就是得到类似于8(1000)的结果,由于除了最高位,每一位都是1进位上来的,结果一定是0,最高位的1由于原本为0,与运算过后也会变为0,这样就将最靠后一个1变成了0。

总结

位运算真的是个很神奇又很巧妙的东西,官解给出的优化方法也是真的巧妙,学到了很多。
如果文章有写的不对的地方还请指正,感恩相遇~

相关文章

  • 191-位1的个数-简单但是很巧妙

    题目 思路 这道题看上去是真的很简单,就是类似于进行十进制与二进制转换的笔算方法。不过要注意负数的问题,题目的下边...

  • 位1的个数

    编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。 示例 :...

  • 【1】位1的个数

    题目 编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被...

  • 1 - Easy - 位1的个数

    编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。 示例 :...

  • 44位1的个数

    编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。 示例 1...

  • 【LeetCode】位1的个数

    题目描述: 编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)...

  • Leetcode 位1的个数

    题目描述 leecode第191题:编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数...

  • Python实现二进制中1的个数,没看懂答案。。

    二进制中1的个数 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 毫无头绪,查阅答案,很巧妙,但...

  • 数组相关

    1、JS两个数组比较,删除重复值巧妙方法

  • 【位运算】^、|、&、>>、>>

    最近看代码的时候看到了,所以简单记录一下这些基本的位运算,高手应该很多用的,因为速度确实快,实现起来也很巧妙。 1...

网友评论

    本文标题:191-位1的个数-简单但是很巧妙

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