为什么需要位运算
机器采用二进制对数值进行表示、存储和运算
在程序中恰当地使用二进制，可以提高运行效率
位运算符
异或运算(xor)
相同为0，不同为1
也可用“不进位加法”来理解
异或运算的特点与应用:
指定位置的位运算
二进制数的最右边为第0位
获取×在二进制下的第n位（0或者1) :(x >>n)& 1
将×在二进制下的第n位置为1:x |(1<
将×在二进制下的第n位置为0: x&(~(1 <
将×在二进制下的第n位取反:x^(1 <
将×最右边的n位清零:x&(~0<
将×最高位至第n位（含）清零:x&((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等技术内容，立即学习
