LeetCode(关于比特位计算的算法题)

分析一下关于leetcode上的位运算的算法，有大佬有牛逼的思路请分享给小弟。

No1.颠倒的二进制位

我的思路：遍历整个32位无符号整数，找到等于1的位颠倒保存到一个变量记录下。

 

No.2 位1的个数

我的思路：the same

 

No.3 2的幂

 

我的思路：你会发现2的幂，在二进制里只有相对应的位为1，

2^0 = 0001;

2^1 = 0010 ;

2^2 = 0100 ;

2^3 = 1000

然后重点你会发现，(2^n) & (-2^n) == (2^n)

原码：3 = 0011 反码：1100   补码：1101  -3 =1101

 

源码&补码 = 0001

 

 原码：4 = 0100 反码：1011   补码：1100  -4 =1100

 

源码&补码 = 0100 == 源码

 

 原码：5 = 0101 反码：1010   补码：1011  -4 =1011

源码&补码 = 0001 == 源码

 原码：8 = 1000 反码：0111   补码：1000  

 原码：16 = 10000 反码：01111   补码：10000  

 

No.4 比特位计数

我的思路：其实跟上面的也是同一个套路

n&(n-1) 与 n相比你会发现它少了一个1 ，所以最后要加1

res[i] = res[i & (i - 1)] + 1;

0011 & 0010 = 0010

0010 & 0001 = 0000

0110 & 0101 = 0100

0111 & 0110 = 0110