导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-191.Number of 1 Bits

题目

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

翻译

编写函数,以一个无符号整数为参数,返回它包含的’1’的位数(也被称为汉明重量http://en.wikipedia.org/wiki/Hamming_weight) 。
例如,32位整数’11’的二进制形式为00000000000000000000000000001011,所以函数应当返回3。

投机取巧的办法,利用JDK的Integer.toBinaryString(int)函数……

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
String binaryString = Integer.toBinaryString(n);
int hammingWeight = 0;
for (char c : binaryString.toCharArray())
if (c == '1')
hammingWeight++;
return hammingWeight;
}
}

但本题其实考察的是对位操作的理解:
1、n & (n - 1)每次可以去掉最末位的1(多少个1操作多少次):

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int hammingWeight = 0;
while (n != 0) {
n &= n - 1;
hammingWeight++;
}
return hammingWeight;
}
}

2、Java中无符号移位操作符>>>(多少位操作多少次)。

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int hammingWeight = 0;
while (n != 0) {
if ((n & 1) == 1)
hammingWeight++;
n >>>= 1;
}
return hammingWeight;
}
}

参考:
http://www.tuicool.com/articles/YBbY3m
http://blog.csdn.net/guang09080908/article/details/44457603
http://www.07net01.com/2015/08/892764.html