友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
191. Number of 1 Bits
Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).
Example 1:
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string Example 2:
Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.Example 3:
Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.Note:
-
Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
-
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3 above the input represents the signed integer
-3.
Follow up:
If this function is called many times, how would you optimize it?
思路分析
减法解法让人开眼界。但是有一个疑问：它的效率就一定高吗？
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Runtime: 2 ms, faster than 7.49% of Java online submissions for Number of 1 Bits.
*
* Memory Usage: 38 MB, less than 5.41% of Java online submissions for Number of 1 Bits.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-25 23:12
*/
public int hammingWeight(int n) {
int result = 0;
while (n != 0) {
if ((n & 1) == 1) {
++result;
}
n = n >>> 1;
}
return result;
}
/**
* Runtime: 2 ms, faster than 7.49% of Java online submissions for Number of 1 Bits.
*
* Memory Usage: 38.2 MB, less than 5.41% of Java online submissions for Number of 1 Bits.
*
* Copy from: https://leetcode.com/problems/number-of-1-bits/solution/[Number of 1 Bits solution - LeetCode]
*/
public int hammingWeightSubtraction(int n) {
int result = 0;
while (n != 0) {
result++;
n &= (n - 1);
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-14 15:34:01
*/
public int hammingWeight(int n) {
// int result = 0;
// while (0 < n) {
// // 这里可以简化成一行： result += n & 1
// // 结果是 0，相加不影响；是 1，则正好计数。
// if ((n & 1) == 1) {
// result++;
// }
// n = n >> 1;
// }
// return result;
// ------------------
// 牛逼闪闪的减法解法
int result = 0;
while (n != 0) {
result++;
n &= n - 1;
}
return result;
}