数据结构与算法———位运算
本文最后更新于 599 天前,其中的信息可能已经有所发展或是发生改变。

位运算

位运算: 直接对整数在内存中的二进制位进行操作。比如6的二进制是110,11的二进制是1011,那么6 and 11的结果就是2,它是二进制对应位进行逻辑运算的结果。由于位运算直接在内存数据进行操作,不需要转为十进制,因此速度非常快。

符号 描述 运算规则
& 两个都为1时,结果才为1
| 两个都为 0时,结果才为1
^ 异或 相同为0,不同为1
~ 取反 0变1,1变0
<< 左移 各二进制位全部左移若干位,高位丢弃,低位补0
>> 右移 各二进制位全部右移若干位,对于无符号数,高位补0,;对于有符号数,有的补符号位(算数右移),有的补0(逻辑右移)

异或的特点:

  • x^0 = x
  • x^1s = ~x1s的意思是全为1的二进制数
  • x^(~x) = 1s
    • x^x = 0
    • a^b = c $\rightarrow$ a^c = b, b^c = a。用来交换a、b的值。比如,设a = 1001, b = 1100,那么c = a^b = 0101,则a^c = 1100, b^c = 1001,正好可以交换a、b的值。
    • a^b^c = a^(b^c) = (a^b)^c

常用的位运算操作:

  • 判断奇偶数:x & 1 ==1为奇数,x & 1 == 0为偶数
  • 清零最低位的1:x & (x-1)
  • 得到最低位的1:x & -x-x为取反再加1

更为复杂的位运算操作:

  • 将x最右边的n位清零:x & (~ 0<<n)
  • 获取x的第n位值(0或1):(x >> n) & 1
  • 获取x的第n位幂值:x & (1 << (n-1))
  • 仅将第n位置为1:x | (1<<n)
  • 仅将第n位置为0:x & (~(1<<n))
  • 将x最高位至第n位(含)清零:x & ((1 << n)-1)
  • 将x第n位至第0位(含)清零:x & (~((1 << (n+1))-1))

例题

位1的个数:

此题为leetcode第191题。用“常用的位运算操作”里的“清零最低位的1”

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n != 0:
            res += 1
            n = n & (n - 1)
        return res

2的幂:

此题为leetcode第231题。2的幂化成2进制,它们都只有一个1,只要判断1的个数即可

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n != 0 and n & (n - 1) == 0

比特位计数

此题为leetcode第338题给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = [0] * (num + 1)
        for n in range(1, num + 1):
            res[n] += (res[n&(n-1)] + 1)
        return res

N皇后II,位运算解法

此题为leetcode第52题,常规用深度优先搜索解法,会用到集合去保存横竖、斜角方向上的状态,解法点这里。而使用位运算可以直接获得棋盘上可以放皇后的位置,可以提高效率。

class Solution:
    # 使用位运算解决
    def totalNQueens(self, n):
        if n < 1:
            return []
        self.count = 0
        self.DFS(n, 0, 0, 0, 0) 
        return self.count

    def DFS(self, n, row, col, pie, na):
        if row >= n:
            self.count += 1
            return 

        # 获得可以放皇后的位置
        bits = (~(col | pie | na)) & ((1 << n) - 1)

        # 递归
        while bits:
            p = bits & -bits    # 获得最低位的1,也就是遍历合法的位置
            self.DFS(n, row + 1, (col | p), (pie | p) << 1, (na | p) >> 1)
            bits = bits & (bits - 1)    # 去掉最低位的1
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