LeetCode0461.汉明距离 Go语言AC笔记

时间复杂度：O(log n)

解题思路

其实就是统计a和b异或后1的个数。

如果不借助于内置函数，可以用Brian Kernighan 算法，令异或后的结果每次都与自身减1做且运算（s&（s-1）），可以删除自身最右侧的1，通过删除次数统计1的个数。

借助于内置函数就是用OnesCount函数统计1的个数。

AC代码

Brian Kernighan 算法

func hammingDistance(x int, y int) (res int) {
    for s:=x^y;s>0;s&=s-1{
        res++//每次循环都会删去s中最右侧的1，故可以统计出1的个数
    }
    return res
}

借助OnesCount函数

func hammingDistance(x, y int) int {
    return bits.OnesCount(uint(x ^ y))
}

感悟

学习到可以通过Brian Kernighan 算法统计二进制数中1的个数