简介
学习链接:位运算(第 13 ~ 14 天)
位运算规则
运算符 | 描述 | 规则 |
---|
| | 按位或运算符 | 只要对应的两个二进位有一个为 1 1 1 时,结果位就为 1 1 1。 |
& | 按位与运算符 | 只有对应的两个二进位都为 1 1 1 时,结果位才为 1 1 1。 |
<< | 左移运算符 | 将二进制数的各个二进位全部左移若干位。<< 右侧数字指定了移动位数,高位丢弃,低位补 0 0 0。 |
>> | 右移运算符 | 对二进制数的各个二进位全部右移若干位。>> 右侧数字指定了移动位数,低位丢弃,高位补 0 0 0。 |
^ | 按位异或运算符 | 对应的两个二进位相异时,结果位为 1 1 1,二进位相同时则结果位为 0 0 0。 |
~ | 取反运算符 | 对二进制数的每个二进位取反,使数字 1 1 1 变为 0 0 0, 0 0 0 变为 1 1 1。 |
位运算应用
功 能 | 位运算 | 示例 |
---|
从右边开始,把最后一个 1 1 1 改写成 0 0 0 | x & (x - 1) | 100101000 -> 100100000 |
去掉右边起第一个 1 1 1 的左边 | x & (x ^ (x - 1)) 或 x & (-x) | 100101000 -> 1000 |
去掉最后一位 | x >> 1 | 101101 -> 10110 |
取右数第 k k k 位 | x >> (k - 1) & 1 | 1101101 -> 1, k = 4 |
取末尾 3 3 3 位 | x & 7 | 1101101 -> 101 |
取末尾 k k k 位 | x & 15 | 1101101 -> 1101, k = 4 |
只保留右边连续的 1 1 1 | (x ^ (x + 1)) >> 1 | 100101111 -> 1111 |
右数第 k k k 位取反 | x ^ (1 << (k - 1)) | 101001 -> 101101, k = 3 |
在最后加一个 0 0 0 | x << 1 | 101101 -> 1011010 |
在最后加一个 1 1 1 | (x << 1) + 1 | 101101 -> 1011011 |
把右数第 k k k 位变成 0 0 0 | x & ~(1 << (k - 1)) | 101101 -> 101001, k = 3 |
把右数第 k k k 位变成 1 1 1 | x | (1 << (k - 1)) | 101001 -> 101101, k = 3 |
把右边起第一个 0 0 0 变成 1 1 1 | x | (x + 1) | 100101111 -> 100111111 |
把右边连续的 0 0 0 变成 1 1 1 | x | (x - 1) | 11011000 -> 11011111 |
把右边连续的 1 1 1 变成 0 0 0 | x & (x + 1) | 100101111 -> 100100000 |
把最后一位变成 0 0 0 | x | 1 - 1 | 101101 -> 101100 |
把最后一位变成 1 1 1 | x | 1 | 101100 -> 101101 |
把末尾 k k k 位变成 1 1 1 | x | (1 << k - 1) | 101001 -> 101111, k = 4 |
最后一位取反 | x ^ 1 | 101101 -> 101100 |
末尾 k k k 位取反 | x ^ (1 << k - 1) | 101001 -> 100110, k = 4 |
练习题
leetcode.cn/problems/reverse-bits/description/" rel="nofollow">190. 颠倒二进制位
思路
代码
class Solution:def reverseBits(self, n):n = bin(n)n = str(n)[2:]if len(n) < 32:n = '0'*(32 - len(n)) + nn = n[::-1]return int(n, 2)
leetcode.cn/problems/number-of-1-bits/description/" rel="nofollow">191. 位1的个数
思路
- 利用
x & (x-1)
把最右1变0操作来统计1的数量
代码
class Solution(object):def hammingWeight(self, n):""":type n: int:rtype: int"""cnt = 0while n:n = n & (n - 1)cnt += 1return cnt
leetcode.cn/problems/bitwise-and-of-numbers-range/description/" rel="nofollow">201. 数字范围按位与
思路
- 参考官方题解,写的很明白
- 找公共前缀,通过位移计算前缀中1的位置。
代码
class Solution(object):def rangeBitwiseAnd(self, left, right):""":type left: int:type right: int:rtype: int"""shift = 0while left < right:left >>= 1right >>= 1shift += 1return left << shift