imicola 位运算
位运算

位运算

285 字 · 约 1 分钟

两数之间的运算符

  • 两数的运算符有 「与,或,异或」三种运算方式,它们都是将两个整数作为二进制数,对二进制表示中的每一位逐一运算。
运算 运算符 数学符号 解释
与 & &,and\And,and 只有两个对应位都为 1 时才为 1
或 | ∣,or\mid,or 只要两个对应位中有一个 1 时就为 1
异或 ^ ⊕,xor\oplus,xor 只有两个对应位不同时才为 1

一些总结经验:

  • 对或(|)运算而言,有如下性质:

    • a∣b=b∣aa \mid b = b \mid a
    • (a∣b)∣c=(b∣c)∣a\left( a \mid b \right) \mid c = \left( b \mid c \right) \mid a
    • a∣0=aa \mid 0 = a
    • a∣a=aa \mid a = a
    • 若 a≤ba\leq b,则 a∣c≤b∣ca \mid c \leq b \mid c(对无符号数成立)
    • a∣b≤max⁡(a,b)a \mid b \leq \max(a,b)
  • 对异或 ⊕\oplus 有如下性质:

    • a⊕b=a+b−2(a&b)a \oplus b = a + b - 2(a \& b)
    • a⊕b=x⇒a=b⊕xa \oplus b = x \Rightarrow a = b \oplus x