位运算 && 状态压缩

本文主要是介绍位运算 && 状态压缩，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. & : 和 and
2. | : 或 or
3. ^ : 异或 xor
4. ~ : 非 not  (从最高位到第0位反转；另外包括符号位)

设个位二进制 n (n = 0 or 1):

和：n = n & 1

取反：~n = n ^ 1

设二进制 n ，其中最低位为第 0 位

• 取出第 k 位：(n >> k) & 1
• 第k位取反：n ^ (1 << k)
• 取出第0 ~ k-1 位 : n & ((1 << k) - 1)
• 第k位取1 : n | (1 << k)
• 第k位取0 : n & (~(1 << k))
• 取出1的最低位(lowbit)：log₂(n & -n)

其他性质：

• 位运算独立性：位运算各位之间是独立的，每个位只与相同位数之间互相影响，不与其他任何位数有关。
• 异或成对交换：n 为偶数时，n ^ 1 = n+1; n 为奇数时，n ^ 1 = n -1。(0与1，2与3，4与5.....成对)（常用于建立反向边，如分层图、网络流残留网络）
• 关于二进制，∨n ∈ [0,35]，2ⁿ mod 37互不相等，且恰好取编 0 ~ 36。（哈希表）

这篇关于位运算 && 状态压缩的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！