实战技巧位运算

为什么需要位运算

机器采用二进制对数值进行表示、存储和运算
在程序中恰当地使用二进制，可以提高运行效率

位运算符

异或运算(xor)

相同为0，不同为1
也可用“不进位加法”来理解

异或运算的特点与应用:

指定位置的位运算

二进制数的最右边为第0位

获取×在二进制下的第n位（0或者1) :(x >>n)& 1

将×在二进制下的第n位置为1:x |(1<<n)
将×在二进制下的第n位置为0: x&(~(1 <<n))
将×在二进制下的第n位取反:x^(1 <<n)

将×最右边的n位清零:x&(~0<<n)
将×最高位至第n位（含）清零:x&((1<<n)- 1)

位运算实战要点

判断奇偶:

• x % 2 == 1 →(x & 1)== 1
• x% 2 == 0 (x & 1)== 0

.
除以2的幂次:

• x/2 → x>> 1
• mid = (left + right)/ 2; →mid =(left + right) >> 1;

lowbit:

• 得到最低位的1: x &-x或x&(~x+ 1)
• 清零最低位的1∶ x=x &(x- 1)

实战

https://leetcode.cn/problems/number-of-1-bits/

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n > 0){
            if((n & 1) == 1) cnt++;
            n = n >> 1;
        }
        return cnt;
    }
};

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        for(int i = 0; i < 32; i++){
            if((n >> i) & 1) cnt++;
        }

        return cnt;
    }
};

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n > 0){
            cnt++;
            n = n & (n - 1);
        }

        return cnt;
    }
};

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

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};

https://leetcode.cn/problems/reverse-bits/

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans = 0;
        for(int i = 0; i < 32; i++){
            ans = (ans << 1) | (n >> i & 1);
        }
        return ans;
    }
};

https://leetcode.cn/problems/counting-bits/

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> cnt(n + 1, 0);
        for(int i = 1; i <= n; i++){
            cnt[i] = cnt[i & (i - 1)] + 1;
        }
        return cnt;
    }
};

分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习