2022/05/13

Leetcode Note: Go - Number of 1 Bits

Number of 1 Bits - LeetCode
https://leetcode.com/problems/number-of-1-bits/

  • Go 言語で取り組んだメモ

所感

  • 各数値を走査して 1 かチェックすれば良さそう

回答

Python/JS/Go/C++ O( lg n ) by bit-manipulation - LeetCode Discuss
https://leetcode.com/problems/number-of-1-bits/discuss/468836/PythonJSGoC%2B%2B-O(-lg-n-)-by-bit-manipulation

func hammingWeight(num uint32) int {
    output := 0
    for i := 0; i < 32; i++ {
        if num&uint32(1) == 1 {
            output++
        }
        num >>= 1
    }
    return output
}
  • uint32 データの各桁を確認するのどうするんだ・・・？と思ってググったら bit 全探索というのがあるらしい
  • num&uint32(1) == 1
    • & がビット演算子で論理積を判定し、真なら 1 を返す
  • num >>= 1
    • >> が左シフトなので…
    • num >>= 1 は num を 1 bit 左シフトするということ
    • これをループしているので bit 全探索が実現できているということ
    • num[i] みたいなアクセスじゃないので、慣れてないと処理内容が想像しにくい

See Also