Bit Manipulation 位运算
知识点1 原码 反码 补码
最高位存符号位。
正数：原码=反码=补码 ；
负数：符号位不变，原码 --(取反)--> 反码 --(+1)--> 补码
>> 0.2+0.4==0.6
False
>> 0.2+0.4
0.6000000000000001
# Python, Java(Double), Why not 0.6?
# tips:做浮点数的时候，知道有精度丢失这么个点
知识点2 位运算符
- Java 位运算符
| 位运算符号 | |
|---|---|
| & | 注意和逻辑运算符区别 && |
| | | 逻辑运算符 || |
| ～ | 逻辑运算符 ！ |
| ^ 异或 | 相异为1 相同为0 |
| << left shift | 补0, 会溢出的"*2" |
| >> right shift | 补0或1，保持和最高位相同Why？"/2" |
| >>> 无符号right shift | 补0 |
- Python 位运算符
| 位运算符号 | |
|---|---|
| & | and |
| | | or |
| ～ | not |
| ^ 异或 | 相异为1 相同为0 |
| << left shift | 补0 无溢出的 "*2" |
| >> right shift | 补0或1，保持和最高位相同 "/2" |
知识点3 空间优化
Contain Unique Letter Word
Determine whether a word contains all letters that are unique (no duplicate letters in the word).
- 1 HashSet
- 2 Array，256个ASCII码 长度256的Array
- 3 Bit Vector 充分利用空间！！
- xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 0~31th bit
- xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 32~63th bit
- ... ...
318. Maximum Product of Word Lengths
给定一个字符串数组words，寻找length(words[i]) * length(words[j])的最大值，其中两个单词不包含相同字母。你可以假设每一个单词只包含小写字母。如果不存在这样的两个单词，返回0
- 1 Two words do not share common letters ：Bit！
- 2 包含相同类型letter的word只用取长度最长的
class Solution(object):
def maxProduct(self, words):
n = len(words)
if n <= 1: return 0
d = {}
for word in words:
mask = 0
for ch in word:
mask |= (1 << (ord(ch) - ord('a')))
d[mask] = max(d.get(mask, 0), len(word))
# pythonic：
# return max([d[x]*d[y] for x in d for y in d if not x & y])
res = 0
for x in d:
for y in d:
if not x & y:
res = max(res, d[x] * d[y])
return res