Bitwise operations on natural numbers #

THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.

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 lxor, which are defined in core.

Main results #

eq_of_test_bit_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_test_bit: 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

source

@[simp]

theorem nat.bit_ff :

nat.bit bool.ff = bit0

source

@[simp]

theorem nat.bit_tt :

nat.bit bool.tt = bit1

source

@[simp]

theorem nat.bit_eq_zero {n : ℕ} {b : bool} :

nat.bit b n = 0 ↔ n = 0 ∧ b = bool.ff

source

theorem nat.zero_of_test_bit_eq_ff {n : ℕ} (h : ∀ (i : ℕ), n.test_bit i = bool.ff) :

n = 0

source

@[simp]

theorem nat.zero_test_bit (i : ℕ) :

0.test_bit i = bool.ff

source

theorem nat.test_bit_eq_inth (n i : ℕ) :

n.test_bit i = n.bits.inth i

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

source

theorem nat.eq_of_test_bit_eq {n m : ℕ} (h : ∀ (i : ℕ), n.test_bit i = m.test_bit i) :

n = m

Bitwise extensionality: Two numbers agree if they agree at every bit position.

source

theorem nat.exists_most_significant_bit {n : ℕ} (h : n ≠ 0) :

∃ (i : ℕ), n.test_bit i = bool.tt ∧ ∀ (j : ℕ), i < j → n.test_bit j = bool.ff

source

theorem nat.lt_of_test_bit {n m : ℕ} (i : ℕ) (hn : n.test_bit i = bool.ff) (hm : m.test_bit i = bool.tt) (hnm : ∀ (j : ℕ), i < j → n.test_bit j = m.test_bit j) :

n < m

source

@[simp]

theorem nat.test_bit_two_pow_self (n : ℕ) :

(2 ^ n).test_bit n = bool.tt

source

theorem nat.test_bit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) :

(2 ^ n).test_bit m = bool.ff

source

theorem nat.test_bit_two_pow (n m : ℕ) :

(2 ^ n).test_bit m = decidable.to_bool (n = m)

source

theorem nat.bitwise_comm {f : bool → bool → bool} (hf : ∀ (b b' : bool), f b b' = f b' b) (hf' : f bool.ff bool.ff = bool.ff) (n m : ℕ) :

nat.bitwise f n m = nat.bitwise f m n

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

source

theorem nat.lor_comm (n m : ℕ) :

n.lor m = m.lor n

source

theorem nat.land_comm (n m : ℕ) :

n.land m = m.land n

source

theorem nat.lxor_comm (n m : ℕ) :

n.lxor m = m.lxor n

source

@[simp]

theorem nat.zero_lxor (n : ℕ) :

0.lxor n = n

source

@[simp]

theorem nat.lxor_zero (n : ℕ) :

n.lxor 0 = n

source

@[simp]

theorem nat.zero_land (n : ℕ) :

0.land n = 0

source

@[simp]

theorem nat.land_zero (n : ℕ) :

n.land 0 = 0

source

@[simp]

theorem nat.zero_lor (n : ℕ) :

0.lor n = n

source

@[simp]

theorem nat.lor_zero (n : ℕ) :

n.lor 0 = n

source

meta def nat.bitwise_assoc_tac :

tactic unit

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.

source

theorem nat.lxor_assoc (n m k : ℕ) :

(n.lxor m).lxor k = n.lxor (m.lxor k)

source

theorem nat.land_assoc (n m k : ℕ) :

(n.land m).land k = n.land (m.land k)

source

theorem nat.lor_assoc (n m k : ℕ) :

(n.lor m).lor k = n.lor (m.lor k)

source

@[simp]

theorem nat.lxor_self (n : ℕ) :