寒假培訓1.20 位運算 -开发者知识库

寒假培訓1.20 位運算 -开发者知识库,第1张

寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第2张

補碼: 負數 ~x 1 正數一樣

<< >> & ! ~ 運算符…

寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第3张
取某位: (x>>pos)&1
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第4张
將某些位置為1
x|(1<< i )
將某些位置為0
x&~(1<< i)
將某些位置取反
x^(1<< i)

求1的個數
1.查表 f[i]=f[i>>1] (i&1)
分段 分成16位
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第5张

如果內存很小怎么辦……
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第6张
(並沒有聽懂..)

求1的個數的奇偶性
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第7张
把它拆成兩個16位 xor一下 再拆成兩個8位 xor一下 ……最后判一判是不是1 就好了

GCC內建函數
__builtin_parity

翻轉位序
f(0) = 0
f(i) = (f(i >> 1) >> 1) | ((i & 1) << 15)
i處理到2^16

也可以這么搞
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第8张
拆成1、2、4、8、16位 相鄰的翻轉就好了

求前綴OR后綴0的個數
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第9张
這個看起來簡單一些
求后綴零同理
(也可以查表)
f[0]=16;
f[i]=f[i>>1]-1; 把32位的數拆成兩個16位的。搞定

第k個1的位置
二分 查表 (查一下有幾個 同1的個數)

提取末尾連續的1
x & (x ^ (x 1))

提取lowbit x&(-x)

bitset
count
find_first/find_next(GCC下 不是標准)

求集合中第k小元素
搞棵線段樹

lower_bound()
1.搞棵線段樹 前綴和 線段樹上二分 O(n/w*logn)
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第10张
就醬 把葉子換成64位整數 可以在整數內 用前面講到的求第k大
2.搞棵線段樹
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第11张
這樣子的 是一個“或”關系的線段樹
中間存儲就不用64位整數了
(好像線段樹思路沒有更好的辦法了 換個角度)

3.搞個輔助的bitset (w叉線段樹)
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第12张
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第13张
集合的與或非還是O(n)級別的改 就醬
O(logn/logw)
4.
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第14张
Tree只有loglogn層 vebTree 但是修改的時候麻煩一點兒
理論上n大的時候有優勢

枚舉子集 (y-1)&x
寒假培訓1.20 位運算 -开发者知识库,這里寫圖片描述,第15张
(DFS一遍 也好啊……)

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复