n&(n-1)的妙用

系统管理员 2023-11-08 06:57 237阅读 0赞

基本原理：

n&(n-1)作用：将n的二进制表示中的最低位为1的改为0，先看一个简单的例子：

n = 10100(二进制），则(n-1) = 10011 ==》n&(n-1) = 10000

可以看到原本最低位为1的那位变为0。

如下应用：

1. 求某一个数的二进制表示中1的个数

代码块：

while(n > 0)  
\{  
count++;  
n&=(n-1);  
\}

完整代码：

\#include <iostream>  
\#include <cstdio>  
using namespace std;  
int main()  
\{  
int n, count = 0;  
cin>>n;  
while(n > 0)  
\{  
count++;  
n&=(n-1);  
\}  
cout<<count<<endl;  
return 0;  
\}

2. 判断一个数是否是2的次幂

代码块：

n > 0 && ((n & (n - 1)) == 0 )

完整代码：

<span style="font-size:24px;">\#include <iostream>  
\#include <cstdio>  
using namespace std;  
int main()  
\{  
int n, count = 0;  
cin>>n;  
if((n>0) && (!(n&(n-1))) == true)  
cout<<"这个数是2的幂"<<endl;  
else  
cout<<"这个数不是2的幂"<<endl;  
return 0;  
\}</span>

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的个数）

发表评论取消回复

表情：

评论列表（有 0 条评论，237人围观）

还没有评论，来说两句吧...

相关阅读

相关 n&(n-1)的妙用

基本原理： n&(n-1)作用：将n的二进制表示中的最低位为1的改为0，先看一个简单的例子： n = 10100(二进制），则(n-1) = 10011 ==》n&(n-1

系统管理员/ 2023年11月08日 06:57/ 0 赞/ 238 阅读

相关 sql where 1=1 的详细解释【妙用】

原文来自：https://blog.csdn.net/zc474235918/article/details/50544484 看一下这两个句子： select

青旅半醒/ 2023年06月17日 09:54/ 0 赞/ 1 阅读

相关宏的妙用

[http://www.vckbase.com/document/viewdoc/?id=957][http_www.vckbase.com_document_viewdoc_

我就是我/ 2022年08月07日 05:51/ 0 赞/ 221 阅读

相关 EXCEL的小妙用

今天，上面给了一个excel，让根据“门店编号”，将对应的“门店ID”导入到数据库中。怎么解？如果，一个个找，然后复制粘贴，太浪费时间了。用sql语

旧城等待，/ 2022年06月10日 07:57/ 0 赞/ 218 阅读

相关 createDocumentFragment()方法的妙用

在更新少量节点的时候可以直接向document.body节点中添加，但是当要向document中添加大量数据时，如果直接添加这些新节点，这个过程非常缓慢，因为每添加一个节点都会

àì夳堔傛蜴生んèń/ 2022年06月02日 08:28/ 0 赞/ 202 阅读

相关 void的妙用

任何表达式都会产生一个值，但是在算数表达式中，如果对计算的值没有进行接收或进行任何其他操作，那么在强制警告的时候编译就会出现警告，此时需要将表达式转为void，表示显示的将该值

男娘i/ 2022年03月21日 12:54/ 0 赞/ 242 阅读

相关 js妙用

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] ()()函数自执行操作：如果你这么写 functi

妖狐艹你老母/ 2022年01月14日 02:27/ 0 赞/ 242 阅读

相关 Convert的妙用

今天无意中发现 Convert.ToString() 还有二进制转换功能,特记录一下,以备后用. // 十进制转二进制 Console.WriteLine(Co

ゝ一世哀愁。/ 2022年01月06日 07:37/ 0 赞/ 337 阅读

相关 onerror的妙用

<html> <body> 姓名:<input type="text"/> <img src = "7777.png" onerror

小咪咪/ 2021年12月19日 00:51/ 0 赞/ 286 阅读

相关 git rebase 的妙用

首先来看应用场景：我们要修改之前某一个特定的commit的时候，就需要用到这个命令。假如之前的某个提交的上一笔commit id是：928fc8a3686bf5fcf452

小鱼儿/ 2021年10月19日 12:24/ 0 赞/ 322 阅读