homework_week8

xkluan · xkluan · commit a54c2e896435 · 2020-08-02T15:53:28.000+08:00
diff --git a/Week08/191-位1的个数.py b/Week08/191-位1的个数.py
@@ -0,0 +1,7 @@
+class Solution:
+    def hammingWeight(self, n: int) -> int:
+        count = 0
+        while(n>0):
+            n = n & (n-1)
+            count +=1
+        return count
diff --git a/Week08/231-2的幂.py b/Week08/231-2的幂.py
@@ -0,0 +1,9 @@
+class Solution:
+    def isPowerOfTwo(self, n: int) -> bool:
+        if n==0:
+            return False
+        else:
+            if n & (n-1) == 0:
+                return True
+            else:
+                return False
diff --git a/Week08/NOTE.md b/Week08/NOTE.md
@@ -1 +1,25 @@
-学习笔记
+学习笔记
+## 指定位置的位运算
+1. 将x最右边的n位清零:x&(~0<<n)
+2. 获取x的第n位值(0或者1):(x>>n)&1
+3. 获取x的第n位的幂值:x&(1<<n)
+4. 仅将第n位置为1:x|(1<<n)
+5. 仅将第n位置为0:x&(~(1<<n))
+6. 将x最高位至第n位(含)清零:x&((1<<n)-1)
+7. 将第n位至第0位(含)清零:x&(~((1<<(n+1))-1))
+
+## 实战位运算要点
+• 判断奇偶:
+x%2==1 —>(x&1)==1 x%2==0 —>(x&1)==0
+• x>>1—>x/2.
+即: x=x/2; —> x=x>>1;
+mid=(left+right)/2; —> mid=(left+right)>>1;
+• X=X&(X-1)清零最低位的1
+• X&-X=>得到最低位的 1
+• X&~X=>0
+
+## Bloom Filter vs Hash Table
+一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索
+一个元素是否在一个集合中。
+优点是空间效率和查询时间都远远超过一般的算法，
+缺点是有一定的误识别率和删除困难。
