773 by (simp only: div_mult2_eq') |
773 by (simp only: div_mult2_eq') |
774 finally show ?thesis |
774 finally show ?thesis |
775 using False by (simp add: take_bit_eq_mod drop_bit_eq_div) |
775 using False by (simp add: take_bit_eq_mod drop_bit_eq_div) |
776 qed |
776 qed |
777 |
777 |
|
778 lemma push_bit_0_id [simp]: |
|
779 "push_bit 0 = id" |
|
780 by (simp add: fun_eq_iff push_bit_eq_mult) |
|
781 |
|
782 lemma push_bit_of_0 [simp]: |
|
783 "push_bit n 0 = 0" |
|
784 by (simp add: push_bit_eq_mult) |
|
785 |
|
786 lemma push_bit_of_1: |
|
787 "push_bit n 1 = 2 ^ n" |
|
788 by (simp add: push_bit_eq_mult) |
|
789 |
|
790 lemma push_bit_Suc [simp]: |
|
791 "push_bit (Suc n) a = push_bit n (a * 2)" |
|
792 by (simp add: push_bit_eq_mult ac_simps) |
|
793 |
|
794 lemma push_bit_double: |
|
795 "push_bit n (a * 2) = push_bit n a * 2" |
|
796 by (simp add: push_bit_eq_mult ac_simps) |
|
797 |
|
798 lemma push_bit_eq_0_iff [simp]: |
|
799 "push_bit n a = 0 \<longleftrightarrow> a = 0" |
|
800 by (simp add: push_bit_eq_mult) |
|
801 |
|
802 lemma push_bit_add: |
|
803 "push_bit n (a + b) = push_bit n a + push_bit n b" |
|
804 by (simp add: push_bit_eq_mult algebra_simps) |
|
805 |
|
806 lemma push_bit_numeral [simp]: |
|
807 "push_bit (numeral l) (numeral k) = push_bit (pred_numeral l) (numeral (Num.Bit0 k))" |
|
808 by (simp only: numeral_eq_Suc power_Suc numeral_Bit0 [of k] mult_2 [symmetric]) (simp add: ac_simps) |
|
809 |
778 lemma take_bit_0 [simp]: |
810 lemma take_bit_0 [simp]: |
779 "take_bit 0 a = 0" |
811 "take_bit 0 a = 0" |
780 by (simp add: take_bit_eq_mod) |
812 by (simp add: take_bit_eq_mod) |
781 |
813 |
782 lemma take_bit_Suc [simp]: |
814 lemma take_bit_Suc [simp]: |
794 |
826 |
795 lemma take_bit_of_0 [simp]: |
827 lemma take_bit_of_0 [simp]: |
796 "take_bit n 0 = 0" |
828 "take_bit n 0 = 0" |
797 by (simp add: take_bit_eq_mod) |
829 by (simp add: take_bit_eq_mod) |
798 |
830 |
|
831 lemma take_bit_of_1 [simp]: |
|
832 "take_bit n 1 = of_bool (n > 0)" |
|
833 by (simp add: take_bit_eq_mod) |
|
834 |
799 lemma take_bit_add: |
835 lemma take_bit_add: |
800 "take_bit n (take_bit n a + take_bit n b) = take_bit n (a + b)" |
836 "take_bit n (take_bit n a + take_bit n b) = take_bit n (a + b)" |
801 by (simp add: take_bit_eq_mod mod_simps) |
837 by (simp add: take_bit_eq_mod mod_simps) |
802 |
838 |
803 lemma take_bit_eq_0_iff: |
839 lemma take_bit_eq_0_iff: |
806 |
842 |
807 lemma take_bit_of_1_eq_0_iff [simp]: |
843 lemma take_bit_of_1_eq_0_iff [simp]: |
808 "take_bit n 1 = 0 \<longleftrightarrow> n = 0" |
844 "take_bit n 1 = 0 \<longleftrightarrow> n = 0" |
809 by (simp add: take_bit_eq_mod) |
845 by (simp add: take_bit_eq_mod) |
810 |
846 |
811 lemma push_bit_eq_0_iff [simp]: |
847 lemma even_take_bit_eq [simp]: |
812 "push_bit n a = 0 \<longleftrightarrow> a = 0" |
848 "even (take_bit n a) \<longleftrightarrow> n = 0 \<or> even a" |
813 by (simp add: push_bit_eq_mult) |
849 by (cases n) (simp_all add: take_bit_eq_mod dvd_mod_iff) |
814 |
850 |
815 lemma push_bit_add: |
851 lemma take_bit_numeral_bit0 [simp]: |
816 "push_bit n (a + b) = push_bit n a + push_bit n b" |
852 "take_bit (numeral l) (numeral (Num.Bit0 k)) = take_bit (pred_numeral l) (numeral k) * 2" |
817 by (simp add: push_bit_eq_mult algebra_simps) |
853 by (simp only: numeral_eq_Suc power_Suc numeral_Bit0 [of k] mult_2 [symmetric] take_bit_Suc |
|
854 ac_simps even_mult_iff nonzero_mult_div_cancel_right [OF numeral_neq_zero]) simp |
|
855 |
|
856 lemma take_bit_numeral_bit1 [simp]: |
|
857 "take_bit (numeral l) (numeral (Num.Bit1 k)) = take_bit (pred_numeral l) (numeral k) * 2 + 1" |
|
858 by (simp only: numeral_eq_Suc power_Suc numeral_Bit1 [of k] mult_2 [symmetric] take_bit_Suc |
|
859 ac_simps even_add even_mult_iff div_mult_self1 [OF numeral_neq_zero]) (simp add: ac_simps) |
818 |
860 |
819 lemma drop_bit_0 [simp]: |
861 lemma drop_bit_0 [simp]: |
820 "drop_bit 0 = id" |
862 "drop_bit 0 = id" |
821 by (simp add: fun_eq_iff drop_bit_eq_div) |
863 by (simp add: fun_eq_iff drop_bit_eq_div) |
822 |
864 |
823 lemma drop_bit_of_0 [simp]: |
865 lemma drop_bit_of_0 [simp]: |
824 "drop_bit n 0 = 0" |
866 "drop_bit n 0 = 0" |
|
867 by (simp add: drop_bit_eq_div) |
|
868 |
|
869 lemma drop_bit_of_1 [simp]: |
|
870 "drop_bit n 1 = of_bool (n = 0)" |
825 by (simp add: drop_bit_eq_div) |
871 by (simp add: drop_bit_eq_div) |
826 |
872 |
827 lemma drop_bit_Suc [simp]: |
873 lemma drop_bit_Suc [simp]: |
828 "drop_bit (Suc n) a = drop_bit n (a div 2)" |
874 "drop_bit (Suc n) a = drop_bit n (a div 2)" |
829 proof (cases "even a") |
875 proof (cases "even a") |
849 |
895 |
850 lemma drop_bit_of_bool [simp]: |
896 lemma drop_bit_of_bool [simp]: |
851 "drop_bit n (of_bool d) = of_bool (n = 0 \<and> d)" |
897 "drop_bit n (of_bool d) = of_bool (n = 0 \<and> d)" |
852 by (cases n) simp_all |
898 by (cases n) simp_all |
853 |
899 |
854 lemma even_take_bit_eq [simp]: |
900 lemma drop_bit_numeral_bit0 [simp]: |
855 "even (take_bit n a) \<longleftrightarrow> n = 0 \<or> even a" |
901 "drop_bit (numeral l) (numeral (Num.Bit0 k)) = drop_bit (pred_numeral l) (numeral k)" |
856 by (cases n) (simp_all add: take_bit_eq_mod dvd_mod_iff) |
902 by (simp only: numeral_eq_Suc power_Suc numeral_Bit0 [of k] mult_2 [symmetric] drop_bit_Suc |
857 |
903 nonzero_mult_div_cancel_left [OF numeral_neq_zero]) |
858 lemma push_bit_0_id [simp]: |
904 |
859 "push_bit 0 = id" |
905 lemma drop_bit_numeral_bit1 [simp]: |
860 by (simp add: fun_eq_iff push_bit_eq_mult) |
906 "drop_bit (numeral l) (numeral (Num.Bit1 k)) = drop_bit (pred_numeral l) (numeral k)" |
861 |
907 by (simp only: numeral_eq_Suc power_Suc numeral_Bit1 [of k] mult_2 [symmetric] drop_bit_Suc |
862 lemma push_bit_of_0 [simp]: |
908 div_mult_self4 [OF numeral_neq_zero]) simp |
863 "push_bit n 0 = 0" |
|
864 by (simp add: push_bit_eq_mult) |
|
865 |
|
866 lemma push_bit_of_1: |
|
867 "push_bit n 1 = 2 ^ n" |
|
868 by (simp add: push_bit_eq_mult) |
|
869 |
|
870 lemma push_bit_Suc [simp]: |
|
871 "push_bit (Suc n) a = push_bit n (a * 2)" |
|
872 by (simp add: push_bit_eq_mult ac_simps) |
|
873 |
|
874 lemma push_bit_double: |
|
875 "push_bit n (a * 2) = push_bit n a * 2" |
|
876 by (simp add: push_bit_eq_mult ac_simps) |
|
877 |
909 |
878 end |
910 end |
879 |
911 |
|
912 lemma push_bit_of_Suc_0 [simp]: |
|
913 "push_bit n (Suc 0) = 2 ^ n" |
|
914 using push_bit_of_1 [where ?'a = nat] by simp |
|
915 |
|
916 lemma take_bit_of_Suc_0 [simp]: |
|
917 "take_bit n (Suc 0) = of_bool (0 < n)" |
|
918 using take_bit_of_1 [where ?'a = nat] by simp |
|
919 |
|
920 lemma drop_bit_of_Suc_0 [simp]: |
|
921 "drop_bit n (Suc 0) = of_bool (n = 0)" |
|
922 using drop_bit_of_1 [where ?'a = nat] by simp |
|
923 |
880 end |
924 end |