n&（n-1）的妙用

向右看齐 2023-10-17 14:03 51阅读 0赞

题目分析:求一个int的n,写成二进制的形式有多少个1?

1.用循环每次把n向右移动一位,判断n&1是否为1,这种方式会超时

2.采用n&(n-1)

**\[java\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **public****class** Solution \{ 
2.  // you need to treat n as an unsigned value
3.  **public****int** hammingWeight(**int** n) \{ 
4.  **int** total=0; 
5.  **while**(n!=0)\{ 
6.   total++; 
7.   n=n&(n-1); 
8.   \} 
9.  **return** total; 
10.  \} 
11. \}

#### n&(n-1)的妙用 (转)    ####

今天无聊拿起《编程之美》看了下，发现原来n&(n-1)还有很多妙用。原理:n与n-1的区别在于,对于n,从右向左数的第一个"1"开始一直到右,和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)的原理及作用，在碰到相关问题时也会比较容易解决。

[view plain]: http://blog.csdn.net/wconvey/article/details/44705639#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/630270
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/630270/fork