mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -169,7 +169,7 @@ theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = f
   · rw [Nat.div_eq_of_lt, bodd_zero]
     exact pow_lt_pow_right one_lt_two hm
   · rw [pow_div hm.le zero_lt_two, ← tsub_add_cancel_of_le (succ_le_of_lt <| tsub_pos_of_lt hm)]
-    simp [pow_succ]
+    simp [pow_succ']
 #align nat.test_bit_two_pow_of_ne Nat.testBit_two_pow_of_ne
 -/
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -288,11 +288,10 @@ theorem xor_self (n : ℕ) : xor n n = 0 :=
 #align nat.lxor_self Nat.xor_self
 -/
 
-#print Nat.lxor_cancel_right /-
+#print Nat.xor_cancel_right /-
 -- These lemmas match `mul_inv_cancel_right` and `mul_inv_cancel_left`.
-theorem lxor_cancel_right (n m : ℕ) : xor (xor m n) n = m := by
-  rw [lxor_assoc, lxor_self, lxor_zero]
-#align nat.lxor_cancel_right Nat.lxor_cancel_right
+theorem xor_cancel_right (n m : ℕ) : xor (xor m n) n = m := by rw [lxor_assoc, lxor_self, lxor_zero]
+#align nat.lxor_cancel_right Nat.xor_cancel_right
 -/
 
 #print Nat.xor_cancel_left /-

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -97,10 +97,10 @@ theorem testBit_eq_inth (n i : ℕ) : n.testBit i = n.bits.getI i :=
 theorem eq_of_testBit_eq {n m : ℕ} (h : ∀ i, testBit n i = testBit m i) : n = m :=
   by
   induction' n using Nat.binaryRec with b n hn generalizing m
-  · simp only [zero_test_bit] at h 
+  · simp only [zero_test_bit] at h
     exact (zero_of_test_bit_eq_ff fun i => (h i).symm).symm
   induction' m using Nat.binaryRec with b' m hm
-  · simp only [zero_test_bit] at h 
+  · simp only [zero_test_bit] at h
     exact zero_of_test_bit_eq_ff h
   suffices h' : n = m
   · rw [h', show b = b' by simpa using h 0]
@@ -133,19 +133,19 @@ theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : tes
   by
   induction' n using Nat.binaryRec with b n hn' generalizing i m
   · contrapose! hm
-    rw [le_zero_iff] at hm 
+    rw [le_zero_iff] at hm
     simp [hm]
   induction' m using Nat.binaryRec with b' m hm' generalizing i
   · exact False.elim (Bool.false_ne_true ((zero_test_bit i).symm.trans hm))
   by_cases hi : i = 0
   · subst hi
-    simp only [test_bit_zero] at hn hm 
+    simp only [test_bit_zero] at hn hm
     have : n = m :=
       eq_of_test_bit_eq fun i => by convert hnm (i + 1) (by decide) using 1 <;> rw [test_bit_succ]
     rw [hn, hm, this, bit_ff, bit_tt, bit0_val, bit1_val]
     exact lt_add_one _
   · obtain ⟨i', rfl⟩ := exists_eq_succ_of_ne_zero hi
-    simp only [test_bit_succ] at hn hm 
+    simp only [test_bit_succ] at hn hm
     have :=
       hn' _ hn hm fun j hj => by convert hnm j.succ (succ_lt_succ hj) using 1 <;> rw [test_bit_succ]
     cases b <;> cases b' <;>

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -167,7 +167,7 @@ theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = f
   rw [test_bit, shiftr_eq_div_pow]
   cases' hm.lt_or_lt with hm hm
   · rw [Nat.div_eq_of_lt, bodd_zero]
-    exact Nat.pow_lt_pow_of_lt_right one_lt_two hm
+    exact pow_lt_pow_right one_lt_two hm
   · rw [pow_div hm.le zero_lt_two, ← tsub_add_cancel_of_le (succ_le_of_lt <| tsub_pos_of_lt hm)]
     simp [pow_succ]
 #align nat.test_bit_two_pow_of_ne Nat.testBit_two_pow_of_ne

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -226,28 +226,28 @@ theorem xor_zero (n : ℕ) : xor n 0 = n := by simp [lxor]
 #align nat.lxor_zero Nat.xor_zero
 -/
 
-#print Nat.zero_land /-
+#print Nat.zero_and /-
 @[simp]
-theorem zero_land (n : ℕ) : land 0 n = 0 := by simp [land]
-#align nat.zero_land Nat.zero_land
+theorem zero_and (n : ℕ) : land 0 n = 0 := by simp [land]
+#align nat.zero_land Nat.zero_and
 -/
 
-#print Nat.land_zero /-
+#print Nat.and_zero /-
 @[simp]
-theorem land_zero (n : ℕ) : land n 0 = 0 := by simp [land]
-#align nat.land_zero Nat.land_zero
+theorem and_zero (n : ℕ) : land n 0 = 0 := by simp [land]
+#align nat.land_zero Nat.and_zero
 -/
 
-#print Nat.zero_lor /-
+#print Nat.zero_or /-
 @[simp]
-theorem zero_lor (n : ℕ) : lor 0 n = n := by simp [lor]
-#align nat.zero_lor Nat.zero_lor
+theorem zero_or (n : ℕ) : lor 0 n = n := by simp [lor]
+#align nat.zero_lor Nat.zero_or
 -/
 
-#print Nat.lor_zero /-
+#print Nat.or_zero /-
 @[simp]
-theorem lor_zero (n : ℕ) : lor n 0 = n := by simp [lor]
-#align nat.lor_zero Nat.lor_zero
+theorem or_zero (n : ℕ) : lor n 0 = n := by simp [lor]
+#align nat.lor_zero Nat.or_zero
 -/
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:337:4: warning: unsupported (TODO): `[tacs] -/

mathlib commit https://github.com/leanprover-community/mathlib/commit/b1abe23ae96fef89ad30d9f4362c307f72a55010

@@ -166,7 +166,7 @@ theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = f
   by
   rw [test_bit, shiftr_eq_div_pow]
   cases' hm.lt_or_lt with hm hm
-  · rw [Nat.div_eq_zero, bodd_zero]
+  · rw [Nat.div_eq_of_lt, bodd_zero]
     exact Nat.pow_lt_pow_of_lt_right one_lt_two hm
   · rw [pow_div hm.le zero_lt_two, ← tsub_add_cancel_of_le (succ_le_of_lt <| tsub_pos_of_lt hm)]
     simp [pow_succ]
@@ -184,70 +184,70 @@ theorem testBit_two_pow (n m : ℕ) : testBit (2 ^ n) m = (n = m) :=
 #align nat.test_bit_two_pow Nat.testBit_two_pow
 -/
 
-#print Nat.bitwise'_comm /-
+#print Nat.bitwise_comm /-
 /-- If `f` is a commutative operation on bools such that `f ff ff = ff`, then `bitwise f` is also
     commutative. -/
-theorem bitwise'_comm {f : Bool → Bool → Bool} (hf : ∀ b b', f b b' = f b' b)
-    (hf' : f false false = false) (n m : ℕ) : bitwise' f n m = bitwise' f m n :=
-  suffices bitwise' f = swap (bitwise' f) by conv_lhs => rw [this]
+theorem bitwise_comm {f : Bool → Bool → Bool} (hf : ∀ b b', f b b' = f b' b)
+    (hf' : f false false = false) (n m : ℕ) : bitwise f n m = bitwise f m n :=
+  suffices bitwise f = swap (bitwise f) by conv_lhs => rw [this]
   calc
-    bitwise' f = bitwise' (swap f) := congr_arg _ <| funext fun _ => funext <| hf _
-    _ = swap (bitwise' f) := bitwise'_swap hf'
-#align nat.bitwise_comm Nat.bitwise'_comm
+    bitwise f = bitwise (swap f) := congr_arg _ <| funext fun _ => funext <| hf _
+    _ = swap (bitwise f) := bitwise_swap hf'
+#align nat.bitwise_comm Nat.bitwise_comm
 -/
 
-#print Nat.lor'_comm /-
-theorem lor'_comm (n m : ℕ) : lor' n m = lor' m n :=
-  bitwise'_comm Bool.or_comm rfl n m
-#align nat.lor_comm Nat.lor'_comm
+#print Nat.lor_comm /-
+theorem lor_comm (n m : ℕ) : lor n m = lor m n :=
+  bitwise_comm Bool.or_comm rfl n m
+#align nat.lor_comm Nat.lor_comm
 -/
 
-#print Nat.land'_comm /-
-theorem land'_comm (n m : ℕ) : land' n m = land' m n :=
-  bitwise'_comm Bool.and_comm rfl n m
-#align nat.land_comm Nat.land'_comm
+#print Nat.land_comm /-
+theorem land_comm (n m : ℕ) : land n m = land m n :=
+  bitwise_comm Bool.and_comm rfl n m
+#align nat.land_comm Nat.land_comm
 -/
 
-#print Nat.lxor'_comm /-
-theorem lxor'_comm (n m : ℕ) : lxor' n m = lxor' m n :=
-  bitwise'_comm Bool.xor_comm rfl n m
-#align nat.lxor_comm Nat.lxor'_comm
+#print Nat.xor_comm /-
+theorem xor_comm (n m : ℕ) : xor n m = xor m n :=
+  bitwise_comm Bool.xor_comm rfl n m
+#align nat.lxor_comm Nat.xor_comm
 -/
 
-#print Nat.zero_lxor' /-
+#print Nat.zero_xor /-
 @[simp]
-theorem zero_lxor' (n : ℕ) : lxor' 0 n = n := by simp [lxor]
-#align nat.zero_lxor Nat.zero_lxor'
+theorem zero_xor (n : ℕ) : xor 0 n = n := by simp [lxor]
+#align nat.zero_lxor Nat.zero_xor
 -/
 
-#print Nat.lxor'_zero /-
+#print Nat.xor_zero /-
 @[simp]
-theorem lxor'_zero (n : ℕ) : lxor' n 0 = n := by simp [lxor]
-#align nat.lxor_zero Nat.lxor'_zero
+theorem xor_zero (n : ℕ) : xor n 0 = n := by simp [lxor]
+#align nat.lxor_zero Nat.xor_zero
 -/
 
-#print Nat.zero_land' /-
+#print Nat.zero_land /-
 @[simp]
-theorem zero_land' (n : ℕ) : land' 0 n = 0 := by simp [land]
-#align nat.zero_land Nat.zero_land'
+theorem zero_land (n : ℕ) : land 0 n = 0 := by simp [land]
+#align nat.zero_land Nat.zero_land
 -/
 
-#print Nat.land'_zero /-
+#print Nat.land_zero /-
 @[simp]
-theorem land'_zero (n : ℕ) : land' n 0 = 0 := by simp [land]
-#align nat.land_zero Nat.land'_zero
+theorem land_zero (n : ℕ) : land n 0 = 0 := by simp [land]
+#align nat.land_zero Nat.land_zero
 -/
 
-#print Nat.zero_lor' /-
+#print Nat.zero_lor /-
 @[simp]
-theorem zero_lor' (n : ℕ) : lor' 0 n = n := by simp [lor]
-#align nat.zero_lor Nat.zero_lor'
+theorem zero_lor (n : ℕ) : lor 0 n = n := by simp [lor]
+#align nat.zero_lor Nat.zero_lor
 -/
 
-#print Nat.lor'_zero /-
+#print Nat.lor_zero /-
 @[simp]
-theorem lor'_zero (n : ℕ) : lor' n 0 = n := by simp [lor]
-#align nat.lor_zero Nat.lor'_zero
+theorem lor_zero (n : ℕ) : lor n 0 = n := by simp [lor]
+#align nat.lor_zero Nat.lor_zero
 -/
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:337:4: warning: unsupported (TODO): `[tacs] -/
@@ -258,92 +258,90 @@ unsafe def bitwise_assoc_tac : tactic Unit :=
 #align nat.bitwise_assoc_tac nat.bitwise_assoc_tac
 
 /- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:69:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
-#print Nat.lxor'_assoc /-
-theorem lxor'_assoc (n m k : ℕ) : lxor' (lxor' n m) k = lxor' n (lxor' m k) := by
+#print Nat.xor_assoc /-
+theorem xor_assoc (n m k : ℕ) : xor (xor n m) k = xor n (xor m k) := by
   run_tac
     bitwise_assoc_tac
-#align nat.lxor_assoc Nat.lxor'_assoc
+#align nat.lxor_assoc Nat.xor_assoc
 -/
 
 /- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:69:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
-#print Nat.land'_assoc /-
-theorem land'_assoc (n m k : ℕ) : land' (land' n m) k = land' n (land' m k) := by
+#print Nat.land_assoc /-
+theorem land_assoc (n m k : ℕ) : land (land n m) k = land n (land m k) := by
   run_tac
     bitwise_assoc_tac
-#align nat.land_assoc Nat.land'_assoc
+#align nat.land_assoc Nat.land_assoc
 -/
 
 /- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:69:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
-#print Nat.lor'_assoc /-
-theorem lor'_assoc (n m k : ℕ) : lor' (lor' n m) k = lor' n (lor' m k) := by
+#print Nat.lor_assoc /-
+theorem lor_assoc (n m k : ℕ) : lor (lor n m) k = lor n (lor m k) := by
   run_tac
     bitwise_assoc_tac
-#align nat.lor_assoc Nat.lor'_assoc
+#align nat.lor_assoc Nat.lor_assoc
 -/
 
-#print Nat.lxor'_self /-
+#print Nat.xor_self /-
 @[simp]
-theorem lxor'_self (n : ℕ) : lxor' n n = 0 :=
+theorem xor_self (n : ℕ) : xor n n = 0 :=
   zero_of_testBit_eq_false fun i => by simp
-#align nat.lxor_self Nat.lxor'_self
+#align nat.lxor_self Nat.xor_self
 -/
 
 #print Nat.lxor_cancel_right /-
 -- These lemmas match `mul_inv_cancel_right` and `mul_inv_cancel_left`.
-theorem lxor_cancel_right (n m : ℕ) : lxor' (lxor' m n) n = m := by
+theorem lxor_cancel_right (n m : ℕ) : xor (xor m n) n = m := by
   rw [lxor_assoc, lxor_self, lxor_zero]
 #align nat.lxor_cancel_right Nat.lxor_cancel_right
 -/
 
-#print Nat.lxor'_cancel_left /-
-theorem lxor'_cancel_left (n m : ℕ) : lxor' n (lxor' n m) = m := by
+#print Nat.xor_cancel_left /-
+theorem xor_cancel_left (n m : ℕ) : xor n (xor n m) = m := by
   rw [← lxor_assoc, lxor_self, zero_lxor]
-#align nat.lxor_cancel_left Nat.lxor'_cancel_left
+#align nat.lxor_cancel_left Nat.xor_cancel_left
 -/
 
-#print Nat.lxor'_right_injective /-
-theorem lxor'_right_injective {n : ℕ} : Function.Injective (lxor' n) := fun m m' h => by
+#print Nat.xor_right_injective /-
+theorem xor_right_injective {n : ℕ} : Function.Injective (xor n) := fun m m' h => by
   rw [← lxor_cancel_left n m, ← lxor_cancel_left n m', h]
-#align nat.lxor_right_injective Nat.lxor'_right_injective
+#align nat.lxor_right_injective Nat.xor_right_injective
 -/
 
-#print Nat.lxor'_left_injective /-
-theorem lxor'_left_injective {n : ℕ} : Function.Injective fun m => lxor' m n :=
-  fun m m' (h : lxor' m n = lxor' m' n) => by
-  rw [← lxor_cancel_right n m, ← lxor_cancel_right n m', h]
-#align nat.lxor_left_injective Nat.lxor'_left_injective
+#print Nat.xor_left_injective /-
+theorem xor_left_injective {n : ℕ} : Function.Injective fun m => xor m n :=
+  fun m m' (h : xor m n = xor m' n) => by rw [← lxor_cancel_right n m, ← lxor_cancel_right n m', h]
+#align nat.lxor_left_injective Nat.xor_left_injective
 -/
 
-#print Nat.lxor'_right_inj /-
+#print Nat.xor_right_inj /-
 @[simp]
-theorem lxor'_right_inj {n m m' : ℕ} : lxor' n m = lxor' n m' ↔ m = m' :=
-  lxor'_right_injective.eq_iff
-#align nat.lxor_right_inj Nat.lxor'_right_inj
+theorem xor_right_inj {n m m' : ℕ} : xor n m = xor n m' ↔ m = m' :=
+  xor_right_injective.eq_iff
+#align nat.lxor_right_inj Nat.xor_right_inj
 -/
 
-#print Nat.lxor'_left_inj /-
+#print Nat.xor_left_inj /-
 @[simp]
-theorem lxor'_left_inj {n m m' : ℕ} : lxor' m n = lxor' m' n ↔ m = m' :=
-  lxor'_left_injective.eq_iff
-#align nat.lxor_left_inj Nat.lxor'_left_inj
+theorem xor_left_inj {n m m' : ℕ} : xor m n = xor m' n ↔ m = m' :=
+  xor_left_injective.eq_iff
+#align nat.lxor_left_inj Nat.xor_left_inj
 -/
 
-#print Nat.lxor'_eq_zero /-
+#print Nat.xor_eq_zero /-
 @[simp]
-theorem lxor'_eq_zero {n m : ℕ} : lxor' n m = 0 ↔ n = m := by
+theorem xor_eq_zero {n m : ℕ} : xor n m = 0 ↔ n = m := by
   rw [← lxor_self n, lxor_right_inj, eq_comm]
-#align nat.lxor_eq_zero Nat.lxor'_eq_zero
+#align nat.lxor_eq_zero Nat.xor_eq_zero
 -/
 
-#print Nat.lxor'_ne_zero /-
-theorem lxor'_ne_zero {n m : ℕ} : lxor' n m ≠ 0 ↔ n ≠ m :=
-  lxor'_eq_zero.Not
-#align nat.lxor_ne_zero Nat.lxor'_ne_zero
+#print Nat.xor_ne_zero /-
+theorem xor_ne_zero {n m : ℕ} : xor n m ≠ 0 ↔ n ≠ m :=
+  xor_eq_zero.Not
+#align nat.lxor_ne_zero Nat.xor_ne_zero
 -/
 
-#print Nat.lxor'_trichotomy /-
-theorem lxor'_trichotomy {a b c : ℕ} (h : a ≠ lxor' b c) :
-    lxor' b c < a ∨ lxor' a c < b ∨ lxor' a b < c :=
+#print Nat.xor_trichotomy /-
+theorem xor_trichotomy {a b c : ℕ} (h : a ≠ xor b c) : xor b c < a ∨ xor a c < b ∨ xor a b < c :=
   by
   set v := lxor a (lxor b c) with hv
   -- The xor of any two of `a`, `b`, `c` is the xor of `v` and the third.
@@ -372,13 +370,13 @@ theorem lxor'_trichotomy {a b c : ℕ} (h : a ≠ lxor' b c) :
       rcases this with (h | h | h) <;>
       [· left; rw [hbc]; · right; left; rw [hac]; · right; right; rw [hab]] <;>
     exact lt_of_test_bit i (by simp [h, hi]) h fun j hj => by simp [hi' _ hj]
-#align nat.lxor_trichotomy Nat.lxor'_trichotomy
+#align nat.lxor_trichotomy Nat.xor_trichotomy
 -/
 
-#print Nat.lt_lxor'_cases /-
-theorem lt_lxor'_cases {a b c : ℕ} (h : a < lxor' b c) : lxor' a c < b ∨ lxor' a b < c :=
-  (or_iff_right fun h' => (h.asymm h').elim).1 <| lxor'_trichotomy h.Ne
-#align nat.lt_lxor_cases Nat.lt_lxor'_cases
+#print Nat.lt_xor_cases /-
+theorem lt_xor_cases {a b c : ℕ} (h : a < xor b c) : xor a c < b ∨ xor a b < c :=
+  (or_iff_right fun h' => (h.asymm h').elim).1 <| xor_trichotomy h.Ne
+#align nat.lt_lxor_cases Nat.lt_xor_cases
 -/
 
 end Nat

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

@@ -3,8 +3,8 @@ Copyright (c) 2020 Markus Himmel. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Markus Himmel
 -/
-import Mathbin.Data.List.Basic
-import Mathbin.Data.Nat.Bits
+import Data.List.Basic
+import Data.Nat.Bits
 import Mathbin.Tactic.Linarith.Default
 
 #align_import data.nat.bitwise from "leanprover-community/mathlib"@"be24ec5de6701447e5df5ca75400ffee19d65659"
@@ -250,7 +250,7 @@ theorem lor'_zero (n : ℕ) : lor' n 0 = n := by simp [lor]
 #align nat.lor_zero Nat.lor'_zero
 -/
 
-/- ./././Mathport/Syntax/Translate/Expr.lean:336:4: warning: unsupported (TODO): `[tacs] -/
+/- ./././Mathport/Syntax/Translate/Expr.lean:337:4: warning: unsupported (TODO): `[tacs] -/
 /-- 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. -/
 unsafe def bitwise_assoc_tac : tactic Unit :=

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

@@ -2,16 +2,13 @@
 Copyright (c) 2020 Markus Himmel. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Markus Himmel
-
-! This file was ported from Lean 3 source module data.nat.bitwise
-! leanprover-community/mathlib commit be24ec5de6701447e5df5ca75400ffee19d65659
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.List.Basic
 import Mathbin.Data.Nat.Bits
 import Mathbin.Tactic.Linarith.Default
 
+#align_import data.nat.bitwise from "leanprover-community/mathlib"@"be24ec5de6701447e5df5ca75400ffee19d65659"
+
 /-!
 # Bitwise operations on natural numbers
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

@@ -176,6 +176,7 @@ theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = f
 #align nat.test_bit_two_pow_of_ne Nat.testBit_two_pow_of_ne
 -/
 
+#print Nat.testBit_two_pow /-
 theorem testBit_two_pow (n m : ℕ) : testBit (2 ^ n) m = (n = m) :=
   by
   by_cases n = m
@@ -184,6 +185,7 @@ theorem testBit_two_pow (n m : ℕ) : testBit (2 ^ n) m = (n = m) :=
   · rw [test_bit_two_pow_of_ne h]
     simp [h]
 #align nat.test_bit_two_pow Nat.testBit_two_pow
+-/
 
 #print Nat.bitwise'_comm /-
 /-- If `f` is a commutative operation on bools such that `f ff ff = ff`, then `bitwise f` is also

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

@@ -194,7 +194,6 @@ theorem bitwise'_comm {f : Bool → Bool → Bool} (hf : ∀ b b', f b b' = f b'
   calc
     bitwise' f = bitwise' (swap f) := congr_arg _ <| funext fun _ => funext <| hf _
     _ = swap (bitwise' f) := bitwise'_swap hf'
-    
 #align nat.bitwise_comm Nat.bitwise'_comm
 -/
 
@@ -252,7 +251,7 @@ theorem lor'_zero (n : ℕ) : lor' n 0 = n := by simp [lor]
 #align nat.lor_zero Nat.lor'_zero
 -/
 
-/- ./././Mathport/Syntax/Translate/Expr.lean:330:4: warning: unsupported (TODO): `[tacs] -/
+/- ./././Mathport/Syntax/Translate/Expr.lean:336:4: warning: unsupported (TODO): `[tacs] -/
 /-- 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. -/
 unsafe def bitwise_assoc_tac : tactic Unit :=

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

@@ -100,10 +100,10 @@ theorem testBit_eq_inth (n i : ℕ) : n.testBit i = n.bits.getI i :=
 theorem eq_of_testBit_eq {n m : ℕ} (h : ∀ i, testBit n i = testBit m i) : n = m :=
   by
   induction' n using Nat.binaryRec with b n hn generalizing m
-  · simp only [zero_test_bit] at h
+  · simp only [zero_test_bit] at h 
     exact (zero_of_test_bit_eq_ff fun i => (h i).symm).symm
   induction' m using Nat.binaryRec with b' m hm
-  · simp only [zero_test_bit] at h
+  · simp only [zero_test_bit] at h 
     exact zero_of_test_bit_eq_ff h
   suffices h' : n = m
   · rw [h', show b = b' by simpa using h 0]
@@ -136,19 +136,19 @@ theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : tes
   by
   induction' n using Nat.binaryRec with b n hn' generalizing i m
   · contrapose! hm
-    rw [le_zero_iff] at hm
+    rw [le_zero_iff] at hm 
     simp [hm]
   induction' m using Nat.binaryRec with b' m hm' generalizing i
   · exact False.elim (Bool.false_ne_true ((zero_test_bit i).symm.trans hm))
   by_cases hi : i = 0
   · subst hi
-    simp only [test_bit_zero] at hn hm
+    simp only [test_bit_zero] at hn hm 
     have : n = m :=
       eq_of_test_bit_eq fun i => by convert hnm (i + 1) (by decide) using 1 <;> rw [test_bit_succ]
     rw [hn, hm, this, bit_ff, bit_tt, bit0_val, bit1_val]
     exact lt_add_one _
   · obtain ⟨i', rfl⟩ := exists_eq_succ_of_ne_zero hi
-    simp only [test_bit_succ] at hn hm
+    simp only [test_bit_succ] at hn hm 
     have :=
       hn' _ hn hm fun j hj => by convert hnm j.succ (succ_lt_succ hj) using 1 <;> rw [test_bit_succ]
     cases b <;> cases b' <;>
@@ -367,12 +367,12 @@ theorem lxor'_trichotomy {a b c : ℕ} (h : a ≠ lxor' b c) :
   have : test_bit a i = tt ∨ test_bit b i = tt ∨ test_bit c i = tt :=
     by
     contrapose! hi
-    simp only [Bool.eq_false_eq_not_eq_true, Ne, test_bit_lxor] at hi⊢
+    simp only [Bool.eq_false_eq_not_eq_true, Ne, test_bit_lxor] at hi ⊢
     rw [hi.1, hi.2.1, hi.2.2, Bool.xor_false, Bool.xor_false]
   -- If, say, `a` has a one bit at position `i`, then `a xor v` has a zero bit at position `i`, but
       -- the same bits as `a` in positions greater than `j`, so `a xor v < a`.
       rcases this with (h | h | h) <;>
-      [· left; rw [hbc];· right; left; rw [hac];· right; right; rw [hab]] <;>
+      [· left; rw [hbc]; · right; left; rw [hac]; · right; right; rw [hab]] <;>
     exact lt_of_test_bit i (by simp [h, hi]) h fun j hj => by simp [hi' _ hj]
 #align nat.lxor_trichotomy Nat.lxor'_trichotomy
 -/

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

@@ -176,12 +176,6 @@ theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = f
 #align nat.test_bit_two_pow_of_ne Nat.testBit_two_pow_of_ne
 -/
 
-/- warning: nat.test_bit_two_pow -> Nat.testBit_two_pow is a dubious translation:
-lean 3 declaration is
-  forall (n : Nat) (m : Nat), Eq.{1} Bool (Nat.testBit (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) n) m) (Decidable.decide (Eq.{1} Nat n m) (Nat.decidableEq n m))
-but is expected to have type
-  forall (n : Nat) (m : Nat), Eq.{1} Prop (Eq.{1} Bool (Nat.testBit (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) n) m) Bool.true) (Eq.{1} Nat n m)
-Case conversion may be inaccurate. Consider using '#align nat.test_bit_two_pow Nat.testBit_two_powₓ'. -/
 theorem testBit_two_pow (n m : ℕ) : testBit (2 ^ n) m = (n = m) :=
   by
   by_cases n = m

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

@@ -119,9 +119,7 @@ theorem exists_most_significant_bit {n : ℕ} (h : n ≠ 0) :
   · exact False.elim (h rfl)
   by_cases h' : n = 0
   · subst h'
-    rw [show b = tt by
-        revert h
-        cases b <;> simp]
+    rw [show b = tt by revert h; cases b <;> simp]
     refine' ⟨0, ⟨by rw [test_bit_zero], fun j hj => _⟩⟩
     obtain ⟨j', rfl⟩ := exists_eq_succ_of_ne_zero (ne_of_gt hj)
     rw [test_bit_succ, zero_test_bit]
@@ -357,8 +355,7 @@ theorem lxor'_trichotomy {a b c : ℕ} (h : a ≠ lxor' b c) :
   by
   set v := lxor a (lxor b c) with hv
   -- The xor of any two of `a`, `b`, `c` is the xor of `v` and the third.
-  have hab : lxor a b = lxor c v := by
-    rw [hv]
+  have hab : lxor a b = lxor c v := by rw [hv];
     conv_rhs =>
       rw [lxor_comm]
       simp [lxor_assoc]
@@ -381,15 +378,7 @@ theorem lxor'_trichotomy {a b c : ℕ} (h : a ≠ lxor' b c) :
   -- If, say, `a` has a one bit at position `i`, then `a xor v` has a zero bit at position `i`, but
       -- the same bits as `a` in positions greater than `j`, so `a xor v < a`.
       rcases this with (h | h | h) <;>
