文档章节

剖析 微博短链接算法 里的 位运算 操作

JacCoffee
 JacCoffee
发布于 2013/10/21 20:22
字数 1194
阅读 192
收藏 2
点赞 0
评论 0

本文主要写给对 java 位运算不是很了解的童鞋 和 我自己

昨天研究了一下微博短链接的算法,但是发现自己对算法里面的位运算不是很明白,所以有了今天这篇文章

微博短链接生成算法:http://blog.csdn.net/wgw335363240/article/details/6568794

在这里我们看到的第一个有关位运算的是

// 这里需要使用 long 型来转换,因为 Inteper .parseInt() 只能处理 31 位 , 首位为符号位 , 如果不用 long ,则会越界
// 将 lHexLong 16进制串 与 0x3fffffff(30位1) 进行 与(&) 操作,即将 lHexLong 超过 30位 的进行忽略处理;
long lHexLong = 0x3FFFFFFF & Long.parseLong (sTempSubString, 16);
这里为什么会用 0x3FFFFFFF &  sTempSubString 进行一个超过30位的忽略处理呢?

首先我们看看0x3FFFFFFF的2进制打印处理的结果是什么?

System.out.println("16f2:"+Long.toBinaryString(0x3fffffff));

结果:111111111111111111111111111111
我们发现它是一个30位 1 组成的一个2 进制串

而接下来我们要先说一下 & 这个在java里的 位操作 
& 与:当两边结果相等,结果为真,否则为0
例子:  
5&3=1 
 5: 0000 0000 0000 0000 0000 0000 0000 0101 
 3: 0000 0000 0000 0000 0000 0000 0000 0011 
     0000 0000 0000 0000 0000 0000 0000 0001 
-5&3=3
-5: 1111 1111 1111 1111 1111 1111 1111 1011 
 3: 0000 0000 0000 0000 0000 0000 0000 0011 
     0000 0000 0000 0000 0000 0000 0000 0011 

你会看到上面的结果运算逻辑
那我们来看看一个从32位md5串里取出来的8位md5串和0x3fffffff 的运算结果是什么?
假设我的md5值为098f6bcd4621d373cade4e832627b4f6,取到第一个8位md5: 098f6bcd
下面运算过程
//获取098f6bcd的二进制值System.out.println("16f2:"+Long.toBinaryString(0x098f6bcd));

结果:1001100011110110101111001101

//上面说过,我们已经获得了0x3fffffff的二进制值
//我们现在直接 & 与操作比较,要注意,比较的位数不够,前面直接补0
//例如 1001100011110110101111001101 补齐30位的结果就是 001001100011110110101111001101
0x3fffffff: 111111111111111111111111111111
0x098f6bcd: 001001100011110110101111001101
result    : 001001100011110110101111001101
result_16+: 098f6bcd

运算代码
System.out.println("16f2:"+Long.toBinaryString(0x3fffffff & 0x098f6bcd));

最后你发现结果居然没变,为什么呢?因为我们的0x098f6bcd的二进制位书并没有超过30位
那我们换一个来看看,假设运算md5串为0xf98f6bcd,我把首位的0换成f
预算过程

//获取f98f6bcd的二进制值 System.out.println("16f2:"+Long.toBinaryString(0xf98f6bcd));

结果:1111111111111111111111111111111111111001100011110110101111001101

&与运算,运算时补齐0x3fffffff的位数
0x3fffffff: 0000000000000000000000000000000000111111111111111111111111111111
0xf98f6bcd: 1111111111111111111111111111111111111001100011110110101111001101
result    : 0000000000000000000000000000000000111001100011110110101111001101
运算代码
System.out.println("16f2:"+Long.toBinaryString(0x3fffffff & 0xf98f6bcd));

通过上面的运算,你会发现,如果是一个数超过了 30 位,把它和0x3fffffff进行&与操作,那就可以截取前面30位的数了

下面我们来看算法里面的第二个位操作

//把得到的值与0x0000003D进行位与运算,取得字符数组chars索引  
int index = 0x0000003D & hexint;
这里是为了将hexint转换成chars字符串数组的索引,以方便从 chars取到字符串然后拼接成短链接
那我们来看看0x0000003D的二进制和十进制数值
System.out.println("16f2:"+Long.toBinaryString(0x0000003D));
二进制结果:111101
System.out.println("16f10:"+Long.parseLong("0000003D",16));
十进制结果:61
看到61这个数值,我们好像明白了点什么?chars的长度不就是62么?那它的索引最大值就是61咯
想多了还不如我们来实践一下,我们刚刚0x098F6BCD通过了0x3FFFFFF的&操作,结果是不变的,还是0x098F6BCD

