LeetCode,求两个数字二进制位不同的有多少个

2021-08-18 15:43:32 浏览数 (1)

力扣题目:

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y,计算并返回它们之间的汉明距离。

「汉明距离」是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以d(x,y)表示两个字x,y之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离。--来自百度百科

  • 来源:力扣(LeetCode)
  • 链接:https://leetcode-cn.com/problems/hamming-distance

在解题前,我们先讲几个知识点,解题需要使用到。

golang的异或符

位运算就是将数值转换为二进制,按位进行操作。go语言的四个相关操作符如下:

  • 或|:都是0才是0,否则都是1
  • 与&:都是1才是1,否则都是0
  • ^异或
    • 二元:a ^ b : 对应位的值相同则为0,不同则为1
    • 一元:^a : 按位取反 1变0,0变1

p

q

P & q

p | q

p ^ q

0

0

0

0

0

0

1

0

1

1

1

1

1

1

0

1

0

0

1

1

移位运算:

  • number >> 4 将数字转为二进制,整体向右移动4位,再将结果转为十进制;
  • number << 4 数字转为二进制,整体向左移动4位,再将结果转为十进制

解题

1. 内置位计数功能

两个整数之间的汉明距离是对应位置上数字不同的位数。我们使用异或运算,当且仅当输入位不同时输出为 1。

代码语言:javascript复制
func hammingDistance(x int, y int) int {
    return bits.OnesCount(uint(x ^ y))
}

2. 异或计数

求x和y的二进制表示中不同位的个数,可以利用异或'^'的性质,相异为1,相同为0,也就是求x^y的二进制表示中,1的个数

代码语言:javascript复制
func hammingDistance(x int, y int) int {
    x = x^y
    count := 0
    for x > 0 {
        //去掉x的二进制表示中,最低位的1,依次循环,直到将所有的1被删除,x为0则退出循环
       x &= (x-1)
       count  = 1 
    }
    return count
}

运行示例

代码语言:javascript复制
package main

import "fmt"

func main() {
    x := 11
    fmt.Printf("x: %bn", x)
    y := 20
    fmt.Printf("y: %bn", y)
    x = x^y
    fmt.Printf("x^y: %bn", x)
    count := 0
    for x > 0 {
       //去掉x的二进制表示中,最低位的1,依次循环,直到将所有的1被删除,x为0则退出循环
       x &= (x-1)
       fmt.Printf("循环:%bn", x)
       count  = 1 
    }

    fmt.Println("count:", count)
}

运行结果:

代码语言:javascript复制
x: 01011
y: 10100
x^y: 11111
循环:11110
循环:11100
循环:11000
循环:10000
循环:0
count: 5

0 人点赞