n&(n-1) n&(-n)
n&(n-1)作用：将n的二进制表示中的最低位为1的改为0，先看一个简单的例子：
n = 10100(二进制），则(n-1) = 10011 ==》n&(n-1) = 10000
可以看到原本最低位为1的那位变为0。
弄明白了n&(n-1)的作用，那它有哪些应用？
1. 求某一个数的二进制表示中1的个数
while (n >0 ) {
count ++;
n &= (n-1);
}
2. 判断一个数是否是2的方幂
n > 0 && ((n & (n - 1)) == 0 )
3. 计算N!的质因数2的个数。
容易得出N!质因数2的个数 = [N / 2] + [N / 4] + [N / 8] + ....
下面通过一个简单的例子来推导一下过程：N = 10101(二进制表示）
现在我们跟踪最高位的1，不考虑其他位假定为0，
则在
[N / 2] 01000
[N / 4] 00100
[N / 8] 00010
[N / 8] 00001
则所有相加等于01111 = 10000 - 1
由此推及其他位可得：(10101)!的质因数2的个数为10000 - 1 + 00100 - 1 + 00001 - 1 = 10101 - 3(二进制表示中1的个数)
推及一般N!的质因数2的个数为N - （N二进制表示中1的个数）
n&(-n)在树状数组中lowbit出现 用来求 t 中的因子中形如2^k的数为多少 用来取得n最右边的1，可以知道其因子中有几个2
10: 0000 1010
-10: 1111 0110
10&(-10)为 0010 = 2 所以10的因子中为2的有一个，2^k的形式的为2^1
8&(-8) = [1000] = 8 所以8的因子中为2的有3个，2^k的形式为2^3
随机推荐
-
十分钟搞懂什么是CGI
原文:CGI Made Really Easy,在翻译的过程中,我增加了一些我在学习过程中找到的更合适的资料,和自己的一些理解.不能算是严格的翻译文章,应该算是我的看这篇文章的过程的随笔吧. CGI真 ...
-
用Javascript实现回到顶部效果
用Javascript实现回到顶部效果 经常看到网页中有回到顶部的效果,今天也研究一下回到顶部有哪些方法.众所周知,用锚链接是实现回到最简单的方法,但是从用户体验效果来说,并不是最好的.(锚链接回到顶 ...
-
Linq专题之查询操作
前面我们主要讲解的是Linq的查询表达式,Linq不但提供了一些基本的查询表达式,还提供了数十个查询操作.比如筛选操作.聚合操作.投影操作等等.通过这些查询操作可以更方便的对数据源进行处理. Linq ...
-
自学silverlight 5.0
这是一个silverlight游戏:http://keleyi.com/keleyi/phtml/silverlight/ 接了个单子,非要用Silverlight 5来作一个项目,之前从来没接触过这 ...
-
DotNetCore跨平台~性能测试~可以放心使用了
使用dotnetCore发布站点后,它的处理请求能力不逊色IIS等大型服务的能力,号称每秒能处理115万个请求,太牛X了也. 先看看它支持的数据库 以下主流数据库都是为支持的 Microsoft SQ ...
-
Ajax，谷歌提示AutoCompleteExtender控件
提示内容从数据库中读取: ------------------------------------------页面 <asp:ScriptManager ID="ScriptManag ...
-
R语言-妹子被追后的选择分析
前提假设 妹子们一生中可以遇到100个追求者,追求者的优秀程度符合正态分布: 每个妹子都具备判断并比较追求者优秀程度的能力: 接受或拒绝一个追求者后永远无法后悔. 那么,问题来了 当遇到追求者时,如何 ...
-
Java中的Set集合接口实现插入对象不重复的原理
在java的集合中,判断两个对象是否相等的规则是: 1).判断两个对象的hashCode是否相等 . 如果不相等,认为两个对象也不相等,完毕 如果相等,转入2)(这一点只是为了提 ...
-
ASP.NET Core 1.0开发Web API程序
.NET Core版本:1.0.0-rc2Visual Studio版本:Microsoft Visual Studio Community 2015 Update 2开发及运行平台:Windows ...
-
angular 指令——时钟范例
<html> <head> <meta charset='utf-8'> <title>模块化</title> <script typ ...