那我们直接和 0x0000003D 进行 & 操作

//获取0x0000003D和0x098F6BCD的二进制值 
System.out.println("16f2:"+Long.toBinaryString(0x0000003D));
System.out.println("16f2:"+Long.toBinaryString(0x098F6BCD));

结果1: 111101
结果2: 1001100011110110101111001101

&与运算,运算时补齐0x0000003D的位数
0x0000003D: 0000000000000000000000111101
0x098F6BCD: 1001100011110110101111001101
result    : 0000000000000000000000001101
result_10+: 13 
运算代码
System.out.println("16f2:"+Long.toBinaryString(0x3fffffff & 0xf98f6bcd));
从上面的运算结果看到, 0x098F6BCD和0x0000003D进行与操作之后的2进制结果是1101,而10进制结果是13
那我们明显的看到任何一个数和 0x0000003D进行&与操作之后得到的值都不会超过61(要知道0x098F6BCD的10进制值是160394189) ,那我们就明白一开始代码的意思了,和0x0000003D进行&与操作是为了将这个值提取成一个大于61的值

So magical !....

最后补充关于>>操作符的一点点

移位运算符 
包括: 
    “>> 右移”;“<< 左移”;“>>> 无符号右移” 
例子: 

 -5>>3=-1 (将-5右移3位) 
1111 1111 1111 1111 1111 1111 1111 1011 
1111 1111 1111 1111 1111 1111 1111 1111 
其结果与 Math.floor((double)-5/(2*2*2)) 完全相同。
  
-5<<3=-40   (将-5左移3位,移动后补0) 
1111 1111 1111 1111 1111 1111 1111 1011 
1111 1111 1111 1111 1111 1111 1101 1000  
其结果与 -5*2*2*2 完全相同。 


PS:总的来说,对于我这个没接触过java位运算的人来说,&与操作实在是太神奇了,一开始有点理解不能





© 著作权归作者所有

共有 人打赏支持
JacCoffee

JacCoffee

粉丝 18
博文 31
码字总数 11816
作品 0
深圳
程序员
微博短链接的生成算法(Java版本)

微博短链接的生成算法(Java 版本) 最近看到微博的短链接真是很火啊,新浪、腾讯、搜狐等微博网站都加入了短链接的功能。之所以要是使用短链接,主要是因为微博只允许发140 字,如果链接地址太...

java-苦苦甜甜
2012/11/22
0
3
微博短链接解析ShortUrl【PHP代码实现】

一、背景简介 短网址应用已经在各大微博上开始流行了起来。例如QQ微博的url.cn,新浪的sinaurl.cn等。我们在QQ微博上发布网址的时候,微博会自动判别网址,并将其转换,例如:http://url.cn...

幸福的猫猫
2013/03/07
0
1
微博URL短网址生成算法原理及(java版、php版实现实例)

短网址(Short URL),顾名思义就是在形式上比较短的网址。通常用的是asp或者php转向,在Web 2.0的今天,不得不说,这是一个潮流。目前已经有许多类似服务,借助短网址您可以用简短的网址替代...

小老傅
2014/08/20
0
5
短网址(short URL)系统的原理及其实现

背景 提供一个短址服务 你有没有发现,我们的任务中出现长 URL 就会比较麻烦?如果有一个短址生成器就好了。虽然市面上有很多,但是我们可以重复发明一个轮子,利用这个机会尝试一下简单的 ...

琯琯
01/20
0
0
URL短地址压缩算法 微博短地址原理解析 (Java实现)

最近,项目中需要用到短网址(ShortUrl)的算法,于是在网上搜索一番,发现有C#的算法,有.Net的算法,有PHP的算法,就是没有找到Java版的短网址(ShortUrl)的算法,很是郁闷。同时还发现有...

神勇小白鼠
2014/07/29
0
0
微博短网址原理的算法

短网址一直都在微博上应用。例如腾讯微博的短网址url.cn,新浪的sinaurl.cn等。 他们是如何实现呢,我在网上看了一下,大多是下面的一些思路: 例如:http://url.cn/1zJdGX?type=1&from=19&u...

