问题描述
461. Hamming Distance
即求两个正整数的二进制对应位数不同的个数
原理说明
从问题描述来看,最直观的解决方法就是十进制数先转成二进制,再比对相同位数是否相同,不同则计数器累加,最终计数器的值即是Hamming Distance
。
优化方案:先
^
运算,对运算结果的位数进行遍历,1
则计数器累计
基于这个思想,需要用到的有 异或运算
和 位运算
。
异或^ 和 异或非
异或运算法则:相同为零,不同为一。
异或非运算法则:相同为一,不同为零。
即:
输入A: 1 0 1 0
输入B: 1 1 0 0
异或运算结果: 0 1 1 0
异或非(同或)运算结果:1 0 0 1
左移<< 和 右移>>
左移
- 右边空出的位用0填补
- 高位左移溢出则舍弃该高位
右移
- 左边空出的位用0或者1填补。正数用0填补,负数用1填补
- 低位右移溢出则舍弃该位
代码实现
func hammingDistance(x int, y int) int {
counter := 0
tmp := x ^ y
t := 1
for i := uint(0); i < 32 && t > 0; i++ {
t = tmp >> i
counter += (tmp >> i) & 1
}
return counter
}
参考
有疑问加站长微信联系(非本文作者)