位运算
实用操作
- X & 1：等于1是奇数，等于0是偶数
- X & (X-1)：消掉X二进制的最后一位1
- X & -X：获取X最后一位1
异或
^，例如X & 1同样可以用X ^ 0表示
(1) 按位异或可以用来使某些特定的位翻转，如对数10100001的第2位和第3位翻转，可以将数与00000110进行按位异或运算。
10100001^00000110=10100111 //1010 0001 ^ 0x06 = 1010 0001 ^ 6
(2) 通过按位异或运算，可以实现两个值的交换，而不必使用临时变量。例如交换两个整数a，b的值，可通过下列语句实现：
a=10100001,b=00000110
a=a^b； //a=10100111
b=b^a； //b=10100001
a=a^b； //a=00000110
(3) 异或运算符的特点是：数a两次异或同一个数b（a=a^b^b）仍然为原值a.
经典题目
191. Number of 1 Bits
用n = n & (n-1)巧妙计算1的个数
- 时间复杂度：\(O(logn)\)
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while(n) {
res++;
n = n & (n-1);
}
return res;
}
};
补充：这题在Python上不能使用同样的做法，在Google了1小时左右，终于在官方文档中看到说明：
Two’s Complement binary for Negative Integers:
Negative numbers are written with a leading one instead of a leading zero. So if you are using only 8 bits for your twos-complement numbers, then you treat patterns from “00000000” to “01111111” as the whole numbers from 0 to 127, and reserve “1xxxxxxx” for writing negative numbers. A negative number, -x, is written using the bit pattern for (x-1) with all of the bits complemented (switched from 1 to 0 or 0 to 1). So -1 is complement(1 - 1) = complement(0) = “11111111”, and -10 is complement(10 - 1) = complement(9) = complement(“00001001”) = “11110110”. This means that negative numbers go all the way down to -128 (“10000000”).
Of course, Python doesn’t use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written "...1111111111111111111011".
所以，Python的实现现在是负数前面有无数多个1……，你需要先处理负数，使之变为二进制相同的正数才行，针对该题的话，C++默认是32位的，所以可以采用2**32 + x的方式处理
231. Power of Two
利用X & (X-1)即可
- 时间复杂度：\(O(1)\)
class Solution {
public:
bool isPowerOfTwo(int n) {
return (n > 0) && ((n & (n-1)) == 0);
}
};
338. Counting Bits
给定n，计算从1到n的所有数的二进制中1的个数
解法： 取i>>1 i除以2的数
因为i»1肯定比i小，所以其count肯定已经计算过了，类似于DP，因此count+(i&1)即可
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num+1, 0);
for(int i = 1; i <= num; i++) {
res[i] = res[i>>1]+(i&1);
}
return res;
}
};
50. Pow(x, n)
- 对n进行二分递归，减少乘以x的次数
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(logn)\)
- 用位运算的思想处理n，解题方法和1一样，但是实现不同
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(1)\)
下面仅给出位运算的方法，通过n >>= 1进行二分
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x = 1 / x
n = -n
ans = 1
while n:
if n & 1:
ans *= x
x *= x
n >>= 1
return ans
更多
个人更多算法总结在Github
