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).
For example, the 32-bit integer '11' has binary representation
, so the function should return 3.
- 00000000000000000000000000001011
解法:
1. 普通解法:利用 1 的移位相与
View Code
- 1 public class Solution {
- 2 // you need to treat n as an unsigned value
- 3 public int hammingWeight(int n) {
- 4 int flag = 1;
- 5 int count = 0;
- 6
- while (flag != 0) {
- 7
- if ((n & flag) != 0) {
- 8 count++;
- 9
- }
- 10 flag = flag << 1;
- 11
- }
- 12
- return count;
- 13
- }
- 14
- }
2. 能给面试官打来惊喜的解法,p80 利用减 1 的性质:减 1 其实是把最右边的一个 1 之后的位取反,再与原数字相与就只剩下了前面的位。
View Code
- 1 public class Solution {
- 2 // you need to treat n as an unsigned value
- 3 public int hammingWeight(int n) {
- 4 int count = 0;
- 5
- while (n != 0) {
- 6 count++;
- 7 n = n & (n - 1);
- 8
- }
- 9
- return count;
- 10
- }
- 11
- }
来源: