Kotlin Leetcode - 191. Number of 1 Bits
class Solution {
fun hammingWeight(n:Int):Int {
}
}
解題思路
這題和 461. Hamming Distance 一樣
考驗的是對 binary operation 的熟悉程度
一個比較直覺的想法
是先宣告變數 count 為零
將 n 和 1 做 and 運算
如果結果為 1,代表最右邊的位元為一
那麼 count 就加一,並且 n 右移一位
否則就 n 直接右移一位
除此之外
我們可以發現數字 n 和數字 n-1
剛好會在結尾的所有 0 變成 1
並將最接近尾端的 1 變成 0
所以 n and (n-1)
就會將最接近尾端的 1 變成 0
我們只要計算進行幾次操作之後 n 變成了 0
就可以知道 n 原本包含了幾個 1 bits
Kotlin 參考解答
點擊展開解答
class Solution {
fun hammingWeight(n: Int): Int {
var number = n
var count = 0
for (i in 0..32) {
if (number and 1 == 1) {
count++
}
number = number shr 1
}
return count
}
}
n and n-1 的做法
class Solution {
fun hammingWeight(n:Int):Int {
var count = 0
var input = n
while(input != 0) {
input = input and (input - 1)
count++
}
return count
}
}
當然也可以使用 Kotlin 內建的 countOneBits()
class Solution {
fun hammingWeight(n: Int): Int {
return n.countOneBits()
}
}
或者用 Integer.bitCount()
class Solution {
fun hammingWeight(n: Int): Int {
return Integer.bitCount(n)
}
}
回到 leetcode 列表