九. 位運(yùn)算
位運(yùn)算不需要轉(zhuǎn)換成10進(jìn)制, 因此處理速度非常快狂秦。
實(shí)戰(zhàn)常用位運(yùn)算
- x & 1 == 1 判斷奇偶 ( x % 2 == 1 )
- x = x & (x-1) 清零最低位的1
- x & -x 得到最低位的1
67. 二進(jìn)制求和
題目:給你兩個(gè)二進(jìn)制字符串我纪,返回它們的和(用二進(jìn)制表示)。
def addBinary(self, a: str, b: str) -> str:
x, y = int(a, 2), int(b, 2) # 直接轉(zhuǎn)成2進(jìn)制的int型
while y: # 直到進(jìn)位問題都處理ok
answer = x ^ y
carry = (x & y) << 1 # 注意進(jìn)位
x, y = answer, carry
return bin(x)[2:] # 轉(zhuǎn)成10進(jìn)制的int型
190. 顛倒二進(jìn)制位
題目:顛倒給定的 32 位無符號(hào)整數(shù)的二進(jìn)制位。
def reverseBits(self, n: int) -> int:
res = 0
for i in range(0, 32): # 0~31位共32位
if n & 1 == 1:
res += math.pow(2, 31-i) # 求和
n = n >> 1
return int(res)
191. 位1的個(gè)數(shù)
題目:位1的個(gè)數(shù)
思考:編碼理論里的漢明重問題
def hammingWeight(self, n: int) -> int:
ret = 0
while n: # 直到n=0
n &= n - 1 # 清零最低位的1
ret += 1
return ret