通过leetcode学习位运算及其Go实现

酒肉穿肠过 · · 3004 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

问题描述

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
}

参考

  1. 百度百科 异或非
  2. 百度百科 位运算

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:酒肉穿肠过

查看原文:通过leetcode学习位运算及其Go实现

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

3004 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传