LeetCode 191 Number of 1 Bits
LeetCode 191 Number of 1 Bits
一份执着?
发布于 2019-12-29 20:15:00
发布于 2019-12-29 20:15:00
位1的个数
题意
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 1 的个数.
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011?中，共有三位为 '1'。示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000?中，共有一位为 '1'。示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。解法一
这里用到了位运算, 如数字 5, 二进制位为 101, 那么使用 & 运算, 和 1 进行与运算, 如:
101
& 001
-----
001因为 1 只有最后一位为 1, 其他为都是 0, 所以他与任何数进行 & 运算后, 都只会保留这个数的最后一位, 如果运算结果还是 1, 说明这个树的最后一位是 1, 反之为 0.
那就很好解决了, 将 num & 1 后判断为 1, 则计数增加 1, 然后将右移一位 num >>= 1, 以此类推, 直到移位 32 次.
public class Solution {
public int hammingWeight(int n) {
int bits = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
if ((n & mask) != 0) {
bits++;
}
n >>= 1;
}
return bits;
}
}时间复杂度 O(1), 空间复杂度 O(1).
解法二
这个解法有些取巧, 在二进制表示中，数字 n 中最低位的 1 总是对应 n - 1 中的 0. 因此, 将 n 和 n - 1 与运算总是能把 n 中最低位的 1 变成 0, 并保持其他位不变.
如对于数字 10, 和 10 - 1 进行 & 运算:
1010
& 1001
------
1000接着对于二进制值 1000, 与 999 进行 & 运算:
1000
& 999
------
0000由于每次都把最低位的 1 变为 0 了, 直到为 0, 那么这种个编程变了几次就说明有多少个 1.
public class Solution {
public int hammingWeight(int n) {
int sum = 0;
while (n != 0) {
sum++;
n &= (n - 1);
}
return sum;
}
}时间复杂度 O(1), 空间复杂度 O(1). 但此算法效率相对比算法一效率高.
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-07-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录