-      [·
-        left
-        rw [hbc];·
-        right
-        left
-        rw [hac];·
-        right
-        right
-        rw [hab]] <;>
+      [· left; rw [hbc];· right; left; rw [hac];· right; right; rw [hab]] <;>
     exact lt_of_test_bit i (by simp [h, hi]) h fun j hj => by simp [hi' _ hj]
 #align nat.lxor_trichotomy Nat.lxor'_trichotomy
 -/

mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b

@@ -383,11 +383,11 @@ theorem lxor'_trichotomy {a b c : ℕ} (h : a ≠ lxor' b c) :
       rcases this with (h | h | h) <;>
       [·
         left
-        rw [hbc],
-      · right
+        rw [hbc];·
+        right
         left
-        rw [hac],
-      · right
+        rw [hac];·
+        right
         right
         rw [hab]] <;>
     exact lt_of_test_bit i (by simp [h, hi]) h fun j hj => by simp [hi' _ hj]

mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212

@@ -72,7 +72,8 @@ theorem zero_of_testBit_eq_false {n : ℕ} (h : ∀ i, testBit n i = false) : n
   induction' n using Nat.binaryRec with b n hn
   · rfl
   · have : b = ff := by simpa using h 0
-    rw [this, bit_ff, bit0_val, hn fun i => by rw [← h (i + 1), test_bit_succ], mul_zero]
+    rw [this, bit_ff, bit0_val, hn fun i => by rw [← h (i + 1), test_bit_succ],
+      MulZeroClass.mul_zero]
 #align nat.zero_of_test_bit_eq_ff Nat.zero_of_testBit_eq_false
 -/
 
@@ -192,42 +193,30 @@ theorem testBit_two_pow (n m : ℕ) : testBit (2 ^ n) m = (n = m) :=
     simp [h]
 #align nat.test_bit_two_pow Nat.testBit_two_pow
 
-/- warning: nat.bitwise_comm -> Nat.bitwise'_comm is a dubious translation:
-lean 3 declaration is
-  forall {f : Bool -> Bool -> Bool}, (forall (b : Bool) (b' : Bool), Eq.{1} Bool (f b b') (f b' b)) -> (Eq.{1} Bool (f Bool.false Bool.false) Bool.false) -> (forall (n : Nat) (m : Nat), Eq.{1} Nat (Nat.bitwise f n m) (Nat.bitwise f m n))
-but is expected to have type
-  forall {f : Bool -> Bool -> Bool}, (forall (b : Bool) (b' : Bool), Eq.{1} Bool (f b b') (f b' b)) -> (Eq.{1} Bool (f Bool.false Bool.false) Bool.false) -> (forall (n : Nat) (m : Nat), Eq.{1} Nat (Nat.bitwise' f n m) (Nat.bitwise' f m n))
-Case conversion may be inaccurate. Consider using '#align nat.bitwise_comm Nat.bitwise'_commₓ'. -/
+#print Nat.bitwise'_comm /-
 /-- If `f` is a commutative operation on bools such that `f ff ff = ff`, then `bitwise f` is also
     commutative. -/
 theorem bitwise'_comm {f : Bool → Bool → Bool} (hf : ∀ b b', f b b' = f b' b)
-    (hf' : f false false = false) (n m : ℕ) : bitwise f n m = bitwise f m n :=
-  suffices bitwise f = swap (bitwise f) by conv_lhs => rw [this]
+    (hf' : f false false = false) (n m : ℕ) : bitwise' f n m = bitwise' f m n :=
+  suffices bitwise' f = swap (bitwise' f) by conv_lhs => rw [this]
   calc
-    bitwise f = bitwise (swap f) := congr_arg _ <| funext fun _ => funext <| hf _
-    _ = swap (bitwise f) := bitwise'_swap hf'
+    bitwise' f = bitwise' (swap f) := congr_arg _ <| funext fun _ => funext <| hf _
+    _ = swap (bitwise' f) := bitwise'_swap hf'
     
 #align nat.bitwise_comm Nat.bitwise'_comm
+-/
 
-/- warning: nat.lor_comm -> Nat.lor'_comm is a dubious translation:
-lean 3 declaration is
-  forall (n : Nat) (m : Nat), Eq.{1} Nat (Nat.lor n m) (Nat.lor m n)
-but is expected to have type
-  forall (n : Nat) (m : Nat), Eq.{1} Nat (Nat.lor' n m) (Nat.lor' m n)
-Case conversion may be inaccurate. Consider using '#align nat.lor_comm Nat.lor'_commₓ'. -/
-theorem lor'_comm (n m : ℕ) : lor n m = lor m n :=
+#print Nat.lor'_comm /-
+theorem lor'_comm (n m : ℕ) : lor' n m = lor' m n :=
   bitwise'_comm Bool.or_comm rfl n m
 #align nat.lor_comm Nat.lor'_comm
+-/
 
-/- warning: nat.land_comm -> Nat.land'_comm is a dubious translation:
-lean 3 declaration is
-  forall (n : Nat) (m : Nat), Eq.{1} Nat (Nat.land n m) (Nat.land m n)
-but is expected to have type
-  forall (n : Nat) (m : Nat), Eq.{1} Nat (Nat.land' n m) (Nat.land' m n)
-Case conversion may be inaccurate. Consider using '#align nat.land_comm Nat.land'_commₓ'. -/
-theorem land'_comm (n m : ℕ) : land n m = land m n :=
+#print Nat.land'_comm /-
+theorem land'_comm (n m : ℕ) : land' n m = land' m n :=
   bitwise'_comm Bool.and_comm rfl n m
 #align nat.land_comm Nat.land'_comm
+-/
 
 #print Nat.lxor'_comm /-
 theorem lxor'_comm (n m : ℕ) : lxor' n m = lxor' m n :=
@@ -249,35 +238,27 @@ theorem lxor'_zero (n : ℕ) : lxor' n 0 = n := by simp [lxor]
 
 #print Nat.zero_land' /-
 @[simp]
-theorem zero_land' (n : ℕ) : land 0 n = 0 := by simp [land]
+theorem zero_land' (n : ℕ) : land' 0 n = 0 := by simp [land]
 #align nat.zero_land Nat.zero_land'
 -/
 
-/- warning: nat.land_zero -> Nat.land'_zero is a dubious translation:
-lean 3 declaration is
-  forall (n : Nat), Eq.{1} Nat (Nat.land n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))
-but is expected to have type
-  forall (n : Nat), Eq.{1} Nat (Nat.land' n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))
-Case conversion may be inaccurate. Consider using '#align nat.land_zero Nat.land'_zeroₓ'. -/
+#print Nat.land'_zero /-
 @[simp]
-theorem land'_zero (n : ℕ) : land n 0 = 0 := by simp [land]
+theorem land'_zero (n : ℕ) : land' n 0 = 0 := by simp [land]
 #align nat.land_zero Nat.land'_zero
+-/
 
 #print Nat.zero_lor' /-
 @[simp]
-theorem zero_lor' (n : ℕ) : lor 0 n = n := by simp [lor]
+theorem zero_lor' (n : ℕ) : lor' 0 n = n := by simp [lor]
 #align nat.zero_lor Nat.zero_lor'
 -/
 
-/- warning: nat.lor_zero -> Nat.lor'_zero is a dubious translation:
-lean 3 declaration is
-  forall (n : Nat), Eq.{1} Nat (Nat.lor n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) n
-but is expected to have type
-  forall (n : Nat), Eq.{1} Nat (Nat.lor' n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) n
-Case conversion may be inaccurate. Consider using '#align nat.lor_zero Nat.lor'_zeroₓ'. -/
+#print Nat.lor'_zero /-
 @[simp]
-theorem lor'_zero (n : ℕ) : lor n 0 = n := by simp [lor]
+theorem lor'_zero (n : ℕ) : lor' n 0 = n := by simp [lor]
 #align nat.lor_zero Nat.lor'_zero
+-/
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:330:4: warning: unsupported (TODO): `[tacs] -/
 /-- Proving associativity of bitwise operations in general essentially boils down to a huge case
@@ -294,29 +275,21 @@ theorem lxor'_assoc (n m k : ℕ) : lxor' (lxor' n m) k = lxor' n (lxor' m k) :=
 #align nat.lxor_assoc Nat.lxor'_assoc
 -/
 
-/- warning: nat.land_assoc -> Nat.land'_assoc is a dubious translation:
-lean 3 declaration is
-  forall (n : Nat) (m : Nat) (k : Nat), Eq.{1} Nat (Nat.land (Nat.land n m) k) (Nat.land n (Nat.land m k))
-but is expected to have type
-  forall (n : Nat) (m : Nat) (k : Nat), Eq.{1} Nat (Nat.land' (Nat.land' n m) k) (Nat.land' n (Nat.land' m k))
-Case conversion may be inaccurate. Consider using '#align nat.land_assoc Nat.land'_assocₓ'. -/
 /- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:69:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
-theorem land'_assoc (n m k : ℕ) : land (land n m) k = land n (land m k) := by
+#print Nat.land'_assoc /-
+theorem land'_assoc (n m k : ℕ) : land' (land' n m) k = land' n (land' m k) := by
   run_tac
     bitwise_assoc_tac
 #align nat.land_assoc Nat.land'_assoc
+-/
 
-/- warning: nat.lor_assoc -> Nat.lor'_assoc is a dubious translation:
-lean 3 declaration is
-  forall (n : Nat) (m : Nat) (k : Nat), Eq.{1} Nat (Nat.lor (Nat.lor n m) k) (Nat.lor n (Nat.lor m k))
-but is expected to have type
-  forall (n : Nat) (m : Nat) (k : Nat), Eq.{1} Nat (Nat.lor' (Nat.lor' n m) k) (Nat.lor' n (Nat.lor' m k))
-Case conversion may be inaccurate. Consider using '#align nat.lor_assoc Nat.lor'_assocₓ'. -/
 /- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:69:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
-theorem lor'_assoc (n m k : ℕ) : lor (lor n m) k = lor n (lor m k) := by
+#print Nat.lor'_assoc /-
+theorem lor'_assoc (n m k : ℕ) : lor' (lor' n m) k = lor' n (lor' m k) := by
   run_tac
     bitwise_assoc_tac
 #align nat.lor_assoc Nat.lor'_assoc
+-/
 
 #print Nat.lxor'_self /-
 @[simp]

mathlib commit https://github.com/leanprover-community/mathlib/commit/4c586d291f189eecb9d00581aeb3dd998ac34442

@@ -279,14 +279,14 @@ Case conversion may be inaccurate. Consider using '#align nat.lor_zero Nat.lor'_
 theorem lor'_zero (n : ℕ) : lor n 0 = n := by simp [lor]
 #align nat.lor_zero Nat.lor'_zero
 
-/- ./././Mathport/Syntax/Translate/Expr.lean:334:4: warning: unsupported (TODO): `[tacs] -/
+/- ./././Mathport/Syntax/Translate/Expr.lean:330:4: warning: unsupported (TODO): `[tacs] -/
 /-- 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. -/
 unsafe def bitwise_assoc_tac : tactic Unit :=
   sorry
 #align nat.bitwise_assoc_tac nat.bitwise_assoc_tac
 
-/- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:72:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
+/- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:69:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
 #print Nat.lxor'_assoc /-
 theorem lxor'_assoc (n m k : ℕ) : lxor' (lxor' n m) k = lxor' n (lxor' m k) := by
   run_tac
@@ -300,7 +300,7 @@ lean 3 declaration is
 but is expected to have type
   forall (n : Nat) (m : Nat) (k : Nat), Eq.{1} Nat (Nat.land' (Nat.land' n m) k) (Nat.land' n (Nat.land' m k))
 Case conversion may be inaccurate. Consider using '#align nat.land_assoc Nat.land'_assocₓ'. -/
-/- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:72:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
+/- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:69:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
 theorem land'_assoc (n m k : ℕ) : land (land n m) k = land n (land m k) := by
   run_tac
     bitwise_assoc_tac
@@ -312,7 +312,7 @@ lean 3 declaration is
 but is expected to have type
   forall (n : Nat) (m : Nat) (k : Nat), Eq.{1} Nat (Nat.lor' (Nat.lor' n m) k) (Nat.lor' n (Nat.lor' m k))
 Case conversion may be inaccurate. Consider using '#align nat.lor_assoc Nat.lor'_assocₓ'. -/
-/- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:72:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
+/- ./././Mathport/Syntax/Translate/Tactic/Builtin.lean:69:18: unsupported non-interactive tactic nat.bitwise_assoc_tac -/
 theorem lor'_assoc (n m k : ℕ) : lor (lor n m) k = lor n (lor m k) := by
   run_tac
     bitwise_assoc_tac

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

This is a far from a complete success at the PR title, but it makes a fair bit of progress, and then guards this with appropriate assert_not_exists Ring statements.

It also breaks apart the Mathlib.GroupTheory.Subsemigroup.[Center|Centralizer] files, to pull the Set.center and Set.centralizer declarations into their own files not depending on Subsemigroup.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

@@ -5,6 +5,7 @@ Authors: Markus Himmel, Alex Keizer
 -/
 import Mathlib.Data.List.GetD
 import Mathlib.Data.Nat.Bits
+import Mathlib.Algebra.Ring.Nat
 import Mathlib.Order.Basic
 import Mathlib.Tactic.Common
 

Move basic Nat lemmas from Data.Nat.Order.Basic and Data.Nat.Pow to Data.Nat.Defs. Most proofs need adapting, but that's easily solved by replacing the general mathlib lemmas by the new Std Nat-specific lemmas and using omega.

Other changes

• Move the last few lemmas left in Data.Nat.Pow to Algebra.GroupPower.Order
• Move the deprecated aliases from Data.Nat.Pow to Algebra.GroupPower.Order
• Move the bit/bit0/bit1 lemmas from Data.Nat.Order.Basic to Data.Nat.Bits
• Fix some fallout from not importing Data.Nat.Order.Basic anymore
• Add a few Nat-specific lemmas to help fix the fallout (look for nolint simpNF)
• Turn Nat.mul_self_le_mul_self_iff and Nat.mul_self_lt_mul_self_iff around (they were misnamed)
• Make more arguments to Nat.one_lt_pow implicit

@@ -3,9 +3,10 @@ Copyright (c) 2020 Markus Himmel. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Markus Himmel, Alex Keizer
 -/
-import Mathlib.Algebra.GroupPower.Order
 import Mathlib.Data.List.GetD
 import Mathlib.Data.Nat.Bits
+import Mathlib.Order.Basic
+import Mathlib.Tactic.Common
 
 #align_import data.nat.bitwise from "leanprover-community/mathlib"@"6afc9b06856ad973f6a2619e3e8a0a8d537a58f2"
 
@@ -86,7 +87,7 @@ lemma bitwise_bit {f : Bool → Bool → Bool} (h : f false false = false := by
   simp only [bit, ite_apply, bit1, bit0, Bool.cond_eq_ite]
   have h1 x :     (x + x) % 2 = 0 := by rw [← two_mul, mul_comm]; apply mul_mod_left
   have h2 x : (x + x + 1) % 2 = 1 := by rw [← two_mul, add_comm]; apply add_mul_mod_self_left
-  have h3 x :     (x + x) / 2 = x := by rw [← two_mul, mul_comm]; apply mul_div_left _ zero_lt_two
+  have h3 x :     (x + x) / 2 = x := by omega
   have h4 x : (x + x + 1) / 2 = x := by rw [← two_mul, add_comm]; simp [add_mul_div_left]
   cases a <;> cases b <;> simp [h1, h2, h3, h4] <;> split_ifs
     <;> simp_all (config := {decide := true})
@@ -245,7 +246,7 @@ theorem exists_most_significant_bit {n : ℕ} (h : n ≠ 0) :
 theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : testBit m i = true)
     (hnm : ∀ j, i < j → testBit n j = testBit m j) : n < m := by
   induction' n using Nat.binaryRec with b n hn' generalizing i m
-  · rw [pos_iff_ne_zero]
+  · rw [Nat.pos_iff_ne_zero]
     rintro rfl
     simp at hm
   induction' m using Nat.binaryRec with b' m hm' generalizing i
@@ -257,12 +258,12 @@ theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : tes
       eq_of_testBit_eq fun i => by convert hnm (i + 1) (Nat.zero_lt_succ _) using 1
       <;> rw [testBit_bit_succ]
     rw [hn, hm, this, bit_false, bit_true, bit0_val, bit1_val]
-    exact lt_add_one _
+    exact Nat.lt_succ_self _
   · obtain ⟨i', rfl⟩ := exists_eq_succ_of_ne_zero hi
     simp only [testBit_bit_succ] at hn hm
     have := hn' _ hn hm fun j hj => by
       convert hnm j.succ (succ_lt_succ hj) using 1 <;> rw [testBit_bit_succ]
-    have this' : 2 * n < 2 * m := Nat.mul_lt_mul' (le_refl _) this two_pos
+    have this' : 2 * n < 2 * m := Nat.mul_lt_mul' (le_refl _) this Nat.two_pos
     cases b <;> cases b'
     <;> simp only [bit_false, bit_true, bit0_val n, bit1_val n, bit0_val m, bit1_val m]
     · exact this'
@@ -275,7 +276,7 @@ theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : tes
 
 @[simp]
 theorem testBit_two_pow_self (n : ℕ) : testBit (2 ^ n) n = true := by
-  rw [testBit, shiftRight_eq_div_pow, Nat.div_self (pow_pos (α := ℕ) zero_lt_two n)]
+  rw [testBit, shiftRight_eq_div_pow, Nat.div_self (Nat.pow_pos Nat.zero_lt_two)]
   simp
 #align nat.test_bit_two_pow_self Nat.testBit_two_pow_self
 
@@ -284,8 +285,8 @@ theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = f
   cases' hm.lt_or_lt with hm hm
   · rw [Nat.div_eq_of_lt]
     · simp
-    · exact pow_lt_pow_right one_lt_two hm
-  · rw [Nat.pow_div hm.le zero_lt_two, ← tsub_add_cancel_of_le (succ_le_of_lt <| tsub_pos_of_lt hm)]
+    · exact Nat.pow_lt_pow_right Nat.one_lt_two hm
+  · rw [Nat.pow_div hm.le Nat.two_pos, ← Nat.sub_add_cancel (succ_le_of_lt <| Nat.sub_pos_of_lt hm)]
     -- Porting note: XXX why does this make it work?
     rw [(rfl : succ 0 = 1)]
     simp [pow_succ, and_one_is_mod, mul_mod_left]
@@ -459,8 +460,7 @@ theorem lt_xor_cases {a b c : ℕ} (h : a < b ^^^ c) : a ^^^ c < b ∨ a ^^^ b <
 #align nat.lt_lxor_cases Nat.lt_xor_cases
 
 @[simp] theorem bit_lt_two_pow_succ_iff {b x n} : bit b x < 2 ^ (n + 1) ↔ x < 2 ^ n := by
-  rw [pow_succ', ← bit0_eq_two_mul]
-  cases b <;> simp
+  cases b <;> simp [bit0, bit1] <;> omega
 
 /-- If `x` and `y` fit within `n` bits, then the result of any bitwise operation on `x` and `y` also
 fits within `n` bits -/
@@ -480,12 +480,12 @@ theorem bitwise_lt {f x y n} (hx : x < 2 ^ n) (hy : y < 2 ^ n) :
       cases n <;> simp_all
 
 lemma shiftLeft_lt {x n m : ℕ} (h : x < 2 ^ n) : x <<< m < 2 ^ (n + m) := by
-  simp only [pow_add, shiftLeft_eq, mul_lt_mul_right (Nat.two_pow_pos _), h]
+  simp only [Nat.pow_add, shiftLeft_eq, Nat.mul_lt_mul_right (Nat.two_pow_pos _), h]
 
 /-- Note that the LHS is the expression used within `Std.BitVec.append`, hence the name. -/
 lemma append_lt {x y n m} (hx : x < 2 ^ n) (hy : y < 2 ^ m) : y <<< n ||| x < 2 ^ (n + m) := by
   apply bitwise_lt
   · rw [add_comm]; apply shiftLeft_lt hy
-  · apply lt_of_lt_of_le hx <| pow_le_pow_right (le_succ _) (le_add_right _ _)
+  · apply lt_of_lt_of_le hx <| Nat.pow_le_pow_right (le_succ _) (le_add_right _ _)
 
 end Nat

Fix two porting notes (one that should have been a porting note!) while looking at on_goals.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -451,14 +451,7 @@ theorem xor_trichotomy {a b c : ℕ} (h : a ≠ b ^^^ c) :
   on_goal 2 => right; left; rw [hac]
   on_goal 3 => right; right; rw [hab]
   all_goals
-    exact lt_of_testBit i (by
-      -- Porting note: this was originally `simp [h, hi]`
-      rw [Nat.testBit_xor, h, Bool.xor, Bool.true_xor, hi]
-      rfl
-    ) h fun j hj => by
-      -- Porting note: this was originally `simp [hi' _ hj]`
-      rw [Nat.testBit_xor, hi' _ hj, Bool.xor, Bool.xor_false, eq_self_iff_true]
-      trivial
+    exact lt_of_testBit i (by simp [h, hi]) h fun j hj => by simp [hi' _ hj]
 #align nat.lxor_trichotomy Nat.xor_trichotomy
 
 theorem lt_xor_cases {a b c : ℕ} (h : a < b ^^^ c) : a ^^^ c < b ∨ a ^^^ b < c :=

@@ -81,7 +81,9 @@ theorem binaryRec_of_ne_zero {C : Nat → Sort*} (z : C 0) (f : ∀ b n, C n →
 lemma bitwise_bit {f : Bool → Bool → Bool} (h : f false false = false := by rfl) (a m b n) :
     bitwise f (bit a m) (bit b n) = bit (f a b) (bitwise f m n) := by
   conv_lhs => unfold bitwise
-  simp (config := { unfoldPartialApp := true }) only [bit, bit1, bit0, Bool.cond_eq_ite]
+  -- Adaptation note: nightly-2024-03-16: simp was
+  -- simp (config := { unfoldPartialApp := true }) only [bit, bit1, bit0, Bool.cond_eq_ite]
+  simp only [bit, ite_apply, bit1, bit0, Bool.cond_eq_ite]
   have h1 x :     (x + x) % 2 = 0 := by rw [← two_mul, mul_comm]; apply mul_mod_left
   have h2 x : (x + x + 1) % 2 = 1 := by rw [← two_mul, add_comm]; apply add_mul_mod_self_left
   have h3 x :     (x + x) / 2 = x := by rw [← two_mul, mul_comm]; apply mul_div_left _ zero_lt_two
@@ -92,7 +94,10 @@ lemma bitwise_bit {f : Bool → Bool → Bool} (h : f false false = false := by
 
 lemma bit_mod_two (a : Bool) (x : ℕ) :
     bit a x % 2 = if a then 1 else 0 := by
-  simp (config := { unfoldPartialApp := true }) only [bit, bit1, bit0, ← mul_two, Bool.cond_eq_ite]
+  -- Adaptation note: nightly-2024-03-16: simp was
+  -- simp (config := { unfoldPartialApp := true }) only [bit, bit1, bit0, ← mul_two,
+  --   Bool.cond_eq_ite]
+  simp only [bit, ite_apply, bit1, bit0, ← mul_two, Bool.cond_eq_ite]
   split_ifs <;> simp [Nat.add_mod]
 
 @[simp]

as it conflicts with xor_comm in the root namespace. Also protect Nat.xor_assoc in case someone adds xor_assoc.

@@ -3,10 +3,9 @@ Copyright (c) 2020 Markus Himmel. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Markus Himmel, Alex Keizer
 -/
+import Mathlib.Algebra.GroupPower.Order
 import Mathlib.Data.List.GetD
 import Mathlib.Data.Nat.Bits
-import Mathlib.Algebra.GroupPower.Order
-import Mathlib.Tactic.Set
 
 #align_import data.nat.bitwise from "leanprover-community/mathlib"@"6afc9b06856ad973f6a2619e3e8a0a8d537a58f2"
 
@@ -241,9 +240,9 @@ theorem exists_most_significant_bit {n : ℕ} (h : n ≠ 0) :
 theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : testBit m i = true)
     (hnm : ∀ j, i < j → testBit n j = testBit m j) : n < m := by
   induction' n using Nat.binaryRec with b n hn' generalizing i m
-  · contrapose! hm
-    rw [le_zero_iff] at hm
-    simp [hm]
+  · rw [pos_iff_ne_zero]
+    rintro rfl
+    simp at hm
   induction' m using Nat.binaryRec with b' m hm' generalizing i
   · exact False.elim (Bool.false_ne_true ((zero_testBit i).symm.trans hm))
   by_cases hi : i = 0
@@ -325,7 +324,7 @@ theorem land_comm (n m : ℕ) : n &&& m = m &&& n :=
   bitwise_comm Bool.and_comm n m
 #align nat.land_comm Nat.land_comm
 
-theorem xor_comm (n m : ℕ) : n ^^^ m = m ^^^ n :=
+protected lemma xor_comm (n m : ℕ) : n ^^^ m = m ^^^ n :=
   bitwise_comm (Bool.bne_eq_xor ▸ Bool.xor_comm) n m
 #align nat.lxor_comm Nat.xor_comm
 
@@ -366,7 +365,7 @@ macro "bitwise_assoc_tac" : tactic => set_option hygiene false in `(tactic| (
   -- This is necessary because these are simp lemmas in mathlib
   <;> simp [hn, Bool.or_assoc, Bool.and_assoc, Bool.bne_eq_xor]))
 
-theorem xor_assoc (n m k : ℕ) : (n ^^^ m) ^^^ k = n ^^^ (m ^^^ k) := by bitwise_assoc_tac
+protected lemma xor_assoc (n m k : ℕ) : (n ^^^ m) ^^^ k = n ^^^ (m ^^^ k) := by bitwise_assoc_tac
 #align nat.lxor_assoc Nat.xor_assoc
 
 theorem land_assoc (n m k : ℕ) : (n &&& m) &&& k = n &&& (m &&& k) := by bitwise_assoc_tac
@@ -381,12 +380,12 @@ theorem xor_self (n : ℕ) : n ^^^ n = 0 :=
 #align nat.lxor_self Nat.xor_self
 
 -- These lemmas match `mul_inv_cancel_right` and `mul_inv_cancel_left`.
-theorem lxor_cancel_right (n m : ℕ) : (m ^^^ n) ^^^ n = m := by
-  rw [xor_assoc, xor_self, xor_zero]
-#align nat.lxor_cancel_right Nat.lxor_cancel_right
+theorem xor_cancel_right (n m : ℕ) : (m ^^^ n) ^^^ n = m := by
+  rw [Nat.xor_assoc, xor_self, xor_zero]
+#align nat.lxor_cancel_right Nat.xor_cancel_right
 
 theorem xor_cancel_left (n m : ℕ) : n ^^^ (n ^^^ m) = m := by
-  rw [← xor_assoc, xor_self, zero_xor]
+  rw [← Nat.xor_assoc, xor_self, zero_xor]
 #align nat.lxor_cancel_left Nat.xor_cancel_left
 
 theorem xor_right_injective {n : ℕ} : Function.Injective (HXor.hXor n : ℕ → ℕ) := fun m m' h => by
@@ -395,7 +394,7 @@ theorem xor_right_injective {n : ℕ} : Function.Injective (HXor.hXor n : ℕ 
 
 theorem xor_left_injective {n : ℕ} : Function.Injective fun m => m ^^^ n :=
   fun m m' (h : m ^^^ n = m' ^^^ n) => by
-  rw [← lxor_cancel_right n m, ← lxor_cancel_right n m', h]
+  rw [← xor_cancel_right n m, ← xor_cancel_right n m', h]
 #align nat.lxor_left_injective Nat.xor_left_injective
 
 @[simp]
@@ -424,15 +423,15 @@ theorem xor_trichotomy {a b c : ℕ} (h : a ≠ b ^^^ c) :
   have hab : a ^^^ b = c ^^^ v := by
     rw [hv]
     conv_rhs =>
-      rw [xor_comm]
-      simp [xor_assoc]
+      rw [Nat.xor_comm]
+      simp [Nat.xor_assoc]
   have hac : a ^^^ c = b ^^^ v := by
     rw [hv]
     conv_rhs =>
       right
-      rw [← xor_comm]
-    rw [← xor_assoc, ← xor_assoc, xor_self, zero_xor, xor_comm]
-  have hbc : b ^^^ c = a ^^^ v := by simp [hv, ← xor_assoc]
+      rw [← Nat.xor_comm]
+    rw [← Nat.xor_assoc, ← Nat.xor_assoc, xor_self, zero_xor, Nat.xor_comm]
+  have hbc : b ^^^ c = a ^^^ v := by simp [hv, ← Nat.xor_assoc]
   -- If `i` is the position of the most significant bit of `v`, then at least one of `a`, `b`, `c`
   -- has a one bit at position `i`.
   obtain ⟨i, ⟨hi, hi'⟩⟩ := exists_most_significant_bit (xor_ne_zero.2 h)

This PR accompanies #11246, squeezing some non-terminal simps highlighted by the linter until I decided to stop!

@@ -66,7 +66,7 @@ lemma bitwise_of_ne_zero {n m : Nat} (hn : n ≠ 0) (hm : m ≠ 0) :
     bitwise f n m = bit (f (bodd n) (bodd m)) (bitwise f (n / 2) (m / 2)) := by
   conv_lhs => unfold bitwise
   have mod_two_iff_bod x : (x % 2 = 1 : Bool) = bodd x := by
-    simp [mod_two_of_bodd, cond]; cases bodd x <;> rfl
+    simp only [mod_two_of_bodd, cond]; cases bodd x <;> rfl
   simp only [hn, hm, mod_two_iff_bod, ite_false, bit, bit1, bit0, Bool.cond_eq_ite]
   split_ifs <;> rfl
 
@@ -93,7 +93,7 @@ lemma bitwise_bit {f : Bool → Bool → Bool} (h : f false false = false := by
 
 lemma bit_mod_two (a : Bool) (x : ℕ) :
     bit a x % 2 = if a then 1 else 0 := by
-  simp (config := { unfoldPartialApp := true }) [bit, bit0, bit1, Bool.cond_eq_ite, ← mul_two]
+  simp (config := { unfoldPartialApp := true }) only [bit, bit1, bit0, ← mul_two, Bool.cond_eq_ite]
   split_ifs <;> simp [Nat.add_mod]
 
 @[simp]

This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0 branch as we update to intermediate nightlies.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>

@@ -86,7 +86,7 @@ lemma bitwise_bit {f : Bool → Bool → Bool} (h : f false false = false := by
   have h1 x :     (x + x) % 2 = 0 := by rw [← two_mul, mul_comm]; apply mul_mod_left
   have h2 x : (x + x + 1) % 2 = 1 := by rw [← two_mul, add_comm]; apply add_mul_mod_self_left
   have h3 x :     (x + x) / 2 = x := by rw [← two_mul, mul_comm]; apply mul_div_left _ zero_lt_two
-  have h4 x : (x + x + 1) / 2 = x := by rw [← two_mul, add_comm]; simp [add_mul_div_left]; rfl
+  have h4 x : (x + x + 1) / 2 = x := by rw [← two_mul, add_comm]; simp [add_mul_div_left]
   cases a <;> cases b <;> simp [h1, h2, h3, h4] <;> split_ifs
     <;> simp_all (config := {decide := true})
 #align nat.bitwise_bit Nat.bitwise_bit

Classifies by adding issue number (#10745) to porting notes claiming was simp.

@@ -362,7 +362,7 @@ macro "bitwise_assoc_tac" : tactic => set_option hygiene false in `(tactic| (
   induction' m using Nat.binaryRec with b' m hm
   · simp
   induction' k using Nat.binaryRec with b'' k hk
-  -- Porting note: was `simp [hn]`
+  -- porting note (#10745): was `simp [hn]`
   -- This is necessary because these are simp lemmas in mathlib
   <;> simp [hn, Bool.or_assoc, Bool.and_assoc, Bool.bne_eq_xor]))
 

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Tobias Grosser <tobias@grosser.es>

@@ -5,7 +5,7 @@ Authors: Markus Himmel, Alex Keizer
 -/
 import Mathlib.Data.List.GetD
 import Mathlib.Data.Nat.Bits
-import Mathlib.Data.Nat.Pow
+import Mathlib.Algebra.GroupPower.Order
 import Mathlib.Tactic.Set
 
 #align_import data.nat.bitwise from "leanprover-community/mathlib"@"6afc9b06856ad973f6a2619e3e8a0a8d537a58f2"
@@ -281,7 +281,7 @@ theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = f
   · rw [Nat.div_eq_of_lt]
     · simp
     · exact pow_lt_pow_right one_lt_two hm
-  · rw [pow_div hm.le zero_lt_two, ← tsub_add_cancel_of_le (succ_le_of_lt <| tsub_pos_of_lt hm)]
+  · rw [Nat.pow_div hm.le zero_lt_two, ← tsub_add_cancel_of_le (succ_le_of_lt <| tsub_pos_of_lt hm)]
     -- Porting note: XXX why does this make it work?
     rw [(rfl : succ 0 = 1)]
     simp [pow_succ, and_one_is_mod, mul_mod_left]

Splits off some lemmas from the end of this file, reducing the size of what is currently the longest file in mathlib.

@@ -3,7 +3,7 @@ Copyright (c) 2020 Markus Himmel. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Markus Himmel, Alex Keizer
 -/
-import Mathlib.Data.List.Basic
+import Mathlib.Data.List.GetD
 import Mathlib.Data.Nat.Bits
 import Mathlib.Data.Nat.Pow
 import Mathlib.Tactic.Set

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -199,7 +199,7 @@ theorem zero_of_testBit_eq_false {n : ℕ} (h : ∀ i, testBit n i = false) : n
   induction' n using Nat.binaryRec with b n hn
   · rfl
   · have : b = false := by simpa using h 0
-    rw [this, bit_false, bit0_val, hn fun i => by rw [← h (i + 1), testBit_succ], mul_zero]
+    rw [this, bit_false, bit0_val, hn fun i => by rw [← h (i + 1), testBit_bit_succ], mul_zero]
 #align nat.zero_of_test_bit_eq_ff Nat.zero_of_testBit_eq_false
 
 theorem testBit_eq_false_of_lt {n i} (h : n < 2 ^ i) : n.testBit i = false := by
@@ -214,7 +214,7 @@ theorem testBit_eq_inth (n i : ℕ) : n.testBit i = n.bits.getI i := by
       bodd_eq_bits_head, List.getI_zero_eq_headI]
     cases List.headI (bits n) <;> rfl
   conv_lhs => rw [← bit_decomp n]
-  rw [testBit_succ, ih n.div2, div2_bits_eq_tail]
+  rw [testBit_bit_succ, ih n.div2, div2_bits_eq_tail]
   cases n.bits <;> simp
 #align nat.test_bit_eq_inth Nat.testBit_eq_inth
 
@@ -229,13 +229,13 @@ theorem exists_most_significant_bit {n : ℕ} (h : n ≠ 0) :
     rw [show b = true by
         revert h
         cases b <;> simp]
-    refine' ⟨0, ⟨by rw [testBit_zero], fun j hj => _⟩⟩
+    refine' ⟨0, ⟨by rw [testBit_bit_zero], fun j hj => _⟩⟩
     obtain ⟨j', rfl⟩ := exists_eq_succ_of_ne_zero (ne_of_gt hj)
-    rw [testBit_succ, zero_testBit]
+    rw [testBit_bit_succ, zero_testBit]
   · obtain ⟨k, ⟨hk, hk'⟩⟩ := hn h'
-    refine' ⟨k + 1, ⟨by rw [testBit_succ, hk], fun j hj => _⟩⟩
+    refine' ⟨k + 1, ⟨by rw [testBit_bit_succ, hk], fun j hj => _⟩⟩
     obtain ⟨j', rfl⟩ := exists_eq_succ_of_ne_zero (show j ≠ 0 by intro x; subst x; simp at hj)
-    exact (testBit_succ _ _ _).trans (hk' _ (lt_of_succ_lt_succ hj))
+    exact (testBit_bit_succ _ _ _).trans (hk' _ (lt_of_succ_lt_succ hj))
 #align nat.exists_most_significant_bit Nat.exists_most_significant_bit
 
 theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : testBit m i = true)
@@ -248,16 +248,16 @@ theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : tes
   · exact False.elim (Bool.false_ne_true ((zero_testBit i).symm.trans hm))
   by_cases hi : i = 0
   · subst hi
-    simp only [testBit_zero] at hn hm
+    simp only [testBit_bit_zero] at hn hm
     have : n = m :=
       eq_of_testBit_eq fun i => by convert hnm (i + 1) (Nat.zero_lt_succ _) using 1
-      <;> rw [testBit_succ]
+      <;> rw [testBit_bit_succ]
     rw [hn, hm, this, bit_false, bit_true, bit0_val, bit1_val]
     exact lt_add_one _
   · obtain ⟨i', rfl⟩ := exists_eq_succ_of_ne_zero hi
-    simp only [testBit_succ] at hn hm
-    have :=
-      hn' _ hn hm fun j hj => by convert hnm j.succ (succ_lt_succ hj) using 1 <;> rw [testBit_succ]
+    simp only [testBit_bit_succ] at hn hm
+    have := hn' _ hn hm fun j hj => by
+      convert hnm j.succ (succ_lt_succ hj) using 1 <;> rw [testBit_bit_succ]
     have this' : 2 * n < 2 * m := Nat.mul_lt_mul' (le_refl _) this two_pos
     cases b <;> cases b'
     <;> simp only [bit_false, bit_true, bit0_val n, bit1_val n, bit0_val m, bit1_val m]
@@ -483,7 +483,7 @@ theorem bitwise_lt {f x y n} (hx : x < 2 ^ n) (hy : y < 2 ^ n) :
       cases n <;> simp_all
 
 lemma shiftLeft_lt {x n m : ℕ} (h : x < 2 ^ n) : x <<< m < 2 ^ (n + m) := by
-  simp only [pow_add, shiftLeft_eq, mul_lt_mul_right (two_pow_pos _), h]
+  simp only [pow_add, shiftLeft_eq, mul_lt_mul_right (Nat.two_pow_pos _), h]
 
 /-- Note that the LHS is the expression used within `Std.BitVec.append`, hence the name. -/
 lemma append_lt {x y n m} (hx : x < 2 ^ n) (hy : y < 2 ^ m) : y <<< n ||| x < 2 ^ (n + m) := by

There's an exciting linter failure on bump/v4.6.0, and I'm wondering if this is caused by strange simp lemmas in leanprover/std4#558, so I'm updating to that before the bump.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -129,12 +129,10 @@ theorem xor_bit : ∀ a m b n, bit a m ^^^ bit b n = bit (bne a b) (m ^^^ n) :=
 attribute [simp] Nat.testBit_bitwise
 #align nat.test_bit_bitwise Nat.testBit_bitwise
 
-@[simp]
 theorem testBit_lor : ∀ m n k, testBit (m ||| n) k = (testBit m k || testBit n k) :=
   testBit_bitwise rfl
 #align nat.test_bit_lor Nat.testBit_lor
 
-@[simp]
 theorem testBit_land : ∀ m n k, testBit (m &&& n) k = (testBit m k && testBit n k) :=
   testBit_bitwise rfl
 #align nat.test_bit_land Nat.testBit_land

This uses the improved shake script from #9772 to reduce imports across mathlib. The corresponding noshake.json file has been added to #9772.

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

@@ -4,7 +4,8 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Markus Himmel, Alex Keizer
 -/
 import Mathlib.Data.List.Basic
-import Mathlib.Data.Nat.Size
+import Mathlib.Data.Nat.Bits
+import Mathlib.Data.Nat.Pow
 import Mathlib.Tactic.Set
 
 #align_import data.nat.bitwise from "leanprover-community/mathlib"@"6afc9b06856ad973f6a2619e3e8a0a8d537a58f2"

The names for lemmas about monotonicity of (a ^ ·) and (· ^ n) were a mess. This PR tidies up everything related by following the naming convention for (a * ·) and (· * b). Namely, (a ^ ·) is pow_right and (· ^ n) is pow_left in lemma names. All lemma renames follow the corresponding multiplication lemma names closely.

Renames

Algebra.GroupPower.Order

• pow_mono → pow_right_mono
• pow_le_pow → pow_le_pow_right
• pow_le_pow_of_le_left → pow_le_pow_left
• pow_lt_pow_of_lt_left → pow_lt_pow_left
• strictMonoOn_pow → pow_left_strictMonoOn
• pow_strictMono_right → pow_right_strictMono
• pow_lt_pow → pow_lt_pow_right
• pow_lt_pow_iff → pow_lt_pow_iff_right
• pow_le_pow_iff → pow_le_pow_iff_right
• self_lt_pow → lt_self_pow
• strictAnti_pow → pow_right_strictAnti
• pow_lt_pow_iff_of_lt_one → pow_lt_pow_iff_right_of_lt_one
• pow_lt_pow_of_lt_one → pow_lt_pow_right_of_lt_one
• lt_of_pow_lt_pow → lt_of_pow_lt_pow_left
• le_of_pow_le_pow → le_of_pow_le_pow_left
• pow_lt_pow₀ → pow_lt_pow_right₀

Algebra.GroupPower.CovariantClass

• pow_le_pow_of_le_left' → pow_le_pow_left'
• nsmul_le_nsmul_of_le_right → nsmul_le_nsmul_right
• pow_lt_pow' → pow_lt_pow_right'
• nsmul_lt_nsmul → nsmul_lt_nsmul_left
• pow_strictMono_left → pow_right_strictMono'
• nsmul_strictMono_right → nsmul_left_strictMono
• StrictMono.pow_right' → StrictMono.pow_const
• StrictMono.nsmul_left → StrictMono.const_nsmul
• pow_strictMono_right' → pow_left_strictMono
• nsmul_strictMono_left → nsmul_right_strictMono
• Monotone.pow_right → Monotone.pow_const
• Monotone.nsmul_left → Monotone.const_nsmul
• lt_of_pow_lt_pow' → lt_of_pow_lt_pow_left'
• lt_of_nsmul_lt_nsmul → lt_of_nsmul_lt_nsmul_right
• pow_le_pow' → pow_le_pow_right'
• nsmul_le_nsmul → nsmul_le_nsmul_left
• pow_le_pow_of_le_one' → pow_le_pow_right_of_le_one'
• nsmul_le_nsmul_of_nonpos → nsmul_le_nsmul_left_of_nonpos
• le_of_pow_le_pow' → le_of_pow_le_pow_left'
• le_of_nsmul_le_nsmul' → le_of_nsmul_le_nsmul_right'
• pow_le_pow_iff' → pow_le_pow_iff_right'
• nsmul_le_nsmul_iff → nsmul_le_nsmul_iff_left
• pow_lt_pow_iff' → pow_lt_pow_iff_right'
• nsmul_lt_nsmul_iff → nsmul_lt_nsmul_iff_left

Data.Nat.Pow

• Nat.pow_lt_pow_of_lt_left → Nat.pow_lt_pow_left
• Nat.pow_le_iff_le_left → Nat.pow_le_pow_iff_left
• Nat.pow_lt_iff_lt_left → Nat.pow_lt_pow_iff_left

Lemmas added

• pow_le_pow_iff_left
• pow_lt_pow_iff_left
• pow_right_injective
• pow_right_inj
• Nat.pow_le_pow_left to have the correct name since Nat.pow_le_pow_of_le_left is in Std.
• Nat.pow_le_pow_right to have the correct name since Nat.pow_le_pow_of_le_right is in Std.

Lemmas removed

• self_le_pow was a duplicate of le_self_pow.
• Nat.pow_lt_pow_of_lt_right is defeq to pow_lt_pow_right.
• Nat.pow_right_strictMono is defeq to pow_right_strictMono.
• Nat.pow_le_iff_le_right is defeq to pow_le_pow_iff_right.
• Nat.pow_lt_iff_lt_right is defeq to pow_lt_pow_iff_right.

Other changes

• A bunch of proofs have been golfed.
• Some lemma assumptions have been turned from 0 < n or 1 ≤ n to n ≠ 0.
• A few Nat lemmas have been protected.
• One docstring has been fixed.

@@ -281,7 +281,7 @@ theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = f
   cases' hm.lt_or_lt with hm hm
   · rw [Nat.div_eq_of_lt]
     · simp
-    · exact Nat.pow_lt_pow_of_lt_right one_lt_two hm
+    · exact pow_lt_pow_right one_lt_two hm
   · rw [pow_div hm.le zero_lt_two, ← tsub_add_cancel_of_le (succ_le_of_lt <| tsub_pos_of_lt hm)]
     -- Porting note: XXX why does this make it work?
     rw [(rfl : succ 0 = 1)]
@@ -490,6 +490,6 @@ lemma shiftLeft_lt {x n m : ℕ} (h : x < 2 ^ n) : x <<< m < 2 ^ (n + m) := by
 lemma append_lt {x y n m} (hx : x < 2 ^ n) (hy : y < 2 ^ m) : y <<< n ||| x < 2 ^ (n + m) := by
   apply bitwise_lt
   · rw [add_comm]; apply shiftLeft_lt hy
-  · apply lt_of_lt_of_le hx <| pow_le_pow (le_succ _) (le_add_right _ _)
+  · apply lt_of_lt_of_le hx <| pow_le_pow_right (le_succ _) (le_add_right _ _)
 
 end Nat

@@ -263,7 +263,7 @@ theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : tes
     cases b <;> cases b'
     <;> simp only [bit_false, bit_true, bit0_val n, bit1_val n, bit0_val m, bit1_val m]
     · exact this'
-    · exact Nat.lt_add_right (2 * n) (2 * m) 1 this'
+    · exact Nat.lt_add_right 1 this'
     · calc
         2 * n + 1 < 2 * n + 2 := lt.base _
         _ ≤ 2 * m := mul_le_mul_left 2 this

Co-authored-by: Moritz Firsching <firsching@google.com>

@@ -92,7 +92,7 @@ lemma bitwise_bit {f : Bool → Bool → Bool} (h : f false false = false := by
 
 lemma bit_mod_two (a : Bool) (x : ℕ) :
     bit a x % 2 = if a then 1 else 0 := by
-  simp (config := { unfoldPartialApp := true }) [bit, bit0, bit1, Bool.cond_eq_ite, ←mul_two]
+  simp (config := { unfoldPartialApp := true }) [bit, bit0, bit1, Bool.cond_eq_ite, ← mul_two]
   split_ifs <;> simp [Nat.add_mod]
 
 @[simp]
@@ -173,7 +173,7 @@ lemma bitwise_bit' {f : Bool → Bool → Bool} (a : Bool) (m : Nat) (b : Bool)
     (ham : m = 0 → a = true) (hbn : n = 0 → b = true) :
     bitwise f (bit a m) (bit b n) = bit (f a b) (bitwise f m n) := by
   conv_lhs => unfold bitwise
-  rw [←bit_ne_zero_iff] at ham hbn
+  rw [← bit_ne_zero_iff] at ham hbn
   simp only [ham, hbn, bit_mod_two_eq_one_iff, Bool.decide_coe, ← div2_val, div2_bit, ne_eq,
     ite_false]
   conv_rhs => simp only [bit, bit1, bit0, Bool.cond_eq_ite]
@@ -187,13 +187,13 @@ lemma bitwise_eq_binaryRec (f : Bool → Bool → Bool) :
   induction x using binaryRec' generalizing y with
   | z => simp only [bitwise_zero_left, binaryRec_zero, Bool.cond_eq_ite]
   | f xb x hxb ih =>
-    rw [←bit_ne_zero_iff] at hxb
+    rw [← bit_ne_zero_iff] at hxb
     simp_rw [binaryRec_of_ne_zero _ _ hxb, bodd_bit, div2_bit, eq_rec_constant]
     induction y using binaryRec' with
     | z => simp only [bitwise_zero_right, binaryRec_zero, Bool.cond_eq_ite]
     | f yb y hyb =>
-      rw [←bit_ne_zero_iff] at hyb
-      simp_rw [binaryRec_of_ne_zero _ _ hyb, bitwise_of_ne_zero hxb hyb, bodd_bit, ←div2_val,
+      rw [← bit_ne_zero_iff] at hyb
+      simp_rw [binaryRec_of_ne_zero _ _ hyb, bitwise_of_ne_zero hxb hyb, bodd_bit, ← div2_val,
         div2_bit, eq_rec_constant, ih]
 
 theorem zero_of_testBit_eq_false {n : ℕ} (h : ∀ i, testBit n i = false) : n = 0 := by
@@ -463,7 +463,7 @@ theorem lt_xor_cases {a b c : ℕ} (h : a < b ^^^ c) : a ^^^ c < b ∨ a ^^^ b <
 #align nat.lt_lxor_cases Nat.lt_xor_cases
 
 @[simp] theorem bit_lt_two_pow_succ_iff {b x n} : bit b x < 2 ^ (n + 1) ↔ x < 2 ^ n := by
-  rw [pow_succ', ←bit0_eq_two_mul]
+  rw [pow_succ', ← bit0_eq_two_mul]
   cases b <;> simp
 
 /-- If `x` and `y` fit within `n` bits, then the result of any bitwise operation on `x` and `y` also

Notably leanprover/std4#366 changed the definition of testBit (to something equivalent) when upstreaming it, which broke a handful of proofs.

Other conflicting changes in Std, resolved for now by priming the mathlib name:

• Std.BitVec.adc: the type was changed from BitVec (n + 1) to Bool × BitVec w
• Nat.mul_add_mod: the type was changed from (a * b + c) % b = c % b to (b * a + c) % b = c % b

Zulip thread

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Alex Keizer <alex@keizer.dev> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

@@ -125,15 +125,7 @@ theorem xor_bit : ∀ a m b n, bit a m ^^^ bit b n = bit (bne a b) (m ^^^ n) :=
   bitwise_bit
 #align nat.lxor_bit Nat.xor_bit
 
-@[simp]
-theorem testBit_bitwise {f : Bool → Bool → Bool} (h : f false false = false) (m n k) :
-    testBit (bitwise f m n) k = f (testBit m k) (testBit n k) := by
-  induction' k with k ih generalizing m n
-  <;> cases' m using bitCasesOn with a m
-  <;> cases' n using bitCasesOn with b n
-  <;> rw [bitwise_bit h]
-  · simp [testBit_zero]
-  · simp [testBit_succ, ih]
+attribute [simp] Nat.testBit_bitwise
 #align nat.test_bit_bitwise Nat.testBit_bitwise
 
 @[simp]
@@ -151,9 +143,7 @@ theorem testBit_ldiff : ∀ m n k, testBit (ldiff m n) k = (testBit m k && not (
   testBit_bitwise rfl
 #align nat.test_bit_ldiff Nat.testBit_ldiff
 
-@[simp]
-theorem testBit_xor : ∀ m n k, testBit (m ^^^ n) k = bne (testBit m k) (testBit n k) :=
-  testBit_bitwise rfl
+attribute [simp] testBit_xor
 #align nat.test_bit_lxor Nat.testBit_xor
 
 end
@@ -216,31 +206,19 @@ theorem zero_of_testBit_eq_false {n : ℕ} (h : ∀ i, testBit n i = false) : n
 theorem testBit_eq_false_of_lt {n i} (h : n < 2 ^ i) : n.testBit i = false := by
   simp [testBit, shiftRight_eq_div_pow, Nat.div_eq_of_lt h]
 
-@[simp]
-theorem zero_testBit (i : ℕ) : testBit 0 i = false := by
-  simp only [testBit, zero_shiftRight, bodd_zero]
 #align nat.zero_test_bit Nat.zero_testBit
 
 /-- The ith bit is the ith element of `n.bits`. -/
 theorem testBit_eq_inth (n i : ℕ) : n.testBit i = n.bits.getI i := by
   induction' i with i ih generalizing n
-  · simp [testBit, bodd_eq_bits_head, List.getI_zero_eq_headI]
+  · simp only [testBit, zero_eq, shiftRight_zero, and_one_is_mod, mod_two_of_bodd,
+      bodd_eq_bits_head, List.getI_zero_eq_headI]
+    cases List.headI (bits n) <;> rfl
   conv_lhs => rw [← bit_decomp n]
   rw [testBit_succ, ih n.div2, div2_bits_eq_tail]
   cases n.bits <;> simp
 #align nat.test_bit_eq_inth Nat.testBit_eq_inth
 
-/-- Bitwise extensionality: Two numbers agree if they agree at every bit position. -/
-theorem eq_of_testBit_eq {n m : ℕ} (h : ∀ i, testBit n i = testBit m i) : n = m := by
-  induction' n using Nat.binaryRec with b n hn generalizing m
-  · simp only [zero_testBit] at h
-    exact (zero_of_testBit_eq_false fun i => (h i).symm).symm
-  induction' m using Nat.binaryRec with b' m
-  · simp only [zero_testBit] at h
-    exact zero_of_testBit_eq_false h
-  suffices h' : n = m by
-    rw [h', show b = b' by simpa using h 0]
-  exact hn fun i => by convert h (i + 1) using 1 <;> rw [testBit_succ]
 #align nat.eq_of_test_bit_eq Nat.eq_of_testBit_eq
 
 theorem exists_most_significant_bit {n : ℕ} (h : n ≠ 0) :
@@ -294,20 +272,20 @@ theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : tes
 
 @[simp]
 theorem testBit_two_pow_self (n : ℕ) : testBit (2 ^ n) n = true := by
-  rw [testBit, shiftRight_eq_div_pow, Nat.div_self (pow_pos (α := ℕ) zero_lt_two n), bodd_one]
+  rw [testBit, shiftRight_eq_div_pow, Nat.div_self (pow_pos (α := ℕ) zero_lt_two n)]
+  simp
 #align nat.test_bit_two_pow_self Nat.testBit_two_pow_self
 
 theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = false := by
   rw [testBit, shiftRight_eq_div_pow]
   cases' hm.lt_or_lt with hm hm
-  · rw [Nat.div_eq_of_lt, bodd_zero]
-    exact Nat.pow_lt_pow_of_lt_right one_lt_two hm
+  · rw [Nat.div_eq_of_lt]
+    · simp
+    · exact Nat.pow_lt_pow_of_lt_right one_lt_two hm
   · rw [pow_div hm.le zero_lt_two, ← tsub_add_cancel_of_le (succ_le_of_lt <| tsub_pos_of_lt hm)]
     -- Porting note: XXX why does this make it work?
     rw [(rfl : succ 0 = 1)]
-    simp only [ge_iff_le, tsub_le_iff_right, pow_succ, bodd_mul,
-      Bool.and_eq_false_eq_eq_false_or_eq_false, or_true]
-    exact Or.inr rfl
+    simp [pow_succ, and_one_is_mod, mul_mod_left]
 #align nat.test_bit_two_pow_of_ne Nat.testBit_two_pow_of_ne
 
 theorem testBit_two_pow (n m : ℕ) : testBit (2 ^ n) m = (n = m) := by
@@ -371,25 +349,10 @@ theorem zero_xor (n : ℕ) : 0 ^^^ n = n := by simp [HXor.hXor, Xor.xor, xor]
 theorem xor_zero (n : ℕ) : n ^^^ 0 = n := by simp [HXor.hXor, Xor.xor, xor]
 #align nat.lxor_zero Nat.xor_zero
 
-@[simp]
-theorem zero_land (n : ℕ) : 0 &&& n = 0 := by
-  simp only [HAnd.hAnd, AndOp.and, land, bitwise_zero_left, ite_false, Bool.and_true];
-#align nat.zero_land Nat.zero_land
-
-@[simp]
-theorem land_zero (n : ℕ) : n &&& 0 = 0 := by
-  simp only [HAnd.hAnd, AndOp.and, land, bitwise_zero_right, ite_false, Bool.and_false]
-#align nat.land_zero Nat.land_zero
-
-@[simp]
-theorem zero_lor (n : ℕ) : 0 ||| n = n := by
-  simp only [HOr.hOr, OrOp.or, lor, bitwise_zero_left, ite_true, Bool.or_true]
-#align nat.zero_lor Nat.zero_lor
-
-@[simp]
-theorem lor_zero (n : ℕ) : n ||| 0 = n := by
-  simp only [HOr.hOr, OrOp.or, lor, bitwise_zero_right, ite_true, Bool.or_false]
-#align nat.lor_zero Nat.lor_zero
+#align nat.zero_land Nat.zero_and
+#align nat.land_zero Nat.and_zero
+#align nat.zero_lor Nat.zero_or
+#align nat.lor_zero Nat.or_zero
 
 
 /-- Proving associativity of bitwise operations in general essentially boils down to a huge case
@@ -487,11 +450,11 @@ theorem xor_trichotomy {a b c : ℕ} (h : a ≠ b ^^^ c) :
   all_goals
     exact lt_of_testBit i (by
       -- Porting note: this was originally `simp [h, hi]`
-      rw [Nat.testBit_xor, h, Bool.bne_eq_xor, Bool.true_xor,hi]
+      rw [Nat.testBit_xor, h, Bool.xor, Bool.true_xor, hi]
       rfl
     ) h fun j hj => by
       -- Porting note: this was originally `simp [hi' _ hj]`
-      rw [Nat.testBit_xor, hi' _ hj, Bool.bne_eq_xor, Bool.xor_false, eq_self_iff_true]
+      rw [Nat.testBit_xor, hi' _ hj, Bool.xor, Bool.xor_false, eq_self_iff_true]
       trivial
 #align nat.lxor_trichotomy Nat.xor_trichotomy
 

• Remove simp-lemma bitwise_of_ne_zero, since it wasn't used, and could cause loops in an inconsistent context.

@@ -61,7 +61,6 @@ lemma bitwise_zero : bitwise f 0 0 = 0 := by
   simp only [bitwise_zero_right, ite_self]
 #align nat.bitwise_zero Nat.bitwise_zero
 
-@[simp]
 lemma bitwise_of_ne_zero {n m : Nat} (hn : n ≠ 0) (hm : m ≠ 0) :
     bitwise f n m = bit (f (bodd n) (bodd m)) (bitwise f (n / 2) (m / 2)) := by
   conv_lhs => unfold bitwise

A simple result which shows that if x and y fit within n bits, then the result of any bitwise operation on x and y also fits within n bits.

Co-authored-by: mhk119 [58151072+mhk119@users.noreply.github.com](mailto:58151072+mhk119@users.noreply.github.com) Co-authored-by: Eric Wieser [wieser.eric@gmail.com](mailto:wieser.eric@gmail.com)

@@ -500,4 +500,34 @@ theorem lt_xor_cases {a b c : ℕ} (h : a < b ^^^ c) : a ^^^ c < b ∨ a ^^^ b <
   (or_iff_right fun h' => (h.asymm h').elim).1 <| xor_trichotomy h.ne
 #align nat.lt_lxor_cases Nat.lt_xor_cases
 
+@[simp] theorem bit_lt_two_pow_succ_iff {b x n} : bit b x < 2 ^ (n + 1) ↔ x < 2 ^ n := by
+  rw [pow_succ', ←bit0_eq_two_mul]
+  cases b <;> simp
+
+/-- 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 bitwise_lt {f x y n} (hx : x < 2 ^ n) (hy : y < 2 ^ n) :
+    bitwise f x y < 2 ^ n := by
+  induction x using Nat.binaryRec' generalizing n y with
+  | z =>
+    simp only [bitwise_zero_left]
+    split <;> assumption
+  | @f bx nx hnx ih =>
+    cases y using Nat.binaryRec' with
+    | z =>
+      simp only [bitwise_zero_right]
+      split <;> assumption
+    | f «by» ny hny =>
+      rw [bitwise_bit' _ _ _ _ hnx hny]
+      cases n <;> simp_all
+
+lemma shiftLeft_lt {x n m : ℕ} (h : x < 2 ^ n) : x <<< m < 2 ^ (n + m) := by
+  simp only [pow_add, shiftLeft_eq, mul_lt_mul_right (two_pow_pos _), h]
+
+/-- Note that the LHS is the expression used within `Std.BitVec.append`, hence the name. -/
+lemma append_lt {x y n m} (hx : x < 2 ^ n) (hy : y < 2 ^ m) : y <<< n ||| x < 2 ^ (n + m) := by
+  apply bitwise_lt
+  · rw [add_comm]; apply shiftLeft_lt hy
+  · apply lt_of_lt_of_le hx <| pow_le_pow (le_succ _) (le_add_right _ _)
+
 end Nat

These are generally useful and split out of #5920.

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

@@ -214,6 +214,9 @@ theorem zero_of_testBit_eq_false {n : ℕ} (h : ∀ i, testBit n i = false) : n
     rw [this, bit_false, bit0_val, hn fun i => by rw [← h (i + 1), testBit_succ], mul_zero]
 #align nat.zero_of_test_bit_eq_ff Nat.zero_of_testBit_eq_false
 
+theorem testBit_eq_false_of_lt {n i} (h : n < 2 ^ i) : n.testBit i = false := by
+  simp [testBit, shiftRight_eq_div_pow, Nat.div_eq_of_lt h]
+
 @[simp]
 theorem zero_testBit (i : ℕ) : testBit 0 i = false := by
   simp only [testBit, zero_shiftRight, bodd_zero]
@@ -350,6 +353,17 @@ theorem xor_comm (n m : ℕ) : n ^^^ m = m ^^^ n :=
   bitwise_comm (Bool.bne_eq_xor ▸ Bool.xor_comm) n m
 #align nat.lxor_comm Nat.xor_comm
 
+lemma and_two_pow (n i : ℕ) : n &&& 2 ^ i = (n.testBit i).toNat * 2 ^ i := by
+  refine eq_of_testBit_eq fun j => ?_
+  obtain rfl | hij := Decidable.eq_or_ne i j <;> cases' h : n.testBit i
+  · simp [h]
+  · simp [h]
+  · simp [h, testBit_two_pow_of_ne hij]
+  · simp [h, testBit_two_pow_of_ne hij]
+
+lemma two_pow_and (n i : ℕ) : 2 ^ i &&& n = 2 ^ i * (n.testBit i).toNat := by
+  rw [mul_comm, land_comm, and_two_pow]
+
 @[simp]
 theorem zero_xor (n : ℕ) : 0 ^^^ n = n := by simp [HXor.hXor, Xor.xor, xor]
 #align nat.zero_lxor Nat.zero_xor

PR contents

This is the supremum of

• #8284
• #8056
• #8023
• #8332
• #8226 (already approved)
• #7834 (already approved)

along with some minor fixes from failures on nightly-testing as Mathlib master is merged into it.

Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.

I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0 branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.

Lean PRs involved in this bump

In particular this includes adjustments for the Lean PRs

• leanprover/lean4#2778
• leanprover/lean4#2790
• leanprover/lean4#2783
• leanprover/lean4#2825
• leanprover/lean4#2722

leanprover/lean4#2778

We can get rid of all the

local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)

macros across Mathlib (and in any projects that want to write natural number powers of reals).

leanprover/lean4#2722

Changes the default behaviour of simp to (config := {decide := false}). This makes simp (and consequentially norm_num) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp or norm_num to decide or rfl, or adding (config := {decide := true}).

leanprover/lean4#2783

This changed the behaviour of simp so that simp [f] will only unfold "fully applied" occurrences of f. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true }). We may in future add a syntax for this, e.g. simp [!f]; please provide feedback! In the meantime, we have made the following changes:

• switching to using explicit lemmas that have the intended level of application
• (config := { unfoldPartialApp := true }) in some places, to recover the old behaviour
• Using @[eqns] to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp and Function.flip.

This change in Lean may require further changes down the line (e.g. adding the !f syntax, and/or upstreaming the special treatment for Function.comp and Function.flip, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>

@@ -82,17 +82,18 @@ theorem binaryRec_of_ne_zero {C : Nat → Sort*} (z : C 0) (f : ∀ b n, C n →
 lemma bitwise_bit {f : Bool → Bool → Bool} (h : f false false = false := by rfl) (a m b n) :
     bitwise f (bit a m) (bit b n) = bit (f a b) (bitwise f m n) := by
   conv_lhs => unfold bitwise
-  simp only [bit, bit1, bit0, Bool.cond_eq_ite]
+  simp (config := { unfoldPartialApp := true }) only [bit, bit1, bit0, Bool.cond_eq_ite]
   have h1 x :     (x + x) % 2 = 0 := by rw [← two_mul, mul_comm]; apply mul_mod_left
   have h2 x : (x + x + 1) % 2 = 1 := by rw [← two_mul, add_comm]; apply add_mul_mod_self_left
   have h3 x :     (x + x) / 2 = x := by rw [← two_mul, mul_comm]; apply mul_div_left _ zero_lt_two
-  have h4 x : (x + x + 1) / 2 = x := by rw [← two_mul, add_comm]; simp [add_mul_div_left]
-  cases a <;> cases b <;> simp [h1, h2, h3, h4] <;> split_ifs <;> simp_all
+  have h4 x : (x + x + 1) / 2 = x := by rw [← two_mul, add_comm]; simp [add_mul_div_left]; rfl
+  cases a <;> cases b <;> simp [h1, h2, h3, h4] <;> split_ifs
+    <;> simp_all (config := {decide := true})
 #align nat.bitwise_bit Nat.bitwise_bit
 
 lemma bit_mod_two (a : Bool) (x : ℕ) :
     bit a x % 2 = if a then 1 else 0 := by
-  simp [bit, bit0, bit1, Bool.cond_eq_ite, ←mul_two]
+  simp (config := { unfoldPartialApp := true }) [bit, bit0, bit1, Bool.cond_eq_ite, ←mul_two]
   split_ifs <;> simp [Nat.add_mod]
 
 @[simp]
@@ -304,6 +305,7 @@ theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = f
     rw [(rfl : succ 0 = 1)]
     simp only [ge_iff_le, tsub_le_iff_right, pow_succ, bodd_mul,
       Bool.and_eq_false_eq_eq_false_or_eq_false, or_true]
+    exact Or.inr rfl
 #align nat.test_bit_two_pow_of_ne Nat.testBit_two_pow_of_ne
 
 theorem testBit_two_pow (n m : ℕ) : testBit (2 ^ n) m = (n = m) := by
@@ -349,8 +351,7 @@ theorem xor_comm (n m : ℕ) : n ^^^ m = m ^^^ n :=
 #align nat.lxor_comm Nat.xor_comm
 
 @[simp]
-theorem zero_xor (n : ℕ) : 0 ^^^ n = n := by
- simp only [HXor.hXor, Xor.xor, xor, bitwise_zero_left, ite_true]
+theorem zero_xor (n : ℕ) : 0 ^^^ n = n := by simp [HXor.hXor, Xor.xor, xor]
 #align nat.zero_lxor Nat.zero_xor
 
 @[simp]
@@ -359,22 +360,22 @@ theorem xor_zero (n : ℕ) : n ^^^ 0 = n := by simp [HXor.hXor, Xor.xor, xor]
 
 @[simp]
 theorem zero_land (n : ℕ) : 0 &&& n = 0 := by
-  simp only [HAnd.hAnd, AndOp.and, land, bitwise_zero_left, ite_false];
+  simp only [HAnd.hAnd, AndOp.and, land, bitwise_zero_left, ite_false, Bool.and_true];
 #align nat.zero_land Nat.zero_land
 
 @[simp]
 theorem land_zero (n : ℕ) : n &&& 0 = 0 := by
-  simp only [HAnd.hAnd, AndOp.and, land, bitwise_zero_right, ite_false]
+  simp only [HAnd.hAnd, AndOp.and, land, bitwise_zero_right, ite_false, Bool.and_false]
 #align nat.land_zero Nat.land_zero
 
 @[simp]
 theorem zero_lor (n : ℕ) : 0 ||| n = n := by
-  simp only [HOr.hOr, OrOp.or, lor, bitwise_zero_left, ite_true]
+  simp only [HOr.hOr, OrOp.or, lor, bitwise_zero_left, ite_true, Bool.or_true]
 #align nat.zero_lor Nat.zero_lor
 
 @[simp]
 theorem lor_zero (n : ℕ) : n ||| 0 = n := by
-  simp only [HOr.hOr, OrOp.or, lor, bitwise_zero_right, ite_true]
+  simp only [HOr.hOr, OrOp.or, lor, bitwise_zero_right, ite_true, Bool.or_false]
 #align nat.lor_zero Nat.lor_zero
 
 

This bumps Std up to leanprover/std4#329.

This is a replacement for #8005, which I'll now close.

Co-authored-by: François G. Dorais <fgdorais@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -477,7 +477,7 @@ theorem xor_trichotomy {a b c : ℕ} (h : a ≠ b ^^^ c) :
       rfl
     ) h fun j hj => by
       -- Porting note: this was originally `simp [hi' _ hj]`
-      rw [Nat.testBit_xor, hi' _ hj, Bool.bne_eq_xor, Bool.xor_false_right, eq_self_iff_true]
+      rw [Nat.testBit_xor, hi' _ hj, Bool.bne_eq_xor, Bool.xor_false, eq_self_iff_true]
       trivial
 #align nat.lxor_trichotomy Nat.xor_trichotomy
 

This didn't exist in Lean 3.

@@ -106,12 +106,12 @@ lemma bit_mod_two_eq_one_iff (a x) :
   rw [bit_mod_two]; split_ifs <;> simp_all
 
 @[simp]
-theorem lor_bit : ∀ a m b n, lor (bit a m) (bit b n) = bit (a || b) (lor m n) :=
+theorem lor_bit : ∀ a m b n, bit a m ||| bit b n = bit (a || b) (m ||| n) :=
   bitwise_bit
 #align nat.lor_bit Nat.lor_bit
 
 @[simp]
-theorem land_bit : ∀ a m b n, land (bit a m) (bit b n) = bit (a && b) (land m n) :=
+theorem land_bit : ∀ a m b n, bit a m &&& bit b n = bit (a && b) (m &&& n) :=
   bitwise_bit
 #align nat.land_bit Nat.land_bit
 
@@ -121,7 +121,7 @@ theorem ldiff_bit : ∀ a m b n, ldiff (bit a m) (bit b n) = bit (a && not b) (l
 #align nat.ldiff_bit Nat.ldiff_bit
 
 @[simp]
-theorem xor_bit : ∀ a m b n, xor (bit a m) (bit b n) = bit (bne a b) (xor m n) :=
+theorem xor_bit : ∀ a m b n, bit a m ^^^ bit b n = bit (bne a b) (m ^^^ n) :=
   bitwise_bit
 #align nat.lxor_bit Nat.xor_bit
 
@@ -137,12 +137,12 @@ theorem testBit_bitwise {f : Bool → Bool → Bool} (h : f false false = false)
 #align nat.test_bit_bitwise Nat.testBit_bitwise
 
 @[simp]
-theorem testBit_lor : ∀ m n k, testBit (lor m n) k = (testBit m k || testBit n k) :=
+theorem testBit_lor : ∀ m n k, testBit (m ||| n) k = (testBit m k || testBit n k) :=
   testBit_bitwise rfl
 #align nat.test_bit_lor Nat.testBit_lor
 
 @[simp]
-theorem testBit_land : ∀ m n k, testBit (land m n) k = (testBit m k && testBit n k) :=
+theorem testBit_land : ∀ m n k, testBit (m &&& n) k = (testBit m k && testBit n k) :=
   testBit_bitwise rfl
 #align nat.test_bit_land Nat.testBit_land
 
@@ -152,7 +152,7 @@ theorem testBit_ldiff : ∀ m n k, testBit (ldiff m n) k = (testBit m k && not (
 #align nat.test_bit_ldiff Nat.testBit_ldiff
 
 @[simp]
-theorem testBit_xor : ∀ m n k, testBit (xor m n) k = bne (testBit m k) (testBit n k) :=
+theorem testBit_xor : ∀ m n k, testBit (m ^^^ n) k = bne (testBit m k) (testBit n k) :=
   testBit_bitwise rfl
 #align nat.test_bit_lxor Nat.testBit_xor
 
@@ -336,45 +336,45 @@ theorem bitwise_comm {f : Bool → Bool → Bool} (hf : ∀ b b', f b b' = f b'
     _ = swap (bitwise f) := bitwise_swap
 #align nat.bitwise_comm Nat.bitwise_comm
 
-theorem lor_comm (n m : ℕ) : lor n m = lor m n :=
+theorem lor_comm (n m : ℕ) : n ||| m = m ||| n :=
   bitwise_comm Bool.or_comm n m
 #align nat.lor_comm Nat.lor_comm
 
-theorem land_comm (n m : ℕ) : land n m = land m n :=
+theorem land_comm (n m : ℕ) : n &&& m = m &&& n :=
   bitwise_comm Bool.and_comm n m
 #align nat.land_comm Nat.land_comm
 
-theorem xor_comm (n m : ℕ) : xor n m = xor m n :=
+theorem xor_comm (n m : ℕ) : n ^^^ m = m ^^^ n :=
   bitwise_comm (Bool.bne_eq_xor ▸ Bool.xor_comm) n m
 #align nat.lxor_comm Nat.xor_comm
 
 @[simp]
-theorem zero_xor (n : ℕ) : xor 0 n = n := by
- simp only [xor, bitwise_zero_left, ite_true]
+theorem zero_xor (n : ℕ) : 0 ^^^ n = n := by
+ simp only [HXor.hXor, Xor.xor, xor, bitwise_zero_left, ite_true]
 #align nat.zero_lxor Nat.zero_xor
 
 @[simp]
-theorem xor_zero (n : ℕ) : xor n 0 = n := by simp [xor]
+theorem xor_zero (n : ℕ) : n ^^^ 0 = n := by simp [HXor.hXor, Xor.xor, xor]
 #align nat.lxor_zero Nat.xor_zero
 
 @[simp]
-theorem zero_land (n : ℕ) : land 0 n = 0 := by
-  simp only [land, bitwise_zero_left, ite_false];
+theorem zero_land (n : ℕ) : 0 &&& n = 0 := by
+  simp only [HAnd.hAnd, AndOp.and, land, bitwise_zero_left, ite_false];
 #align nat.zero_land Nat.zero_land
 
 @[simp]
-theorem land_zero (n : ℕ) : land n 0 = 0 := by
-  simp only [land, bitwise_zero_right, ite_false]
+theorem land_zero (n : ℕ) : n &&& 0 = 0 := by
+  simp only [HAnd.hAnd, AndOp.and, land, bitwise_zero_right, ite_false]
 #align nat.land_zero Nat.land_zero
 
 @[simp]
-theorem zero_lor (n : ℕ) : lor 0 n = n := by
-  simp only [lor, bitwise_zero_left, ite_true]
+theorem zero_lor (n : ℕ) : 0 ||| n = n := by
+  simp only [HOr.hOr, OrOp.or, lor, bitwise_zero_left, ite_true]
 #align nat.zero_lor Nat.zero_lor
 
 @[simp]
-theorem lor_zero (n : ℕ) : lor n 0 = n := by
-  simp only [lor, bitwise_zero_right, ite_true]
+theorem lor_zero (n : ℕ) : n ||| 0 = n := by
+  simp only [HOr.hOr, OrOp.or, lor, bitwise_zero_right, ite_true]
 #align nat.lor_zero Nat.lor_zero
 
 
@@ -390,73 +390,73 @@ macro "bitwise_assoc_tac" : tactic => set_option hygiene false in `(tactic| (
   -- This is necessary because these are simp lemmas in mathlib
   <;> simp [hn, Bool.or_assoc, Bool.and_assoc, Bool.bne_eq_xor]))
 
-theorem xor_assoc (n m k : ℕ) : xor (xor n m) k = xor n (xor m k) := by bitwise_assoc_tac
+theorem xor_assoc (n m k : ℕ) : (n ^^^ m) ^^^ k = n ^^^ (m ^^^ k) := by bitwise_assoc_tac
 #align nat.lxor_assoc Nat.xor_assoc
 
-theorem land_assoc (n m k : ℕ) : land (land n m) k = land n (land m k) := by bitwise_assoc_tac
+theorem land_assoc (n m k : ℕ) : (n &&& m) &&& k = n &&& (m &&& k) := by bitwise_assoc_tac
 #align nat.land_assoc Nat.land_assoc
 
-theorem lor_assoc (n m k : ℕ) : lor (lor n m) k = lor n (lor m k) := by bitwise_assoc_tac
+theorem lor_assoc (n m k : ℕ) : (n ||| m) ||| k = n ||| (m ||| k) := by bitwise_assoc_tac
 #align nat.lor_assoc Nat.lor_assoc
 
 @[simp]
-theorem xor_self (n : ℕ) : xor n n = 0 :=
+theorem xor_self (n : ℕ) : n ^^^ n = 0 :=
   zero_of_testBit_eq_false fun i => by simp
 #align nat.lxor_self Nat.xor_self
 
 -- These lemmas match `mul_inv_cancel_right` and `mul_inv_cancel_left`.
-theorem lxor_cancel_right (n m : ℕ) : xor (xor m n) n = m := by
+theorem lxor_cancel_right (n m : ℕ) : (m ^^^ n) ^^^ n = m := by
   rw [xor_assoc, xor_self, xor_zero]
 #align nat.lxor_cancel_right Nat.lxor_cancel_right
 
-theorem xor_cancel_left (n m : ℕ) : xor n (xor n m) = m := by
+theorem xor_cancel_left (n m : ℕ) : n ^^^ (n ^^^ m) = m := by
   rw [← xor_assoc, xor_self, zero_xor]
 #align nat.lxor_cancel_left Nat.xor_cancel_left
 
-theorem xor_right_injective {n : ℕ} : Function.Injective (xor n) := fun m m' h => by
+theorem xor_right_injective {n : ℕ} : Function.Injective (HXor.hXor n : ℕ → ℕ) := fun m m' h => by
   rw [← xor_cancel_left n m, ← xor_cancel_left n m', h]
 #align nat.lxor_right_injective Nat.xor_right_injective
 
-theorem xor_left_injective {n : ℕ} : Function.Injective fun m => xor m n :=
-  fun m m' (h : xor m n = xor m' n) => by
+theorem xor_left_injective {n : ℕ} : Function.Injective fun m => m ^^^ n :=
+  fun m m' (h : m ^^^ n = m' ^^^ n) => by
   rw [← lxor_cancel_right n m, ← lxor_cancel_right n m', h]
 #align nat.lxor_left_injective Nat.xor_left_injective
 
 @[simp]
-theorem xor_right_inj {n m m' : ℕ} : xor n m = xor n m' ↔ m = m' :=
+theorem xor_right_inj {n m m' : ℕ} : n ^^^ m = n ^^^ m' ↔ m = m' :=
   xor_right_injective.eq_iff
 #align nat.lxor_right_inj Nat.xor_right_inj
 
 @[simp]
-theorem xor_left_inj {n m m' : ℕ} : xor m n = xor m' n ↔ m = m' :=
+theorem xor_left_inj {n m m' : ℕ} : m ^^^ n = m' ^^^ n ↔ m = m' :=
   xor_left_injective.eq_iff
 #align nat.lxor_left_inj Nat.xor_left_inj
 
 @[simp]
-theorem xor_eq_zero {n m : ℕ} : xor n m = 0 ↔ n = m := by
+theorem xor_eq_zero {n m : ℕ} : n ^^^ m = 0 ↔ n = m := by
   rw [← xor_self n, xor_right_inj, eq_comm]
 #align nat.lxor_eq_zero Nat.xor_eq_zero
 
-theorem xor_ne_zero {n m : ℕ} : xor n m ≠ 0 ↔ n ≠ m :=
+theorem xor_ne_zero {n m : ℕ} : n ^^^ m ≠ 0 ↔ n ≠ m :=
   xor_eq_zero.not
 #align nat.lxor_ne_zero Nat.xor_ne_zero
 
-theorem xor_trichotomy {a b c : ℕ} (h : a ≠ xor b c) :
-    xor b c < a ∨ xor a c < b ∨ xor a b < c := by
-  set v := xor a (xor b c) with hv
+theorem xor_trichotomy {a b c : ℕ} (h : a ≠ b ^^^ c) :
+    b ^^^ c < a ∨ a ^^^ c < b ∨ a ^^^ b < c := by
+  set v := a ^^^ (b ^^^ c) with hv
   -- The xor of any two of `a`, `b`, `c` is the xor of `v` and the third.
-  have hab : xor a b = xor c v := by
+  have hab : a ^^^ b = c ^^^ v := by
     rw [hv]
     conv_rhs =>
       rw [xor_comm]
       simp [xor_assoc]
-  have hac : xor a c = xor b v := by
+  have hac : a ^^^ c = b ^^^ v := by
     rw [hv]
     conv_rhs =>
       right
       rw [← xor_comm]
     rw [← xor_assoc, ← xor_assoc, xor_self, zero_xor, xor_comm]
-  have hbc : xor b c = xor a v := by simp [hv, ← xor_assoc]
+  have hbc : b ^^^ c = a ^^^ v := by simp [hv, ← xor_assoc]
   -- If `i` is the position of the most significant bit of `v`, then at least one of `a`, `b`, `c`
   -- has a one bit at position `i`.
   obtain ⟨i, ⟨hi, hi'⟩⟩ := exists_most_significant_bit (xor_ne_zero.2 h)
@@ -481,7 +481,7 @@ theorem xor_trichotomy {a b c : ℕ} (h : a ≠ xor b c) :
       trivial
 #align nat.lxor_trichotomy Nat.xor_trichotomy
 
-theorem lt_xor_cases {a b c : ℕ} (h : a < xor b c) : xor a c < b ∨ xor a b < c :=
+theorem lt_xor_cases {a b c : ℕ} (h : a < b ^^^ c) : a ^^^ c < b ∨ a ^^^ b < c :=
   (or_iff_right fun h' => (h.asymm h').elim).1 <| xor_trichotomy h.ne
 #align nat.lt_lxor_cases Nat.lt_xor_cases
 

We would like to move much of the content of this file up to Std, as projects working on SMT automation need them.

This is a preliminary cleanup to reduce imports in preparation for upstreaming.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -3,13 +3,9 @@ Copyright (c) 2020 Markus Himmel. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Markus Himmel, Alex Keizer
 -/
-import Lean.Elab.Tactic
 import Mathlib.Data.List.Basic
-import Mathlib.Data.Nat.Bits
 import Mathlib.Data.Nat.Size
-import Mathlib.Data.Nat.Order.Lemmas
-import Mathlib.Tactic.Linarith
-import Mathlib.Tactic.Ring
+import Mathlib.Tactic.Set
 
 #align_import data.nat.bitwise from "leanprover-community/mathlib"@"6afc9b06856ad973f6a2619e3e8a0a8d537a58f2"
 
@@ -87,10 +83,10 @@ lemma bitwise_bit {f : Bool → Bool → Bool} (h : f false false = false := by
     bitwise f (bit a m) (bit b n) = bit (f a b) (bitwise f m n) := by
   conv_lhs => unfold bitwise
   simp only [bit, bit1, bit0, Bool.cond_eq_ite]
-  have h1 x :     (x + x) % 2 = 0 := by ring_nf; apply mul_mod_left
-  have h2 x : (x + x + 1) % 2 = 1 := by ring_nf; apply add_mul_mod_self_right
-  have h3 x :     (x + x) / 2 = x := by ring_nf; apply mul_div_left _ zero_lt_two
-  have h4 x : (x + x + 1) / 2 = x := by ring_nf; simp [add_mul_div_right]
+  have h1 x :     (x + x) % 2 = 0 := by rw [← two_mul, mul_comm]; apply mul_mod_left
+  have h2 x : (x + x + 1) % 2 = 1 := by rw [← two_mul, add_comm]; apply add_mul_mod_self_left
+  have h3 x :     (x + x) / 2 = x := by rw [← two_mul, mul_comm]; apply mul_div_left _ zero_lt_two
+  have h4 x : (x + x + 1) / 2 = x := by rw [← two_mul, add_comm]; simp [add_mul_div_left]
   cases a <;> cases b <;> simp [h1, h2, h3, h4] <;> split_ifs <;> simp_all
 #align nat.bitwise_bit Nat.bitwise_bit
 
@@ -282,9 +278,15 @@ theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : tes
     simp only [testBit_succ] at hn hm
     have :=
       hn' _ hn hm fun j hj => by convert hnm j.succ (succ_lt_succ hj) using 1 <;> rw [testBit_succ]
+    have this' : 2 * n < 2 * m := Nat.mul_lt_mul' (le_refl _) this two_pos
     cases b <;> cases b'
     <;> simp only [bit_false, bit_true, bit0_val n, bit1_val n, bit0_val m, bit1_val m]
-    <;> linarith only [this]
+    · exact this'
+    · exact Nat.lt_add_right (2 * n) (2 * m) 1 this'
+    · calc
+        2 * n + 1 < 2 * n + 2 := lt.base _
+        _ ≤ 2 * m := mul_le_mul_left 2 this
+    · exact Nat.succ_lt_succ this'
 #align nat.lt_of_test_bit Nat.lt_of_testBit
 
 @[simp]
@@ -295,7 +297,7 @@ theorem testBit_two_pow_self (n : ℕ) : testBit (2 ^ n) n = true := by
 theorem testBit_two_pow_of_ne {n m : ℕ} (hm : n ≠ m) : testBit (2 ^ n) m = false := by
   rw [testBit, shiftRight_eq_div_pow]
   cases' hm.lt_or_lt with hm hm
-  · rw [Nat.div_eq_zero, bodd_zero]
+  · rw [Nat.div_eq_of_lt, bodd_zero]
     exact Nat.pow_lt_pow_of_lt_right one_lt_two hm
   · rw [pow_div hm.le zero_lt_two, ← tsub_add_cancel_of_le (succ_le_of_lt <| tsub_pos_of_lt hm)]
     -- Porting note: XXX why does this make it work?

Building upon the proof that Nat.bitwise and Nat.bitwise' are equal (from #7410), this PR completely removes bitwise' and changes all uses to bitwise instead.

In particular, land'/lor'/lxor' are replaced with the bitwise-based equivalent operations in core, which have overriden optimized implementations in the compiler.

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Alex Keizer <alex@keizer.dev> Co-authored-by: Chris Hughes <chrishughes24@gmail.com>

@@ -18,7 +18,7 @@ import Mathlib.Tactic.Ring
 
 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.
+`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.
@@ -48,16 +48,10 @@ set_option linter.deprecated false
 section
 variable {f : Bool → Bool → Bool}
 
-lemma bitwise'_bit' {f : Bool → Bool → Bool} (a : Bool) (m : Nat) (b : Bool) (n : Nat)
-    (ham : m = 0 → a = true) (hbn : n = 0 → b = true) :
-    bitwise' f (bit a m) (bit b n) = bit (f a b) (bitwise' f m n) := by
-  rw [bitwise', binaryRec_eq', binaryRec_eq']
-  · apply Or.inr hbn
-  · apply Or.inr ham
-
 @[simp]
 lemma bitwise_zero_left (m : Nat) : bitwise f 0 m = if f false true then m else 0 :=
   rfl
+#align nat.bitwise_zero_left Nat.bitwise_zero_left
 
 @[simp]
 lemma bitwise_zero_right (n : Nat) : bitwise f n 0 = if f true false then n else 0 := by
@@ -65,81 +59,106 @@ lemma bitwise_zero_right (n : Nat) : bitwise f n 0 = if f true false then n else
   simp only [ite_self, decide_False, Nat.zero_div, ite_true, ite_eq_right_iff]
   rintro ⟨⟩
   split_ifs <;> rfl
-
-@[simp]
-theorem bitwise'_zero_right (m : Nat) :
-    bitwise' f m 0 = bif f true false then m else 0 := by
-  unfold bitwise' binaryRec
-  simp only [Bool.cond_eq_ite, eq_mpr_eq_cast, cast_eq, dite_eq_ite]
-  split_ifs with hx <;> simp only [bit_decomp, binaryRec_zero, hx]
+#align nat.bitwise_zero_right Nat.bitwise_zero_right
 
 lemma bitwise_zero : bitwise f 0 0 = 0 := by
   simp only [bitwise_zero_right, ite_self]
+#align nat.bitwise_zero Nat.bitwise_zero
 
 @[simp]
 lemma bitwise_of_ne_zero {n m : Nat} (hn : n ≠ 0) (hm : m ≠ 0) :
     bitwise f n m = bit (f (bodd n) (bodd m)) (bitwise f (n / 2) (m / 2)) := by
-  conv_lhs => { unfold bitwise }
+  conv_lhs => unfold bitwise
   have mod_two_iff_bod x : (x % 2 = 1 : Bool) = bodd x := by
     simp [mod_two_of_bodd, cond]; cases bodd x <;> rfl
   simp only [hn, hm, mod_two_iff_bod, ite_false, bit, bit1, bit0, Bool.cond_eq_ite]
   split_ifs <;> rfl
 
-@[simp]
-lemma bitwise'_of_ne_zero {n m : Nat} (hn : n ≠ 0) (hm : m ≠ 0) :
-    bitwise' f n m = bit (f (bodd n) (bodd m)) (bitwise' f (n / 2) (m / 2)) := by
-  conv_lhs => { rw [←bit_decomp n, ←bit_decomp m] }
-  rw [bitwise'_bit', bit, div2_val, div2_val]
-  case ham =>
-    obtain ⟨⟩ | n := n
-    · contradiction
-    · simp only [div2_succ, cond, bodd_succ, Bool.not_not]
-      cases bodd n <;> simp
-  case hbn =>
-    obtain ⟨⟩ | m := m
-    · contradiction
-    · simp only [div2_succ, cond, bodd_succ, Bool.not_not]
-      cases bodd m <;> simp
-
-lemma bitwise'_eq_bitwise (f) : bitwise' f = bitwise f := by
-  funext x y
-  induction' x using Nat.strongInductionOn with x ih generalizing y
-  cases' x with x <;> cases' y with y
-  · simp only [bitwise_zero, bitwise'_zero]
-  · simp only [bitwise_zero_left, bitwise'_zero_left, Bool.cond_eq_ite]
-  · simp only [bitwise_zero_right, bitwise'_zero_right, Bool.cond_eq_ite]
-  · specialize ih ((x+1) / 2) (div_lt_self' ..)
-    simp only [ne_eq, succ_ne_zero, not_false_eq_true, bitwise'_of_ne_zero, ih, bitwise_of_ne_zero]
-
-theorem lor'_eq_lor : lor' = lor :=
-  bitwise'_eq_bitwise _
-
-theorem land'_eq_land : land' = land :=
-  bitwise'_eq_bitwise _
-
-theorem xor'_eq_xor : lxor' = xor := by
-  unfold lxor' xor
-  have : _root_.xor = bne := by
-    funext x y; cases x <;> cases y <;> rfl
-  rw [this]
-  exact bitwise'_eq_bitwise _
+theorem binaryRec_of_ne_zero {C : Nat → Sort*} (z : C 0) (f : ∀ b n, C n → C (bit b n)) {n}
+    (h : n ≠ 0) :
+    binaryRec z f n = bit_decomp n ▸ f (bodd n) (div2 n) (binaryRec z f (div2 n)) := by
+  rw [Eq.rec_eq_cast]
+  rw [binaryRec]
+  dsimp only
+  rw [dif_neg h, eq_mpr_eq_cast]
 
 @[simp]
 lemma bitwise_bit {f : Bool → Bool → Bool} (h : f false false = false := by rfl) (a m b n) :
     bitwise f (bit a m) (bit b n) = bit (f a b) (bitwise f m n) := by
-  simp only [←bitwise'_eq_bitwise, bitwise'_bit h]
+  conv_lhs => unfold bitwise
+  simp only [bit, bit1, bit0, Bool.cond_eq_ite]
+  have h1 x :     (x + x) % 2 = 0 := by ring_nf; apply mul_mod_left
+  have h2 x : (x + x + 1) % 2 = 1 := by ring_nf; apply add_mul_mod_self_right
+  have h3 x :     (x + x) / 2 = x := by ring_nf; apply mul_div_left _ zero_lt_two
+  have h4 x : (x + x + 1) / 2 = x := by ring_nf; simp [add_mul_div_right]
+  cases a <;> cases b <;> simp [h1, h2, h3, h4] <;> split_ifs <;> simp_all
+#align nat.bitwise_bit Nat.bitwise_bit
+
+lemma bit_mod_two (a : Bool) (x : ℕ) :
+    bit a x % 2 = if a then 1 else 0 := by
+  simp [bit, bit0, bit1, Bool.cond_eq_ite, ←mul_two]
+  split_ifs <;> simp [Nat.add_mod]
+
+@[simp]
+lemma bit_mod_two_eq_zero_iff (a x) :
+    bit a x % 2 = 0 ↔ !a := by
+  rw [bit_mod_two]; split_ifs <;> simp_all
+
+@[simp]
+lemma bit_mod_two_eq_one_iff (a x) :
+    bit a x % 2 = 1 ↔ a := by
+  rw [bit_mod_two]; split_ifs <;> simp_all
 
 @[simp]
 theorem lor_bit : ∀ a m b n, lor (bit a m) (bit b n) = bit (a || b) (lor m n) :=
   bitwise_bit
+#align nat.lor_bit Nat.lor_bit
 
 @[simp]
 theorem land_bit : ∀ a m b n, land (bit a m) (bit b n) = bit (a && b) (land m n) :=
   bitwise_bit
+#align nat.land_bit Nat.land_bit
 
 @[simp]
-theorem lxor_bit : ∀ a m b n, xor (bit a m) (bit b n) = bit (bne a b) (xor m n) :=
+theorem ldiff_bit : ∀ a m b n, ldiff (bit a m) (bit b n) = bit (a && not b) (ldiff m n) :=
   bitwise_bit
+#align nat.ldiff_bit Nat.ldiff_bit
+
+@[simp]
+theorem xor_bit : ∀ a m b n, xor (bit a m) (bit b n) = bit (bne a b) (xor m n) :=
+  bitwise_bit
+#align nat.lxor_bit Nat.xor_bit
+
+@[simp]
+theorem testBit_bitwise {f : Bool → Bool → Bool} (h : f false false = false) (m n k) :
+    testBit (bitwise f m n) k = f (testBit m k) (testBit n k) := by
+  induction' k with k ih generalizing m n
+  <;> cases' m using bitCasesOn with a m
+  <;> cases' n using bitCasesOn with b n
+  <;> rw [bitwise_bit h]
+  · simp [testBit_zero]
+  · simp [testBit_succ, ih]
+#align nat.test_bit_bitwise Nat.testBit_bitwise
+
+@[simp]
+theorem testBit_lor : ∀ m n k, testBit (lor m n) k = (testBit m k || testBit n k) :=
+  testBit_bitwise rfl
+#align nat.test_bit_lor Nat.testBit_lor
+
+@[simp]
+theorem testBit_land : ∀ m n k, testBit (land m n) k = (testBit m k && testBit n k) :=
+  testBit_bitwise rfl
+#align nat.test_bit_land Nat.testBit_land
+
+@[simp]
+theorem testBit_ldiff : ∀ m n k, testBit (ldiff m n) k = (testBit m k && not (testBit n k)) :=
+  testBit_bitwise rfl
+#align nat.test_bit_ldiff Nat.testBit_ldiff
+
+@[simp]
+theorem testBit_xor : ∀ m n k, testBit (xor m n) k = bne (testBit m k) (testBit n k) :=
+  testBit_bitwise rfl
+#align nat.test_bit_lxor Nat.testBit_xor
 
 end
 
@@ -158,6 +177,39 @@ theorem bit_eq_zero {n : ℕ} {b : Bool} : n.bit b = 0 ↔ n = 0 ∧ b = false :
   cases b <;> simp [Nat.bit0_eq_zero, Nat.bit1_ne_zero]
 #align nat.bit_eq_zero Nat.bit_eq_zero
 
+theorem bit_ne_zero_iff {n : ℕ} {b : Bool} : n.bit b ≠ 0 ↔ n = 0 → b = true := by
+  simpa only [not_and, Bool.not_eq_false] using (@bit_eq_zero n b).not
+
+/-- 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`) -/
+lemma bitwise_bit' {f : Bool → Bool → Bool} (a : Bool) (m : Nat) (b : Bool) (n : Nat)
+    (ham : m = 0 → a = true) (hbn : n = 0 → b = true) :
+    bitwise f (bit a m) (bit b n) = bit (f a b) (bitwise f m n) := by
+  conv_lhs => unfold bitwise
+  rw [←bit_ne_zero_iff] at ham hbn
+  simp only [ham, hbn, bit_mod_two_eq_one_iff, Bool.decide_coe, ← div2_val, div2_bit, ne_eq,
+    ite_false]
+  conv_rhs => simp only [bit, bit1, bit0, Bool.cond_eq_ite]
+  split_ifs with hf <;> rfl
+
+lemma bitwise_eq_binaryRec (f : Bool → Bool → Bool) :
+    bitwise f =
+    binaryRec (fun n => cond (f false true) n 0) fun a m Ia =>
+      binaryRec (cond (f true false) (bit a m) 0) fun b n _ => bit (f a b) (Ia n) := by
+  funext x y
+  induction x using binaryRec' generalizing y with
+  | z => simp only [bitwise_zero_left, binaryRec_zero, Bool.cond_eq_ite]
+  | f xb x hxb ih =>
+    rw [←bit_ne_zero_iff] at hxb
+    simp_rw [binaryRec_of_ne_zero _ _ hxb, bodd_bit, div2_bit, eq_rec_constant]
+    induction y using binaryRec' with
+    | z => simp only [bitwise_zero_right, binaryRec_zero, Bool.cond_eq_ite]
+    | f yb y hyb =>
+      rw [←bit_ne_zero_iff] at hyb
+      simp_rw [binaryRec_of_ne_zero _ _ hyb, bitwise_of_ne_zero hxb hyb, bodd_bit, ←div2_val,
+        div2_bit, eq_rec_constant, ih]
+
 theorem zero_of_testBit_eq_false {n : ℕ} (h : ∀ i, testBit n i = false) : n = 0 := by
   induction' n using Nat.binaryRec with b n hn
   · rfl
@@ -260,65 +312,68 @@ theorem testBit_two_pow (n m : ℕ) : testBit (2 ^ n) m = (n = m) := by
     simp [h]
 #align nat.test_bit_two_pow Nat.testBit_two_pow
 
-theorem bitwise'_swap {f : Bool → Bool → Bool} (h : f false false = false) :
-    bitwise' (Function.swap f) = Function.swap (bitwise' f) := by
-  funext m n; revert n
-  dsimp [Function.swap]
-  apply binaryRec _ _ m <;> intro n
-  · rw [bitwise'_zero_left, bitwise'_zero_right, Bool.cond_eq_ite]
-  · intros a ih m'
-    apply bitCasesOn m'; intro b n'
-    rw [bitwise'_bit, bitwise'_bit, ih] <;> exact h
-#align nat.bitwise_swap Nat.bitwise'_swap
+theorem bitwise_swap {f : Bool → Bool → Bool} :
+    bitwise (Function.swap f) = Function.swap (bitwise f) := by
+  funext m n
+  simp only [Function.swap]
+  induction' m using Nat.strongInductionOn with m ih generalizing n
+  cases' m with m
+  <;> cases' n with n
+  <;> try rw [bitwise_zero_left, bitwise_zero_right]
+  · specialize ih ((m+1) / 2) (div_lt_self' ..)
+    simp [bitwise_of_ne_zero, ih]
+#align nat.bitwise_swap Nat.bitwise_swap
 
 /-- If `f` is a commutative operation on bools such that `f false false = false`, then `bitwise f`
     is also commutative. -/
-theorem bitwise'_comm {f : Bool → Bool → Bool} (hf : ∀ b b', f b b' = f b' b)
-    (hf' : f false false = false) (n m : ℕ) : bitwise' f n m = bitwise' f m n :=
-  suffices bitwise' f = swap (bitwise' f) by conv_lhs => rw [this]
+theorem bitwise_comm {f : Bool → Bool → Bool} (hf : ∀ b b', f b b' = f b' b) (n m : ℕ) :
+    bitwise f n m = bitwise f m n :=
+  suffices bitwise f = swap (bitwise f) by conv_lhs => rw [this]
   calc
-    bitwise' f = bitwise' (swap f) := congr_arg _ <| funext fun _ => funext <| hf _
-    _ = swap (bitwise' f) := bitwise'_swap hf'
-#align nat.bitwise_comm Nat.bitwise'_comm
+    bitwise f = bitwise (swap f) := congr_arg _ <| funext fun _ => funext <| hf _
+    _ = swap (bitwise f) := bitwise_swap
+#align nat.bitwise_comm Nat.bitwise_comm
 
-theorem lor'_comm (n m : ℕ) : lor' n m = lor' m n :=
-  bitwise'_comm Bool.or_comm rfl n m
-#align nat.lor_comm Nat.lor'_comm
+theorem lor_comm (n m : ℕ) : lor n m = lor m n :=
+  bitwise_comm Bool.or_comm n m
+#align nat.lor_comm Nat.lor_comm
 
-theorem land'_comm (n m : ℕ) : land' n m = land' m n :=
-  bitwise'_comm Bool.and_comm rfl n m
-#align nat.land_comm Nat.land'_comm
+theorem land_comm (n m : ℕ) : land n m = land m n :=
+  bitwise_comm Bool.and_comm n m
+#align nat.land_comm Nat.land_comm
 
-theorem lxor'_comm (n m : ℕ) : lxor' n m = lxor' m n :=
-  bitwise'_comm Bool.xor_comm rfl n m
-#align nat.lxor_comm Nat.lxor'_comm
+theorem xor_comm (n m : ℕ) : xor n m = xor m n :=
+  bitwise_comm (Bool.bne_eq_xor ▸ Bool.xor_comm) n m
+#align nat.lxor_comm Nat.xor_comm
 
 @[simp]
-theorem zero_lxor' (n : ℕ) : lxor' 0 n = n := by
- simp only [Bool.xor_false_left, Nat.bitwise'_zero_left, eq_self_iff_true, Bool.cond_true, lxor']
-#align nat.zero_lxor Nat.zero_lxor'
+theorem zero_xor (n : ℕ) : xor 0 n = n := by
+ simp only [xor, bitwise_zero_left, ite_true]
+#align nat.zero_lxor Nat.zero_xor
 
 @[simp]
-theorem lxor'_zero (n : ℕ) : lxor' n 0 = n := by simp [lxor']
-#align nat.lxor_zero Nat.lxor'_zero
+theorem xor_zero (n : ℕ) : xor n 0 = n := by simp [xor]
+#align nat.lxor_zero Nat.xor_zero
 
 @[simp]
-theorem zero_land' (n : ℕ) : land' 0 n = 0 := by
-  simp only [Nat.bitwise'_zero_left, Bool.cond_false, eq_self_iff_true, land', Bool.false_and]
-#align nat.zero_land Nat.zero_land'
+theorem zero_land (n : ℕ) : land 0 n = 0 := by
+  simp only [land, bitwise_zero_left, ite_false];
+#align nat.zero_land Nat.zero_land
 
 @[simp]
-theorem land'_zero (n : ℕ) : land' n 0 = 0 := by simp [land']
-#align nat.land_zero Nat.land'_zero
+theorem land_zero (n : ℕ) : land n 0 = 0 := by
+  simp only [land, bitwise_zero_right, ite_false]
+#align nat.land_zero Nat.land_zero
 
 @[simp]
-theorem zero_lor' (n : ℕ) : lor' 0 n = n := by --simp [lor']
-  simp only [Nat.bitwise'_zero_left, Bool.false_or, eq_self_iff_true, Bool.cond_true, Nat.lor']
-#align nat.zero_lor Nat.zero_lor'
+theorem zero_lor (n : ℕ) : lor 0 n = n := by
+  simp only [lor, bitwise_zero_left, ite_true]
+#align nat.zero_lor Nat.zero_lor
 
 @[simp]
-theorem lor'_zero (n : ℕ) : lor' n 0 = n := by simp [lor']
-#align nat.lor_zero Nat.lor'_zero
+theorem lor_zero (n : ℕ) : lor n 0 = n := by
+  simp only [lor, bitwise_zero_right, ite_true]
+#align nat.lor_zero Nat.lor_zero
 
 
 /-- Proving associativity of bitwise operations in general essentially boils down to a huge case
@@ -331,81 +386,81 @@ macro "bitwise_assoc_tac" : tactic => set_option hygiene false in `(tactic| (
   induction' k using Nat.binaryRec with b'' k hk
   -- Porting note: was `simp [hn]`
   -- This is necessary because these are simp lemmas in mathlib
-  <;> simp [hn, Bool.or_assoc, Bool.and_assoc]))
+  <;> simp [hn, Bool.or_assoc, Bool.and_assoc, Bool.bne_eq_xor]))
 
-theorem lxor'_assoc (n m k : ℕ) : lxor' (lxor' n m) k = lxor' n (lxor' m k) := by bitwise_assoc_tac
-#align nat.lxor_assoc Nat.lxor'_assoc
+theorem xor_assoc (n m k : ℕ) : xor (xor n m) k = xor n (xor m k) := by bitwise_assoc_tac
+#align nat.lxor_assoc Nat.xor_assoc
 
-theorem land'_assoc (n m k : ℕ) : land' (land' n m) k = land' n (land' m k) := by bitwise_assoc_tac
-#align nat.land_assoc Nat.land'_assoc
+theorem land_assoc (n m k : ℕ) : land (land n m) k = land n (land m k) := by bitwise_assoc_tac
+#align nat.land_assoc Nat.land_assoc
 
-theorem lor'_assoc (n m k : ℕ) : lor' (lor' n m) k = lor' n (lor' m k) := by bitwise_assoc_tac
-#align nat.lor_assoc Nat.lor'_assoc
+theorem lor_assoc (n m k : ℕ) : lor (lor n m) k = lor n (lor m k) := by bitwise_assoc_tac
+#align nat.lor_assoc Nat.lor_assoc
 
 @[simp]
-theorem lxor'_self (n : ℕ) : lxor' n n = 0 :=
+theorem xor_self (n : ℕ) : xor n n = 0 :=
   zero_of_testBit_eq_false fun i => by simp
-#align nat.lxor_self Nat.lxor'_self
+#align nat.lxor_self Nat.xor_self
 
 -- These lemmas match `mul_inv_cancel_right` and `mul_inv_cancel_left`.
-theorem lxor_cancel_right (n m : ℕ) : lxor' (lxor' m n) n = m := by
-  rw [lxor'_assoc, lxor'_self, lxor'_zero]
+theorem lxor_cancel_right (n m : ℕ) : xor (xor m n) n = m := by
+  rw [xor_assoc, xor_self, xor_zero]
 #align nat.lxor_cancel_right Nat.lxor_cancel_right
 
-theorem lxor'_cancel_left (n m : ℕ) : lxor' n (lxor' n m) = m := by
-  rw [← lxor'_assoc, lxor'_self, zero_lxor']
-#align nat.lxor_cancel_left Nat.lxor'_cancel_left
+theorem xor_cancel_left (n m : ℕ) : xor n (xor n m) = m := by
+  rw [← xor_assoc, xor_self, zero_xor]
+#align nat.lxor_cancel_left Nat.xor_cancel_left
 
-theorem lxor'_right_injective {n : ℕ} : Function.Injective (lxor' n) := fun m m' h => by
-  rw [← lxor'_cancel_left n m, ← lxor'_cancel_left n m', h]
-#align nat.lxor_right_injective Nat.lxor'_right_injective
+theorem xor_right_injective {n : ℕ} : Function.Injective (xor n) := fun m m' h => by
+  rw [← xor_cancel_left n m, ← xor_cancel_left n m', h]
+#align nat.lxor_right_injective Nat.xor_right_injective
 
-theorem lxor'_left_injective {n : ℕ} : Function.Injective fun m => lxor' m n :=
-  fun m m' (h : lxor' m n = lxor' m' n) => by
+theorem xor_left_injective {n : ℕ} : Function.Injective fun m => xor m n :=
+  fun m m' (h : xor m n = xor m' n) => by
   rw [← lxor_cancel_right n m, ← lxor_cancel_right n m', h]
-#align nat.lxor_left_injective Nat.lxor'_left_injective
+#align nat.lxor_left_injective Nat.xor_left_injective
 
 @[simp]
-theorem lxor'_right_inj {n m m' : ℕ} : lxor' n m = lxor' n m' ↔ m = m' :=
-  lxor'_right_injective.eq_iff
-#align nat.lxor_right_inj Nat.lxor'_right_inj
+theorem xor_right_inj {n m m' : ℕ} : xor n m = xor n m' ↔ m = m' :=
+  xor_right_injective.eq_iff
+#align nat.lxor_right_inj Nat.xor_right_inj
 
 @[simp]
-theorem lxor'_left_inj {n m m' : ℕ} : lxor' m n = lxor' m' n ↔ m = m' :=
-  lxor'_left_injective.eq_iff
-#align nat.lxor_left_inj Nat.lxor'_left_inj
+theorem xor_left_inj {n m m' : ℕ} : xor m n = xor m' n ↔ m = m' :=
+  xor_left_injective.eq_iff
+#align nat.lxor_left_inj Nat.xor_left_inj
 
 @[simp]
-theorem lxor'_eq_zero {n m : ℕ} : lxor' n m = 0 ↔ n = m := by
-  rw [← lxor'_self n, lxor'_right_inj, eq_comm]
-#align nat.lxor_eq_zero Nat.lxor'_eq_zero
+theorem xor_eq_zero {n m : ℕ} : xor n m = 0 ↔ n = m := by
+  rw [← xor_self n, xor_right_inj, eq_comm]
+#align nat.lxor_eq_zero Nat.xor_eq_zero
 
-theorem lxor'_ne_zero {n m : ℕ} : lxor' n m ≠ 0 ↔ n ≠ m :=
-  lxor'_eq_zero.not
-#align nat.lxor_ne_zero Nat.lxor'_ne_zero
+theorem xor_ne_zero {n m : ℕ} : xor n m ≠ 0 ↔ n ≠ m :=
+  xor_eq_zero.not
+#align nat.lxor_ne_zero Nat.xor_ne_zero
 
-theorem lxor'_trichotomy {a b c : ℕ} (h : a ≠ lxor' b c) :
-    lxor' b c < a ∨ lxor' a c < b ∨ lxor' a b < c := by
-  set v := lxor' a (lxor' b c) with hv
+theorem xor_trichotomy {a b c : ℕ} (h : a ≠ xor b c) :
+    xor b c < a ∨ xor a c < b ∨ xor a b < c := by
+  set v := xor a (xor b c) with hv
   -- The xor of any two of `a`, `b`, `c` is the xor of `v` and the third.
-  have hab : lxor' a b = lxor' c v := by
+  have hab : xor a b = xor c v := by
     rw [hv]
     conv_rhs =>
-      rw [lxor'_comm]
-      simp [lxor'_assoc]
-  have hac : lxor' a c = lxor' b v := by
+      rw [xor_comm]
+      simp [xor_assoc]
+  have hac : xor a c = xor b v := by
     rw [hv]
     conv_rhs =>
       right
-      rw [← lxor'_comm]
-    rw [← lxor'_assoc, ← lxor'_assoc, lxor'_self, zero_lxor', lxor'_comm]
-  have hbc : lxor' b c = lxor' a v := by simp [hv, ← lxor'_assoc]
+      rw [← xor_comm]
+    rw [← xor_assoc, ← xor_assoc, xor_self, zero_xor, xor_comm]
+  have hbc : xor b c = xor a v := by simp [hv, ← xor_assoc]
   -- If `i` is the position of the most significant bit of `v`, then at least one of `a`, `b`, `c`
   -- has a one bit at position `i`.
-  obtain ⟨i, ⟨hi, hi'⟩⟩ := exists_most_significant_bit (lxor'_ne_zero.2 h)
+  obtain ⟨i, ⟨hi, hi'⟩⟩ := exists_most_significant_bit (xor_ne_zero.2 h)
   have : testBit a i = true ∨ testBit b i = true ∨ testBit c i = true := by
     contrapose! hi
-    simp only [Bool.eq_false_eq_not_eq_true, Ne, testBit_lxor'] at hi ⊢
+    simp only [Bool.eq_false_eq_not_eq_true, Ne, testBit_xor, Bool.bne_eq_xor] at hi ⊢
     rw [hi.1, hi.2.1, hi.2.2, Bool.xor_false, Bool.xor_false]
   -- If, say, `a` has a one bit at position `i`, then `a xor v` has a zero bit at position `i`, but
   -- the same bits as `a` in positions greater than `j`, so `a xor v < a`.
@@ -416,16 +471,16 @@ theorem lxor'_trichotomy {a b c : ℕ} (h : a ≠ lxor' b c) :
   all_goals
     exact lt_of_testBit i (by
       -- Porting note: this was originally `simp [h, hi]`
-      rw [Nat.testBit_lxor', h, Bool.true_xor,hi]
+      rw [Nat.testBit_xor, h, Bool.bne_eq_xor, Bool.true_xor,hi]
       rfl
     ) h fun j hj => by
       -- Porting note: this was originally `simp [hi' _ hj]`
-      rw [Nat.testBit_lxor', hi' _ hj, Bool.xor_false_right, eq_self_iff_true]
+      rw [Nat.testBit_xor, hi' _ hj, Bool.bne_eq_xor, Bool.xor_false_right, eq_self_iff_true]
       trivial
-#align nat.lxor_trichotomy Nat.lxor'_trichotomy
+#align nat.lxor_trichotomy Nat.xor_trichotomy
 
-theorem lt_lxor'_cases {a b c : ℕ} (h : a < lxor' b c) : lxor' a c < b ∨ lxor' a b < c :=
-  (or_iff_right fun h' => (h.asymm h').elim).1 <| lxor'_trichotomy h.ne
-#align nat.lt_lxor_cases Nat.lt_lxor'_cases
+theorem lt_xor_cases {a b c : ℕ} (h : a < xor b c) : xor a c < b ∨ xor a b < c :=
+  (or_iff_right fun h' => (h.asymm h').elim).1 <| xor_trichotomy h.ne
+#align nat.lt_lxor_cases Nat.lt_xor_cases
 
 end Nat

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -217,7 +217,7 @@ theorem lt_of_testBit {n m : ℕ} (i : ℕ) (hn : testBit n i = false) (hm : tes
     rw [le_zero_iff] at hm
     simp [hm]
   induction' m using Nat.binaryRec with b' m hm' generalizing i
-  · exact False.elim (Bool.ff_ne_tt ((zero_testBit i).symm.trans hm))
+  · exact False.elim (Bool.false_ne_true ((zero_testBit i).symm.trans hm))
   by_cases hi : i = 0
   · subst hi
     simp only [testBit_zero] at hn hm

This PR proves that Nat.bitwise (from core) and Nat.bitwise' (from mathlib) are equal

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>