Skip to content

binary_op.md

Latest commit

History

History
201 lines (138 loc) · 5.9 KB

binary_op.md

File metadata and controls

201 lines (138 loc) · 5.9 KB
Raw

二进制

常见二进制操作

基本操作

a=0^a=a^0

0=a^a

由上面两个推导出：a=a^b^b

交换两个数

a=a^b

b=a^b

a=a^b

移除最后一个 1

a=n&(n-1)

获取最后一个 1

diff=(n&(n-1))^n

常见题目

single-number

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

classSolution:
defsingleNumber(self, nums: List[int]) ->int:
out=0fornuminnums:
out^=numreturnout

single-number-ii

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

classSolution:
defsingleNumber(self, nums: List[int]) ->int:
seen_once=seen_twice=0fornuminnums:
seen_once=~seen_twice& (seen_once^num)
seen_twice=~seen_once& (seen_twice^num)
returnseen_once

single-number-iii

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

classSolution:
defsingleNumber(self, nums: int) ->List[int]:
# difference between two numbers (x and y) which were seen only oncebitmask=0fornuminnums:
bitmask^=num# rightmost 1-bit diff between x and ydiff=bitmask& (-bitmask)
x=0fornuminnums:
# bitmask which will contain only xifnum&diff:
x^=numreturn [x, bitmask^x]

number-of-1-bits

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

classSolution:
defhammingWeight(self, n: int) ->int:
num_ones=0whilen>0:
num_ones+=1n&=n-1returnnum_ones

counting-bits

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

  • 思路：利用上一题的解法容易想到 O(nk) 的解法，k 为位数。但是实际上可以利用动态规划将复杂度降到 O(n)，想法其实也很简单，即当前数的 1 个数等于比它少一个 1 的数的结果加 1。下面给出三种 DP 解法
# x <- x // 2classSolution:
defcountBits(self, num: int) ->List[int]:
num_ones= [0] * (num+1)
foriinrange(1, num+1):
num_ones[i] =num_ones[i>>1] + (i&1) # 注意位运算的优先级returnnum_ones
# x <- x minus right most 1classSolution:
defcountBits(self, num: int) ->List[int]:
num_ones= [0] * (num+1)
foriinrange(1, num+1):
num_ones[i] =num_ones[i& (i-1)] +1returnnum_ones
# x <- x minus left most 1classSolution:
defcountBits(self, num: int) ->List[int]:
num_ones= [0] * (num+1)
left_most=1whileleft_most<=num:
foriinrange(left_most):
ifi+left_most>num:
breaknum_ones[i+left_most] =num_ones[i] +1left_most<<=1returnnum_ones

reverse-bits

颠倒给定的 32 位无符号整数的二进制位。

思路：简单想法依次颠倒即可。更高级的想法是考虑到处理超长比特串时可能出现重复的pattern，此时如果使用 cache 记录出现过的 pattern 并在重复出现时直接调用结果可以节约时间复杂度，具体可以参考 leetcode 给出的解法。

importfunctoolsclassSolution:
defreverseBits(self, n):
ret, power=0, 24whilen:
ret+=self.reverseByte(n&0xff) <<powern=n>>8power-=8returnret# memoization with decorator@functools.lru_cache(maxsize=256)defreverseByte(self, byte):
return (byte*0x0202020202&0x010884422010) %1023

bitwise-and-of-numbers-range

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

思路：直接从 m 到 n 遍历一遍显然不是最优。一个性质，如果 m 不等于 n，则结果第一位一定是 0 （中间必定包含一个偶数）。利用这个性质，类似的将 m 和 n 右移后我们也可以判断第三位、第四位等等，免去了遍历的时间复杂度。

classSolution:
defrangeBitwiseAnd(self, m: int, n: int) ->int:
shift=0whilem<n:
shift+=1m>>=1n>>=1returnm<<shift

练习