n&(n-1)的妙用
2024-08-30 07:09:35
今天无聊拿起《编程之美》看了下，发现原来n&(n-1)还有很多妙用。
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-1)的原理及作用，在碰到相关问题时也会比较容易解决。
最新文章
- Building OpenCASCADE on Debian
- Android 学习第15课，Android 开发的单元测试、及输出错误信息
- 由项目中一个hash2int函数引发的思考
- Java关键字——final
- 创建文本，innerHTML与createTextNode的使用
- Combination Sum 和Combination Sum II
- CString.Format的详细用法(转)
- Android开发-API指南-<instrumentation >
- CentOS 安装 mono
- Entity Framework 6.1 学习系列1--概况、安装
- 线性表之顺序存储结构（C语言动态数组实现）
- Web 前端 —— javaScript
- OS error set
- bzoj 1196: [HNOI2006]公路修建问题 二分+并查集
- 图片，音频资源预加载和文档dom加载
- MDX 用Ancestors得到Hierarchy中指定Level的值（附带SCOPE用法之一）
- POJ 2251 三维BFS(基础题）
- C++求出旋转数组的最小数字
- android项目 之 记事本（11） ----- 加入数据库
- 项目总结19：layui实现表格渲染、表格搜索、数据获取