当前位置：首页 > article >正文

Leetcode算法基础篇-位运算

article 2024/11/18 6:24:43

简介

学习链接：位运算（第 13 ~ 14 天）

位运算规则

运算符	描述	规则
`\|`	按位或运算符	只要对应的两个二进位有一个为 $1$ 时，结果位就为 $1$ 。
`&`	按位与运算符	只有对应的两个二进位都为 $1$ 时，结果位才为 $1$ 。
`<<`	左移运算符	将二进制数的各个二进位全部左移若干位。`<<` 右侧数字指定了移动位数，高位丢弃，低位补 $0$ 。
`>>`	右移运算符	对二进制数的各个二进位全部右移若干位。`>>` 右侧数字指定了移动位数，低位丢弃，高位补 $0$ 。
`^`	按位异或运算符	对应的两个二进位相异时，结果位为 $1$ ，二进位相同时则结果位为 $0$ 。
`~`	取反运算符	对二进制数的每个二进位取反，使数字 $1$ 变为 $0$ ， $0$ 变为 $1$ 。

位运算应用

功能	位运算	示例
从右边开始，把最后一个 $1$ 改写成 $0$	`x & (x - 1)`	`100101000 -> 100100000`
去掉右边起第一个 $1$ 的左边	`x & (x ^ (x - 1))` 或 `x & (-x)`	`100101000 -> 1000`
去掉最后一位	`x >> 1`	`101101 -> 10110`
取右数第 $k$ 位	`x >> (k - 1) & 1`	`1101101 -> 1, k = 4`
取末尾 $3$ 位	`x & 7`	`1101101 -> 101`
取末尾 $k$ 位	`x & 15`	`1101101 -> 1101, k = 4`
只保留右边连续的 $1$	`(x ^ (x + 1)) >> 1`	`100101111 -> 1111`
右数第 $k$ 位取反	`x ^ (1 << (k - 1))`	`101001 -> 101101, k = 3`
在最后加一个 $0$	`x << 1`	`101101 -> 1011010`
在最后加一个 $1$	`(x << 1) + 1`	`101101 -> 1011011`
把右数第 $k$ 位变成 $0$	`x & ~(1 << (k - 1))`	`101101 -> 101001, k = 3`
把右数第 $k$ 位变成 $1$	`x \| (1 << (k - 1))`	`101001 -> 101101, k = 3`
把右边起第一个 $0$ 变成 $1$	`x \| (x + 1)`	`100101111 -> 100111111`
把右边连续的 $0$ 变成 $1$	`x \| (x - 1)`	`11011000 -> 11011111`
把右边连续的 $1$ 变成 $0$	`x & (x + 1)`	`100101111 -> 100100000`
把最后一位变成 $0$	`x \| 1 - 1`	`101101 -> 101100`
把最后一位变成 $1$	`x \| 1`	`101100 -> 101101`
把末尾 $k$ 位变成 $1$	`x \| (1 << k - 1)`	`101001 -> 101111, k = 4`
最后一位取反	`x ^ 1`	`101101 -> 101100`
末尾 $k$ 位取反	`x ^ (1 << k - 1)`	`101001 -> 100110, k = 4`

练习题

190. 颠倒二进制位

思路

执行操作即可

代码

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        n = bin(n)
        n = str(n)[2:]
        if len(n) < 32:
            n = '0'*(32 - len(n)) + n
        # print(n)
        n = n[::-1]
        return int(n, 2)

191. 位1的个数

思路

利用 x & (x-1)把最右1变0操作来统计1的数量

代码

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        cnt = 0
        while n:
            n = n & (n - 1)
            cnt += 1
        return cnt

201. 数字范围按位与

思路

参考官方题解，写的很明白
找公共前缀，通过位移计算前缀中1的位置。

代码

class Solution(object):
    def rangeBitwiseAnd(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: int
        """
        shift = 0
        while left < right:
            left >>= 1
            right >>= 1
            shift += 1
        return left << shift