疯狂的流浪
2012/12/10
13K
29
深入分析ConcurrentHashMap

术语定义 术语 英文 解释 哈希算法 hash algorithm 是一种将任意内容的输入转换成相同长度输出的加密方式,其输出被称为哈希值。 哈希表 hash table 根据设定的哈希函数H(key)和处理冲突方法...

markGao
2014/02/28
0
0
微博的那个生成网址,是不是这么回事。

微博的那个生成网址(我这里给他取名字叫做短网址),是不是这么回事。 比如我发条微博,里边有个链接,他把链接按照一定的算法,生成这样子的格式 t.cn/算法结果,访问这个链接,就跳到t.c...

PHP程斌
2012/11/02
213
3
JAVA 生成无重复8位随机码

短8位UUID思想其实借鉴微博短域名的生成方式,但是其重复概率过高,而且每次生成4个,需要随即选取一个。 本算法利用62个可打印字符,通过随机生成32位UUID,由于UUID都为十六进制,所以将U...

不停息的脚步
2015/08/12
0
9
如何利用新媒体平台,优化个人网站!

现阶段你如果和一些新入行的营销人员谈论SEO,他们可能并不了解,虽然SEO有着悠久的历史,但当你与他们谈论新媒体的时候,几乎每个人都会有独到的见解。 随着新媒体的不断崛起与影响力的不断...

蝙蝠侠it
01/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Android 复制和粘贴功能

做了一回搬运工,原文地址:https://blog.csdn.net/kennethyo/article/details/76602765 Android 复制和粘贴功能,需要调用系统服务ClipboardManager来实现。 ClipboardManager mClipboardM...

她叫我小渝
30分钟前
0
0
拦截SQLSERVER的SSL加密通道替换传输过程中的用户名密码实现运维审计(一)

工作准备 •一台SQLSERVER 2005/SQLSERVER 2008服务 •SQLSERVER jdbc驱动程序 •Java开发环境eclipse + jdk1.8 •java反编译工具JD-Core 反编译JDBC分析SQLSERVER客户端与服务器通信原理 SQ...

紅顏為君笑
47分钟前
4
0
jQuery零基础入门——(六)修改DOM结构

《jQuery零基础入门》系列博文是在廖雪峰老师的博文基础上,可能补充了个人的理解和日常遇到的点,用我的理解表述出来,主干出处来自廖雪峰老师的技术分享。 在《零基础入门JavaScript》的时...

JandenMa
今天
0
0
linux mint 1.9 qq 安装

转: https://www.jianshu.com/p/cdc3d03c144d 1. 下载 qq 轻聊版,可在百度搜索后下载 QQ7.9Light.exe 2. 去wine的官网(https://wiki.winehq.org/Ubuntu) 安装 wine . 提醒网页可以切换成中...

Canaan_
今天
0
0
PHP后台运行命令并管理运行程序

php后台运行命令并管理后台运行程序 class ProcessModel{ private $pid; private $command; private $resultToFile = ''; public function __construct($cl=false){......

colin_86
今天
1
0
数据结构与算法4

在此程序中,HighArray类中的find()方法用数据项的值作为参数传递,它的返回值决定是否找到此数据项。 insert()方法向数组下一个空位置放置一个新的数据项。一个名为nElems的字段跟踪记录着...

沉迷于编程的小菜菜
今天
1
1
fiddler安装和基本使用以及代理设置

项目需求 由于开发过程中客户端和服务器数据交互非常频繁,有时候服务端需要知道客户端调用接口传了哪些参数过来,这个时候就需要一个工具可以监听这些接口请求参数,已经接口的响应的数据,这种...

银装素裹
今天
0
0
Python分析《我不是药神》豆瓣评论

读取 Mongo 中的短评数据,进行中文分词 对分词结果取 Top50 生成词云 生成词云效果 看来网上关于 我不是药神 vs 达拉斯 的争论很热啊。关于词频统计就这些,代码中也会完成一些其它的分析任...

猫咪编程
今天
0
0
虚拟机怎么安装vmware tools

https://blog.csdn.net/tjcwt2011/article/details/72638977

AndyZhouX
昨天
1
0
There is no session with id[xxx]

参考网页 https://blog.csdn.net/caimengyuan/article/details/52526765 报错 2018-07-19 23:04:35,330 [http-nio-1008-exec-8] DEBUG [org.apache.shiro.web.servlet.SimpleCookie] - Found......

karma123
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部