《位运算》专题

Posted on Edited on In , Views:

1. 整数二进制中1的个数（汉明权重）

【解析】

常规法：判断最低位是0还是1，右移。

公式法：利用公式 n&(n−1) ，它的作用是消除二进制最右侧的1。因此在整数变为0之前，消除1的次数就是答案。

【ac代码】

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n)
        {
            n = n&(n-1);
            count++;
        }
        return count;
    }
};

2. 从二进制最右侧的1开始截取 lowbit()

比如

lowbit(1010) = 10
lowbit(101000) = 1000
它的实现有个简单的公式：
$$
lowbit(x) = x&(~x+1) = x&(-x)
$$
利用这个公式我们可以轻松求出某个数的二进制表示中1的个数：就是它不断与自己的lowbit异或的过程，到0为止。 

1
2
3
4
5
6
7
8
9
10
11
int NumberOf1(int n)
{       
    int count = 0;
    while(n)
    {
        n-=(n&(-n));
        count++;
    }
    return count; 
}

3. 从低位开始数第k位上的值

$$
(n>>k)&1
$$

4. 消掉最低位的1

$$
n&(n-1)
$$

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

【题目】

https://leetcode-cn.com/problems/power-of-two/

【解析】

对任意一个2的整数次幂n，其二进制的最高位为1，其余位为0；那么n-1的二进制最高位为0，其余位为1。因此如果n是2的整数次幂， n & (n-1) ==0 恒成立。

【ac代码】

1
2
3
4
5
6
7
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n<=0) return false;
        return !(n & (n-1));
    }
};