Swift 汉明距离 - LeetCode

LeetCode

题目： 汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 2³¹.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

方案一：最先印入脑海的方法----10进制转2进制然后一一对比，那10进制怎么转2进制？

参考百度百科：10进制转2进制

代码一：

func hammingDistance(_ x: Int, _ y: Int) -> Int {
    
    //初始化两个空数组来装各自对应的二进制
    var dicX = [Int]()
    var dicY = [Int]()
   
    //将x,y改成可变的
    var x = x
    var y = y
    
    if (x == 0) {
        dicX.append(0)
    }
    if (y == 0) {
        dicY.append(0)
    }
    
   //对2求余将10进制转换为2进制
    while x != 0 {
        dicX.append(x%2)
        x /= 2
    }
    
    while y != 0 {
        dicY.append(y%2)
        y /= 2
    }

    print(dicX)
    print(dicY)
    
    //区分长短是为了方便后面对比
    let short = dicX.count <= dicY.count ? dicX:dicY
    let long  = dicX.count <= dicY.count ? dicY:dicX
    
    var count = 0
    var index = 0
    //一一对比
    for i in 0..<short.count {
        if short[i] != long[i] {
            count += 1
        }
        index = i
    }
    // 统计长的数组中 长出来那部分的1的个数
    if long.count > short.count {
        for i in index+1..<long.count {
            if long[i] == 1 {
                count += 1
            }
        }
    }
   
    return count
}

执行用时：36ms

这个方法是蠢了点、、、但是我也不怕写出来、、、这毕竟也算是一个正常的思路

方案二：位运算：按位异或+右移运算

参考百度百科：位运算

x 和 y 异或得到的就是一个包含所求汉明距离的一个数，此时用右移运算去做统计

代码二：

func hammingDistance(_ x: Int, _ y: Int) -> Int {
    
    var num : Int = x ^ y
    var sum : Int = 0
    
    while (num > 0) {
        sum += num & 1 == 1 ? 1 : 0
        num = num >> 1
    }
    return sum
}

执行用时：12ms

用Swift开始学习算法中，在LeetCode中开始做初级算法这一章节，将做的题目在此做个笔记，希望有更好方法同学们cue我哦。