Recca Chao 的 gitHub page

推廣網站開發,包含 Laravel 和 Kotlin 後端撰寫、自動化測試、讀書心得等。Taiwan Kotlin User Group 管理員。

View on GitHub

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 列表