位1的个数
题意
编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 1
的个数.
示例 1:
1 | 输入:00000000000000000000000000001011 |
示例 2:
1 | 输入:00000000000000000000000010000000 |
示例 3:
1 | 输入:11111111111111111111111111111101 |
解法一
这里用到了位运算, 如数字 5, 二进制位为 101
, 那么使用 &
运算, 和 1
进行与运算, 如:
1 | 101 |
因为 1 只有最后一位为 1, 其他为都是 0, 所以他与任何数进行 &
运算后, 都只会保留这个数的最后一位, 如果运算结果还是 1, 说明这个树的最后一位是 1, 反之为 0.
那就很好解决了, 将 num & 1 后判断为 1, 则计数增加 1, 然后将右移一位 num >>= 1, 以此类推, 直到移位 32 次.
1 | public class Solution { |
时间复杂度 O(1), 空间复杂度 O(1).
解法二
这个解法有些取巧, 在二进制表示中,数字 n
中最低位的 1
总是对应 n - 1
中的 0
. 因此, 将 n
和 n - 1
与运算总是能把 n
中最低位的 1
变成 0
, 并保持其他位不变.
如对于数字 10, 和 10 - 1 进行 &
运算:
1 | 1010 |
接着对于二进制值 1000
, 与 999
进行 &
运算:
1 | 1000 |
由于每次都把最低位的 1
变为 0
了, 直到为 0
, 那么这种个编程变了几次就说明有多少个 1
.
1 | public class Solution { |
时间复杂度 O(1), 空间复杂度 O(1). 但此算法效率相对比算法一效率高.