常用的位运算有6个:
&
|
~
^
相当于不进位的加法
<<
<< 1 相当于x2 上取整 << 3相当于x8
>>
>> 1 相当于/2 下取整
技巧篇
- lowbit运算1:
n & -n
表示 n的二进制表示里最右边的1,所以 n & -n == n
表示n为2的整数次幂,n & -n < n
则n不为2的整数次方 - lowbit运算2:
n & (n -1)
就会把该整数二进制的最后一位1置零 - 异或运算^:
a ^ a = 0
, 0 ^ a = a
而且异或满足交换律和结合律
实战篇:剑指offer15题——二进制中的1的个数
本题思考方式可以将数字的最后一位和1进行与运算,然后右移来统计二进制中的1.但是如果整数为负数的时候,就会出现补1的情况从而造成死循环。
解决办法1
将输入的数字强制转换成unsigned int
类型即可。
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
unsigned int un = n;
while (un) res += un & 1, un >>= 1;
return res;
}
};
解决办法2
设置一个unsigned int flag = 1 每次与输入整数进行与运算后判断是否为1尔后左移统计1的个数,从而负数高位补零造成死循环。
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
unsigned int flag = 1;
while (flag) {
if (flag & n) res++;
flag <<= 1;
}
return res;
}
};
解决办法3
n & (n -1)就会把该整数二进制的最后一位1置零。那么二进制数有多少个1就会进行多少次这样的操作。
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
while (n){
n &= (n + 1);
res++;
}
return res;
}
};
LeetCode231:2的幂
给定一个整数,编写一个函数来判断它是否是 2 的幂次方。
利用lowbit运算即可判断:
class Solution {
public:
bool isPowerOfTwo(int n) {
//return n > 0 && (n & -n) == n;
return (n > 0) ? ((n & -n) == n) : false;
}
};
LeetCode762:二进制表示中质数个计算置位
给定两个整数 L 和 R ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个数。
注意:
- 计算置位代表二进制表示中1的个数。
- L, R 是 L <= R 且在 [1,
] 中的整数。
- R - L 的最大值为 10000。
解题思路
- 根据R的上限可以判断R <=
,因为
是1024,1024的平方大于
,所以判断正确,可以定义
存储枚举的素数。
- 在循环前设置结果变量res,初始化为0;
- 外循环遍历数据范围,内循环遍历当前数据二进制的每一位进行lowbit操作,将数据最右侧1置零,同时统计1的个数。若统计个数在枚举的容器中,则结果加1;最后返回res就是最终答案。
class Solution {
public:
int countPrimeSetBits(int L, int R) {
unordered_set<int> prime({2, 3,5,7,11,13,17,19});
int res = 0;
for (int n = L; n <= R; n++){
int sum = 0;
for (int k = n; k; k &= (k - 1))
sum++;
if (prime.count(sum))
res++;
}
return res;
}
};
LeetCode136:只出现1次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
运用异或的性质即可,相同数字异或相当于消消乐,即为0,而0与任何数字异或都等于当前数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (auto x : nums)
res ^= x;
return res;
}
};
LeetCode137:只出现1次的数字II
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
要求:不使用额外的空间
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (int bit = 0; bit < 32; bit++){
int counter = 0;
for (int i = 0; i < nums.size(); i++)
counter += (nums[i] >> bit) & 1;
res += (counter % 3) << bit;
}
return res;
}
};
LeetCode137:只出现1次的数字III
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int s = 0;
for (auto x : nums) s ^= x; // 消除了相同数字,只剩下只出现一次的两个数字异或
//假设 s = a ^ b
int k = 0;
while (!(s >> k & 1)) // 求一个整数s的第k位是0还是1,比较常用的技巧
k++;
int s2 = 0;
for (auto x : nums)
if (x >> k &1)
s2 ^= x; // s2 = a
// 所以 s ^ s2 = a ^ b ^ a = b;
return vector<int>({s2, s ^ s2});
}
};
LeetCode476: 数字的补数
给定一个正整数,输出它的补数。补数是对该数的二进制表示取反。
- 输入两个数m和n,计算需要改变m的二进制表示的多少位才能得到n。