leetcode位运算思路总结

leetcode位运算题解和总结,使用Python完成,未来选择性的加入lintcode题解。


Python3题解及刷题完成度详见gayhub:


Single Number:

对数组中的元素一一异或,相同的数异或=0。

实现异或的两种方式:

def _xor(self,a,b):
return a^b
# or
import operator
from functools import reduce

return reduce(operator.xor, A)


Single Number Ⅱ

其他元素出现3次,使用统计方法或者位运算。
位运算解法和其他元素出现4次时的解法:

# one 出现一次  two 出现两次  three 出现三次
one, two = 0
one, two = (~x & one) | (x & ~one & ~two), (~x & two) | (x & one)
one, two, three = (~x & one) | (x & ~one & ~two & ~three), (~x & two) | (x & one), (~x & three) | (x & two)

使用counter计算:

import collections
return (collections.Counter(list(set(nums))*3) - collections.Counter(nums)).keys()[0]


Single Number Ⅲ

两个元素出现一次,其他元素出现两次
全部异或,得到xor,获得bit:

bit = xor & ~xor

bit是两个数第一个不相同的位

result[bool(i&bit)] ^= i

其他数异或下来都是0 , 这两个数异或下来的bool值一个是1 一个是0,成功分到了一个数组中。


Reverse Bits

二进制翻转,原数右移一位,赋给result,result左移一位:

result = 0
for i in range(32):
result <<= 1
result |= n&1 # 取右边第一位
n >>= 1

使用zfill(返回指定长度的字符串–右对齐)的一行解:

return int(bin(n)[2:].zfill(32)[::-1], 2) # bin()开头是0b

Q:如果该方法被大量调用,或者用于处理超大数据(Bulk data)时有什么优化方法?

A:将数字分成8份,每份只能是0-15,记录0-15的翻转值,array或者map:

private int[] reverseHex = new int[] {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};

// you need treat n as an unsigned value
public int reverseBits(int n) {
int rev = 0;
while (n != 0) {
rev = (rev << 4) + reverseHex[n & 0xF];
n >>>= 4;
}
return rev;
}


Number of 1 Bits

求出二进制数中1的个数

def hammingWeight(self, n):
result = 0
while n:
n &= n - 1
result += 1
return result

n&(n-1)的妙用:

n与n-1的区别在于,对于n,从右向左数的第一个"1"开始一直到右,和n-1,完全相反
n&(n-1)作用:将n的二进制表示中的最低位为1的改为0

Bitwise AND of Numbers Range


Author: Ykk
Link: https://ykksmile.top/posts/24951/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.