文档章节

海明距离 Hamming Distance

叶枫啦啦
 叶枫啦啦
发布于 2017/08/22 09:47
字数 397
阅读 19
收藏 0

问题:

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ xy < 2^31.

Example:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ?   ?
The above arrows point to positions where the corresponding bits are different.

解决:

【注】题目要求的海明距离实际上是指两个二进制数对应位不相同的个数

① 根据异或的性质:相同为0,不同为1。所以先求出异或的结果,然后计算结果中1的个数。

class Solution { // 11ms
    public int hammingDistance(int x, int y) {
        if(x == y) return 0;
        int count = 0;
        int tmp = x ^ y;
        while(tmp != 0){
            tmp = tmp & (tmp - 1);
            count ++;
        }
        return count;
    }
}

② 直接调用java中的方法计算1的个数。

class Solution { // 15ms
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

③ 在网上看到一种递归的写法,递归终止的条件是当两个数异或为0时,表明此时两个数完全相同。我们返回0,否则我们返回异或和对2取余加上对x>>1和y>>1调用递归的结果。异或和对2取余相当于检查最低位是否相同而对x>>1和y>>1调用递归相当于将x和y分别向右移动一位,这样每一位都可以比较到,也能得到正确结果。

class Solution { // 10ms
    public int hammingDistance(int x, int y) {
        if((x ^ y) == 0) return 0;
        return (x ^ y) % 2 + hammingDistance(x >> 1,y >> 1);
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
simhash算法实现--查找文件相似度

一、Simhash简介 SimHash是用来网页去重最常用的hash方法,速度很快。Google采用这种算法来解决万亿级别的网页去重任务。 SimHash算法的主要思想是降维。将高维的特征向量映射成一个低维的特...

hiqj
2014/08/18
4.9K
0
总的海明距离 Total Hamming Distance

问题: The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance bet......

叶枫啦啦
2018/01/06
10
0
我也出一道面试题,看看面试官会不

天天面试我,我出一道,看看哪个面试官会。而且是我遇到的问题。 用户表 (用户id,simhash值),文章表(文章di,simhash值),用户文章表(用户id,文章id,Hamming ) Hamming :海明距离...

韭零后张子游
2013/08/28
434
3
常见的距离算法和相似度(相关系数)计算方法

摘要: 1.常见的距离算法 1.1欧几里得距离(Euclidean Distance)以及欧式距离的标准化(Standardized Euclidean distance) 1.2马哈拉诺比斯距离(Mahalanobis Distance) 1.3曼哈顿距离(M...

Airship
03/15
50
0
Hamming Distance (汉明距离)

原文链接:https://blog.csdn.net/chouisbo/article/details/54906909 Hamming Distance (汉明距离) 1. 汉明距离的定义 在信息理论中,Hamming Distance 表示两个等长字符串在对应位置上不同...

ersaijun
08/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

服务器性能监控之New Relic 入门教程

New Relic 是一个很强大的服务器性能监控工具,New Relic目前专注于SaaS和App性能管理业务,它支持支持agent和API传送数据,能够对部署在本地或在云中的web应用程序进行监控、故障修复、诊断...

xiaolyuh
27分钟前
4
0
SpringBoot 集成ElasticSearch

一、ElasticSearch介绍 ElasticSearch 是一个开源的搜索引擎,建立在一个全文搜索引擎库 Apache Lucene™ 基础之上。 Lucene 可以说是当下最先进、高性能、全功能的搜索引擎库——无论是开源...

zw965
51分钟前
6
0
【JVM学习】2.Java虚拟机运行时数据区

来源: 公众号: 猿人谷 这里我们先说句题外话,相信大家在面试中经常被问到介绍Java内存模型,我在面试别人时也会经常问这个问题。但是,往往都会令我比较尴尬,我还话音未落,面试者就会“...

物种起源-达尔文
59分钟前
4
0
dart datetime

var date = DateTime.now().toUtc(); //格式化输出 String timestamp = "${date.year.toString()}-${date.month.toString().padLeft(2, '0')}-${date.day.toString().padLeft(2, ......

zdglf
今天
21
0
如何在Linux中复制文档

在办公室里复印文档过去需要专门的员工与机器。如今,复制是电脑用户无需多加思考的任务。在电脑里复制数据是如此微不足道的事,以致于你还没有意识到复制就发生了,例如当拖动文档到外部硬盘...

老孟的Linux私房菜
今天
50
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部