写点什么

【LeetCode】位 1 的个数 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 03 月 22 日

题目


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


示例 1:


输入:00000000000000000000000000001011


输出:3


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


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/problems/number-of-1-bits


代码


public class DayCode {    public static void main(String[] args) {        int n = 1;        int ans = new DayCode().hammingWeight(n);        System.out.println("ans is " + ans);                int result  = Integer.bitCount(n);        System.out.println("result is " + result);    }
/** * 题目链接: https://leetcode-cn.com/problems/number-of-1-bits/ * 时间复杂度 O(n) * 空间复杂度 O(1) * @param n * @return */ public int hammingWeight(int n) { int count = 0; while (n != 0) { n &= (n - 1); count++; } return count; }}
复制代码


Java 8 中 bitCount 的实现。


    /**     * Returns the number of one-bits in the two's complement binary     * representation of the specified {@code int} value.  This function is     * sometimes referred to as the <i>population count</i>.     *     * @param i the value whose bits are to be counted     * @return the number of one-bits in the two's complement binary     *     representation of the specified {@code int} value.     * @since 1.5     */    public static int bitCount(int i) {        // HD, Figure 5-2        i = i - ((i >>> 1) & 0x55555555);        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);        i = (i + (i >>> 4)) & 0x0f0f0f0f;        i = i + (i >>> 8);        i = i + (i >>> 16);        return i & 0x3f;    }
复制代码


总结

  • 今天这个题目是之前做过的一个题目,复习了一下,可以快速 AC。

  • 上文还贴了 Java 中 bitCount 的实现。可见,我们在生产环境中,工程实践的代码还是比较复杂的。

  • 这个题目是二进制的应用,二进制可以高效的进行计算。 n = n & (n - 1) 把最低位的 1 变成 0。

  • 坚持每日一题,加油!


发布于: 2021 年 03 月 22 日阅读数: 9
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】位1的个数Java题解