【LeetCode-191】Number of 1 bits
【LeetCode-191】Number of 1 bits
周三不加班
发布于 2019-09-03 10:55:27
发布于 2019-09-03 10:55:27
1题目
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
Example 1:
Input: 11Output: 3Explanation: Integer 11 has binary representation 00000000000000000000000000001011 Example 2:
Input: 128Output: 1Explanation: Integer 128 has binary representation 00000000000000000000000010000002翻译
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为
3解法
并行任务部分主要包含Parallel Time这一行以及其下面的详细任务信息。
思路一
这道题有一个非常取巧的解法，在java语言中 Integer类中提供了一个方法叫做 Integer.bitCount
它的主要作用就是用于统计参数n转成2进制后有多少个1，也就是说，只需要一行代码就可以搞定
public static int hammingWeight(int n) {
return Integer.bitCount(n);
}
当然，如果有一天面试官问你这个问题的时候你这样解答错是没有错，但肯定不是他想要的答案，于是乎，你应该搬出这个方法的源码和他聊一聊，具体代码也不是很难，主要是一些进制转换和位运算的知识，jdk源代码如下：
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;
}
除此之外，你还应该提供给他一个自己的实现方案
思路二
首先我们可以确定，如果一个整数不为0，那么这个整数至少有一位会是1，如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话),其余所有位将不会受到影响
public static int hammingWeight2(int n) {
int count = 0;
while (n != 0) {
count++;
n = (n - 1) & n;
}
return count;
}
思路三
用flag来与n的每位做位于运算，来判断1的个数
public int hammingWeight3(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((flag & n) != 0) {
count++;
}
flag = flag << 1;
}
return count;
}4总结
总体而言，今天这道题是比较简单的，只要判断好边界条件和了解一些进制转换及位运算的知识点就能解决，除此之外，还应该掌握java中各个基本数据类型可以表示的数据范围大小
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-10-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读