Bitwise operations on natural numbers

In the first half of this file, we provide theorems for reasoning about natural numbers from their bitwise properties. In the second half of this file, we show properties of the bitwise operations lor, land and xor, which are defined in core.

Main results

• eq_of_testBit_eq: two natural numbers are equal if they have equal bits at every position.
• exists_most_significant_bit: if n ≠ 0, then there is some position i that contains the most significant 1-bit of n.
• lt_of_testBit: if n and m are numbers and i is a position such that the i-th bit of of n is zero, the i-th bit of m is one, and all more significant bits are equal, then n < m.

Future work

There is another way to express bitwise properties of natural number: digits 2. The two ways should be connected.

Keywords

bitwise, and, or, xor

@[simp]

theorem Nat.bitwise_zero_left {f : Bool → Bool → Bool} (m : ℕ) : Nat.bitwise f 0 m = if f false true = true then m else 0

@[simp]

theorem Nat.bitwise_zero_right {f : Bool → Bool → Bool} (n : ℕ) : Nat.bitwise f n 0 = if f true false = true then n else 0

theorem Nat.bitwise_zero {f : Bool → Bool → Bool} : Nat.bitwise f 0 0 = 0

theorem Nat.bitwise_of_ne_zero {f : Bool → Bool → Bool} {n : ℕ} {m : ℕ} (hn : n ≠ 0) (hm : m ≠ 0) : Nat.bitwise f n m = Nat.bit (f (Nat.bodd n) (Nat.bodd m)) (Nat.bitwise f (n / 2) (m / 2))

theorem Nat.binaryRec_of_ne_zero {C : ℕ → Sort u_1} (z : C 0) (f : (b : Bool) → (n : ℕ) → C n → C (Nat.bit b n)) {n : ℕ} (h : n ≠ 0) : Nat.binaryRec z f n = (_ : Nat.bit (Nat.bodd n) (Nat.div2 n) = n) ▸ f (Nat.bodd n) (Nat.div2 n) (Nat.binaryRec z f (Nat.div2 n))

@[simp]

theorem Nat.bitwise_bit {f : Bool → Bool → Bool} (h : autoParam (f false false = false) _auto✝) (a : Bool) (m : ℕ) (b : Bool) (n : ℕ) : Nat.bitwise f (Nat.bit a m) (Nat.bit b n) = Nat.bit (f a b) (Nat.bitwise f m n)

theorem Nat.bit_mod_two (a : Bool) (x : ℕ) : Nat.bit a x % 2 = if a = true then 1 else 0

@[simp]

theorem Nat.bit_mod_two_eq_zero_iff (a : Bool) (x : ℕ) : Nat.bit a x % 2 = 0 ↔ (!a) = true

@[simp]

theorem Nat.bit_mod_two_eq_one_iff (a : Bool) (x : ℕ) : Nat.bit a x % 2 = 1 ↔ a = true

@[simp]

theorem Nat.lor_bit (a : Bool) (m : ℕ) (b : Bool) (n : ℕ) : Nat.bit a m ||| Nat.bit b n = Nat.bit (a || b) (m ||| n)

@[simp]

theorem Nat.land_bit (a : Bool) (m : ℕ) (b : Bool) (n : ℕ) : Nat.bit a m &&& Nat.bit b n = Nat.bit (a && b) (m &&& n)

@[simp]

theorem Nat.ldiff_bit (a : Bool) (m : ℕ) (b : Bool) (n : ℕ) : Nat.ldiff (Nat.bit a m) (Nat.bit b n) = Nat.bit (a && !b) (Nat.ldiff m n)

@[simp]

theorem Nat.xor_bit (a : Bool) (m : ℕ) (b : Bool) (n : ℕ) : Nat.bit a m ^^^ Nat.bit b n = Nat.bit (a != b) (m ^^^ n)

theorem Nat.testBit_lor (m : ℕ) (n : ℕ) (k : ℕ) : Nat.testBit (m ||| n) k = (Nat.testBit m k || Nat.testBit n k)

theorem Nat.testBit_land (m : ℕ) (n : ℕ) (k : ℕ) : Nat.testBit (m &&& n) k = (Nat.testBit m k && Nat.testBit n k)

