n&(n-1)为什么可以用来检测1024?

最近写了好几篇跟bit操作相关的东西.

我们在介绍Integer.bitCount介绍了他的出处, 是HD第五章.

在介绍HashMap.tableSizeFor时候,介绍了他的出处, 是HD第三章.

既然都这么有缘分了, 不打开看看,实在说不过去.打开看了几页,确实颇多神仙操作. 这本让Java标准库开发者大肆抄代码的书, 果然有独到之处.

这篇简单介绍下,第二章第一页的几个神奇公式.

1准备工作

先复习下都熟悉的, 基本的位操作符.

&(and) 双方都为1时候为1

1&1=1
0&0=1&0 =0 &1 = 0

|(or) 双方都为0时候为0

0|0=0
1|0=0|1 =1 &1 = 1

^(xor) 双方不同为1,相同为0

1^0=0^1=1
1^1=0^0=0

~(not) 这个是一元操作符, 就是翻转

~1 = 0
~0 = 1

当两个数字进行位运算时候, 就是他们二进制形式的每一个bit都按对应着按照上面的规律进行运算.

接下来开始HD第二章.

2HD 2 Basics

这篇写写HD第二章中学到的内容. 这章叫:Basics, 几乎全是位运算,看着让人拍案叫绝.全都是我们会的操作, 但是效果却是如此神奇.

2-1 操作最右的bit

先来确定一件事, 当一个数字用二进制表示时候.

非0的数字,至少包含1个bit是1
一个数字的二进制的每一位,要么是0要么是1

这两句看起来是废话,对吧. 别着急,后面有用.

n&(n-1)

这个式子的神奇之处是, 他可以把数字最右侧的1给消灭掉.

假设现在有一个数字n,写成二进制形式有k位,大概是这样:. 我们可以确定一件事, 要么是0,要么是1.

如果是1,

那么, n-1应该可以表示为:

n&(n-1) 就相当于

最右侧这个1,就消失了.

如果是0

在n!=0的前提, 他左面一定至少有一位是1. 假设这一位是. 那么到之间应该都是0.这时候

数字n应该写作
n-1应该写作

n&(n-1)就变成了

最右侧这个1,也消失了. 证明完毕.后面的算法基本也都是相似的证明路径,就不试着写证明了.

我们知道, 除0以外的数字,都含有至少1个1.那么,什么数字,刚刚好只有1个1?

这种2的整数次方,就是二进制表示出来只有1个1的数字.

套用上面的公式,我们知道一定是0,因为他只有一个1,还被消灭掉了.这是一种检查数字是否是的办法.

n|(n+1)

这个式子可以让最右侧的0bit变成1. 这个我就不试着证明了, 和前面的手法是相似的.

n&(n+1)

这个式子可以让尾部连续的1变成0. 比如 0b10111经过这个式子操作,就会变成0b10000.

n|(n-1)

这个式子, 可以让一个数字尾部连续的0都变成1. 比如10100经过这个操作,会变成10100|10011=10111

~n&(n+1)

这个式子, 可以让一个数字最右边的0变成1, 其他的位都变成0. 比如 101,经过这个操作,010&110=010

~n|(n-1)

这个式子, 可以数字最右边的1变成0,其他的位都变成1. 比如 101, 经过这个操作, 010|100= 110

3总结

到这里, 差不多等于摘录了第二章第一页的半页内容吧. 这部分全都是如何操作最右侧的某个或者某些bit的神仙操作. 其实还有很多有趣的内容,我没摘. 估计背下来也不太可能,反正记不住. 记得以后如果有位运算的需求时候, 先来HD翻翻,就很好了.

这篇就到这里, 我水一下. 最近阅读量不够, 输出不了什么东西了.

原文始发于微信公众号（K字的研究）：n&(n-1)为什么可以用来检测1024?

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/24684.html