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

伪斜杠青年

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

41 | 面试题:2的幂次方问题&比特位计数问题

231. 2的幂

判断是不是2的 x 次方。

方法一:不断除2看是否能被整除

方法二:用内置函数

方法三:上节是位运算X & (X-1) 统计1的个数,这里是位为1的个数只能是1个。

所以利用X & (X-1)消除二进制中的1,则就是0了,仅需操作一次。

class Solution {
    fun isPowerOfTwo(n: Int): Boolean {
        val x=n.toLong()
        if (x == 0L) return false
        return x and (x - 1) == 0L
    }
}

338. 比特位计数

方法一:按上个题目的思路,依次对每个数字进行统计

方法二:利用位运算递推

建立一个数组,利用 x & (x – 1) 每次消除一个1的特性,可以得出这么一个递推式:bits[i] += bits[i & (i – 1) ] +1

class Solution {
fun countBits(num: Int): IntArray {
val bits = IntArray(num + 1) { 0 }
for (i in 1 .. num){
bits[i]+=bits[i and (i-1)] +1
}
return bits
}
}

0条评论

发表评论