@[simp]

theorem Nat.testBit_ldiff (m : ℕ) (n : ℕ) (k : ℕ) : Nat.testBit (Nat.ldiff m n) k = (Nat.testBit m k && !Nat.testBit n k)

@[simp]

theorem Nat.bit_false : Nat.bit false = bit0

@[simp]

theorem Nat.bit_true : Nat.bit true = bit1

@[simp]

theorem Nat.bit_eq_zero {n : ℕ} {b : Bool} : Nat.bit b n = 0 ↔ n = 0 ∧ b = false

theorem Nat.bit_ne_zero_iff {n : ℕ} {b : Bool} : Nat.bit b n ≠ 0 ↔ n = 0 → b = true

theorem Nat.bitwise_bit' {f : Bool → Bool → Bool} (a : Bool) (m : ℕ) (b : Bool) (n : ℕ) (ham : m = 0 → a = true) (hbn : n = 0 → b = true) : Nat.bitwise f (Nat.bit a m) (Nat.bit b n) = Nat.bit (f a b) (Nat.bitwise f m n)

An alternative for bitwise_bit which replaces the f false false = false assumption with assumptions that neither bit a m nor bit b n are 0 (albeit, phrased as the implications m = 0 → a = true and n = 0 → b = true)

theorem Nat.bitwise_eq_binaryRec (f : Bool → Bool → Bool) : Nat.bitwise f = Nat.binaryRec (fun (n : ℕ) => bif f false true then n else 0) fun (a : Bool) (m : ℕ) (Ia : ℕ → ℕ) => Nat.binaryRec (bif f true false then Nat.bit a m else 0) fun (b : Bool) (n x : ℕ) => Nat.bit (f a b) (Ia n)

theorem Nat.zero_of_testBit_eq_false {n : ℕ} (h : ∀ (i : ℕ), Nat.testBit n i = false) : n = 0

theorem Nat.testBit_eq_false_of_lt {n : ℕ} {i : ℕ} (h : n < 2 ^ i) : Nat.testBit n i = false

theorem Nat.testBit_eq_inth (n : ℕ) (i : ℕ) : Nat.testBit n i = List.getI (Nat.bits n) i

The ith bit is the ith element of n.bits.

theorem Nat.exists_most_significant_bit {n : ℕ} (h : n ≠ 0) : ∃ (i : ℕ), Nat.testBit n i = true ∧ ∀ (j : ℕ), i < j → Nat.testBit n j = false

theorem Nat.lt_of_testBit {n : ℕ} {m : ℕ} (i : ℕ) (hn : Nat.testBit n i = false) (hm : Nat.testBit m i = true) (hnm : ∀ (j : ℕ), i < j → Nat.testBit n j = Nat.testBit m j) : n < m

@[simp]

theorem Nat.testBit_two_pow_self (n : ℕ) : Nat.testBit (2 ^ n) n = true

theorem Nat.testBit_two_pow_of_ne {n : ℕ} {m : ℕ} (hm : n ≠ m) : Nat.testBit (2 ^ n) m = false

theorem Nat.testBit_two_pow (n : ℕ) (m : ℕ) : (Nat.testBit (2 ^ n) m = true) = (n = m)

theorem Nat.bitwise_swap {f : Bool → Bool → Bool} : Nat.bitwise (Function.swap f) = Function.swap (Nat.bitwise f)

