【算法】lc位运算合集
1.lc231. 2 的幂原题链接
给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。 如果存在一个整数 x 使得 n == 2x ,则认为 n 是 2 的幂次方。
思路一:找到int范围内最大的2的幂(2 ^ 30) 对 n 取模 如果等于0则true
code
return n > 0 && (1 << 30) % n == 0;
思路二:利用lowbit操作
lowbit : x & -x 等于x二进制表示的最右边的1; eg: x : 1011000 -x : 0100111 + 1 = 0101000 X & -X = 0001000
对于此题,在 x lowbit操作后,因为如果 x 是2的幂,他的最右1一定是在第一位,还是等于他本身
code
return n > 0 && (n & -n) == n;
2.lc762二进制表示中质数个计算置位原题链接
给定两个整数 L 和 R ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个数。 (注意,计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有,1 不是质数。)
思路:主要在统计1的个数上:
- 第一种:利用lowbit操作统计1的个数
- 第二种: 每次cnt += x & 1 然后 x >>= 1;
(此题数据范围较小1的个数不多可以弄个质数表偷鸡判断质数)
笨比codeclass Solution { public int countPrimeSetBits(int left, int right) { int cnt = 0; for(int i = left; i <= right; i ++){ // int sum = count(i); int sum = 0; for(int k = i; k > 0; k >>= 1)sum += k & 1; if(sum == 1)continue; boolean flag = true; for (int j = 2; j <= sum / j; j ++ ){ if (sum % j == 0)flag = false; } if(flag)cnt ++; } return cnt; } public int count(int n){ int res = 0; while(n != 0){ n -= (n & - n); res ++; } return res; } }
3.lc136只出现一次的数字原题链接
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。 找出那个只出现了一次的元素。
思路:
利用异或运算 (满***换律和结合律)
a ^ a = 0
a ^ 0 = a
code
class Solution { public int singleNumber(int[] nums) { int cnt = 0; for(int i = 0; i < nums.length; i ++){ cnt ^= nums[i]; } return cnt; } }
4.lc476数字的补数原题链接
给你一个 正 整数 num ,输出它的补数。补数是对该数的二进制表示取反。
思路:
统计每一位的反,再将该数左移到对应的位即可,注意不是求的fan
code
class Solution { public int findComplement(int num) { int res = 0; int t = 0; //注意不是补码,只是取反 while(num > 0){ res += (1 - num & 1) << t; num = num >> 1; t ++; } return res; } }
5.lc371. 两整数之和原题链接
不使用运算符 + 和 - ,计算两整数 a 、b 之和。
思路:
利用异或将两数相加,在相与看是否进位即可。(异或相当于不进位加法:1 ^ 1 → 0,1 ^ 0 → 1, 0 ^ 0 → 0)
这题最多只会递归32次,因为每迭代一次b << 1,会在其最后一位多个0,到最后b一定等于0;
code
class Solution { public int getSum(int a, int b) { if(b == 0)return a;//不用进位即得答案 int sum = a ^ b;//异或可以想成不进位加法 int carry = (a & b) << 1; return getSum(sum,carry); } }