抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

40 | 面试题:统计位1的个数

191. 位1的个数

解法一:取余

对数取余,余数为1,则 count ++,然后每次取余后左移一位

时间复杂度:常数级 O(1)

代码一:取余会超时,改用位运算 X & -X 判断低位是否为1

class Solution {
// you need treat n as an unsigned value
fun hammingWeight(n: Int): Int {
var x = n
var count = 0
for (i in 0 until 32) {
if (x and -x == 1) {
count++
}
x = x.shr(1)
}
return count
}
}

代码二:改用位运算 X & 1 判断低位是否为1 也可

class Solution {
// you need treat n as an unsigned value
fun hammingWeight(n: Int): Int {
var x = n
var count = 0
for (i in 0 until 32) {
if (x and 1 == 1) {
count++
}
x = x.shr(1)
}
return count
}
}

解法二:利用位运算 每次消除一个1

上节课讲到:X = X & (X-1) => 清零最低位的1

于是可以写一个循环,每次消除一个1,直到等于0(变成全0)为止。

时间复杂度:O(二进制中1的个数) 常数级 O(1)

class Solution {
// you need treat n as an unsigned value
fun hammingWeight(n: Int): Int {
var x = n
var count = 0
while (x != 0) {
count++
x = x and (x - 1)
}
return count
}
}

最坏情况下(全1数字)两者解法效率一致,为:O(二进制位数)


0条评论

发表评论