theorem Nat.bitwise_comm {f : Bool → Bool → Bool} (hf : ∀ (b b' : Bool), f b b' = f b' b) (n : ℕ) (m : ℕ) : Nat.bitwise f n m = Nat.bitwise f m n

If f is a commutative operation on bools such that f false false = false, then bitwise f is also commutative.

theorem Nat.lor_comm (n : ℕ) (m : ℕ) : n ||| m = m ||| n

theorem Nat.land_comm (n : ℕ) (m : ℕ) : n &&& m = m &&& n

theorem Nat.xor_comm (n : ℕ) (m : ℕ) : n ^^^ m = m ^^^ n

theorem Nat.and_two_pow (n : ℕ) (i : ℕ) : n &&& 2 ^ i = Bool.toNat (Nat.testBit n i) * 2 ^ i

theorem Nat.two_pow_and (n : ℕ) (i : ℕ) : 2 ^ i &&& n = 2 ^ i * Bool.toNat (Nat.testBit n i)

@[simp]

theorem Nat.zero_xor (n : ℕ) : 0 ^^^ n = n

@[simp]

theorem Nat.xor_zero (n : ℕ) : n ^^^ 0 = n

def Nat.tacticBitwise_assoc_tac : Lean.ParserDescr

Proving associativity of bitwise operations in general essentially boils down to a huge case distinction, so it is shorter to use this tactic instead of proving it in the general case.

Equations

• Nat.tacticBitwise_assoc_tac = Lean.ParserDescr.node `Nat.tacticBitwise_assoc_tac 1024 (Lean.ParserDescr.nonReservedSymbol "bitwise_assoc_tac" false)

theorem Nat.xor_assoc (n : ℕ) (m : ℕ) (k : ℕ) : n ^^^ m ^^^ k = n ^^^ (m ^^^ k)

theorem Nat.land_assoc (n : ℕ) (m : ℕ) (k : ℕ) : n &&& m &&& k = n &&& (m &&& k)

theorem Nat.lor_assoc (n : ℕ) (m : ℕ) (k : ℕ) : n ||| m ||| k = n ||| (m ||| k)

@[simp]

theorem Nat.xor_self (n : ℕ) : n ^^^ n = 0

theorem Nat.lxor_cancel_right (n : ℕ) (m : ℕ) : m ^^^ n ^^^ n = m

theorem Nat.xor_cancel_left (n : ℕ) (m : ℕ) : n ^^^ (n ^^^ m) = m

theorem Nat.xor_right_injective {n : ℕ} : Function.Injective (HXor.hXor n)

theorem Nat.xor_left_injective {n : ℕ} : Function.Injective fun (m : ℕ) => m ^^^ n

@[simp]

theorem Nat.xor_right_inj {n : ℕ} {m : ℕ} {m' : ℕ} : n ^^^ m = n ^^^ m' ↔ m = m'

@[simp]

theorem Nat.xor_left_inj {n : ℕ} {m : ℕ} {m' : ℕ} : m ^^^ n = m' ^^^ n ↔ m = m'

@[simp]

theorem Nat.xor_eq_zero {n : ℕ} {m : ℕ} : n ^^^ m = 0 ↔ n = m

theorem Nat.xor_ne_zero {n : ℕ} {m : ℕ} : n ^^^ m ≠ 0 ↔ n ≠ m

theorem Nat.xor_trichotomy {a : ℕ} {b : ℕ} {c : ℕ} (h : a ≠ b ^^^ c) : b ^^^ c < a ∨ a ^^^ c < b ∨ a ^^^ b < c

theorem Nat.lt_xor_cases {a : ℕ} {b : ℕ} {c : ℕ} (h : a < b ^^^ c) : a ^^^ c < b ∨ a ^^^ b < c

@[simp]

theorem Nat.bit_lt_two_pow_succ_iff {b : Bool} {x : ℕ} {n : ℕ} : Nat.bit b x < 2 ^ (n + 1) ↔ x < 2 ^ n

theorem Nat.bitwise_lt {f : Bool → Bool → Bool} {x : ℕ} {y : ℕ} {n : ℕ} (hx : x < 2 ^ n) (hy : y < 2 ^ n) : Nat.bitwise f x y < 2 ^ n

If x and y fit within n bits, then the result of any bitwise operation on x and y also fits within n bits

theorem Nat.shiftLeft_lt {x : ℕ} {n : ℕ} {m : ℕ} (h : x < 2 ^ n) : x <<< m < 2 ^ (n + m)

theorem Nat.append_lt {x : ℕ} {y : ℕ} {n : ℕ} {m : ℕ} (hx : x < 2 ^ n) (hy : y < 2 ^ m) : y <<< n ||| x < 2 ^ (n + m)

Note that the LHS is the expression used within Std.BitVec.append, hence the name.