位运算 - wenzhoullq/leetcode GitHub Wiki
int
int 是32位,做位运算的最大值的时候取的是31位
交换律和结合律
位运算中 ^ 和 & 满足 结合律,即 (b&c)^a = (a^b)&(a^c),记忆方式是 把&当作+,把^当作*, 其他的都满足交换律
题目
X进制
取模运算,如果有mod>1的话,代表无法转为这个进制(因为一个进制只能有一位
题目
位运算区分数字
不同题目要求不同
题目
136. 只出现一次的数字 ^即可
137. 只出现一次的数字 II 计算每一位的累计和,然后%
260. 只出现一次的数字 III 不是累计,是用一个数进行区分
| 和 ^
^ 运算只能去掉一个|运算
题目
*|运算和连续
可以记录一个dp来统计最后一次这个位上的出现是哪个数字
题目
逆序位运算
模板
for(int i=0;i<32;i++){ ans|=((1&(n>>i))<<(31-i));//先右移,取到第一位,然后再左移(31-i) }
题目
最长前缀
最长前缀和&运算有关
题目
是否有重复字符
将字符和num|计算,然后num1&num是否为0,为0则无重复
题目
其他
不好归类
题目
338. 比特位计数 n和n/2+n%2的关系是 二进制1的个数一样,和
6127. 优质数对的数目 &和|的关系,在数量上,bitCount(a|b)+bitCount(a&b)=bitCount(a)+bitCount(b) ,可以通过画韦恩图来理解
6209. 二的幂数组中查询范围内的乘积 前缀积会爆long,通过位运算分解后很短,可以暴力求解