608 done |
608 done |
609 qed (auto simp add: zdiv_zmult2_eq zmod_zmult2_eq power_add power_diff not_le bit_int_def) |
609 qed (auto simp add: zdiv_zmult2_eq zmod_zmult2_eq power_add power_diff not_le bit_int_def) |
610 |
610 |
611 end |
611 end |
612 |
612 |
613 class semiring_bit_shifts = semiring_bits + |
|
614 fixes push_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
|
615 assumes push_bit_eq_mult: \<open>push_bit n a = a * 2 ^ n\<close> |
|
616 fixes drop_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
|
617 assumes drop_bit_eq_div: \<open>drop_bit n a = a div 2 ^ n\<close> |
|
618 fixes take_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
|
619 assumes take_bit_eq_mod: \<open>take_bit n a = a mod 2 ^ n\<close> |
|
620 begin |
|
621 |
|
622 text \<open> |
|
623 Logically, \<^const>\<open>push_bit\<close>, |
|
624 \<^const>\<open>drop_bit\<close> and \<^const>\<open>take_bit\<close> are just aliases; having them |
|
625 as separate operations makes proofs easier, otherwise proof automation |
|
626 would fiddle with concrete expressions \<^term>\<open>2 ^ n\<close> in a way obfuscating the basic |
|
627 algebraic relationships between those operations. |
|
628 Having |
|
629 them as definitional class operations |
|
630 takes into account that specific instances of these can be implemented |
|
631 differently wrt. code generation. |
|
632 \<close> |
|
633 |
|
634 lemma bit_iff_odd_drop_bit: |
|
635 \<open>bit a n \<longleftrightarrow> odd (drop_bit n a)\<close> |
|
636 by (simp add: bit_iff_odd drop_bit_eq_div) |
|
637 |
|
638 lemma even_drop_bit_iff_not_bit: |
|
639 \<open>even (drop_bit n a) \<longleftrightarrow> \<not> bit a n\<close> |
|
640 by (simp add: bit_iff_odd_drop_bit) |
|
641 |
|
642 lemma div_push_bit_of_1_eq_drop_bit: |
|
643 \<open>a div push_bit n 1 = drop_bit n a\<close> |
|
644 by (simp add: push_bit_eq_mult drop_bit_eq_div) |
|
645 |
|
646 lemma bits_ident: |
|
647 "push_bit n (drop_bit n a) + take_bit n a = a" |
|
648 using div_mult_mod_eq by (simp add: push_bit_eq_mult take_bit_eq_mod drop_bit_eq_div) |
|
649 |
|
650 lemma push_bit_push_bit [simp]: |
|
651 "push_bit m (push_bit n a) = push_bit (m + n) a" |
|
652 by (simp add: push_bit_eq_mult power_add ac_simps) |
|
653 |
|
654 lemma push_bit_0_id [simp]: |
|
655 "push_bit 0 = id" |
|
656 by (simp add: fun_eq_iff push_bit_eq_mult) |
|
657 |
|
658 lemma push_bit_of_0 [simp]: |
|
659 "push_bit n 0 = 0" |
|
660 by (simp add: push_bit_eq_mult) |
|
661 |
|
662 lemma push_bit_of_1: |
|
663 "push_bit n 1 = 2 ^ n" |
|
664 by (simp add: push_bit_eq_mult) |
|
665 |
|
666 lemma push_bit_Suc [simp]: |
|
667 "push_bit (Suc n) a = push_bit n (a * 2)" |
|
668 by (simp add: push_bit_eq_mult ac_simps) |
|
669 |
|
670 lemma push_bit_double: |
|
671 "push_bit n (a * 2) = push_bit n a * 2" |
|
672 by (simp add: push_bit_eq_mult ac_simps) |
|
673 |
|
674 lemma push_bit_add: |
|
675 "push_bit n (a + b) = push_bit n a + push_bit n b" |
|
676 by (simp add: push_bit_eq_mult algebra_simps) |
|
677 |
|
678 lemma push_bit_numeral [simp]: |
|
679 \<open>push_bit (numeral l) (numeral k) = push_bit (pred_numeral l) (numeral (Num.Bit0 k))\<close> |
|
680 by (simp add: numeral_eq_Suc mult_2_right) (simp add: numeral_Bit0) |
|
681 |
|
682 lemma take_bit_0 [simp]: |
|
683 "take_bit 0 a = 0" |
|
684 by (simp add: take_bit_eq_mod) |
|
685 |
|
686 lemma take_bit_Suc: |
|
687 \<open>take_bit (Suc n) a = take_bit n (a div 2) * 2 + a mod 2\<close> |
|
688 proof - |
|
689 have \<open>take_bit (Suc n) (a div 2 * 2 + of_bool (odd a)) = take_bit n (a div 2) * 2 + of_bool (odd a)\<close> |
|
690 using even_succ_mod_exp [of \<open>2 * (a div 2)\<close> \<open>Suc n\<close>] |
|
691 mult_exp_mod_exp_eq [of 1 \<open>Suc n\<close> \<open>a div 2\<close>] |
|
692 by (auto simp add: take_bit_eq_mod ac_simps) |
|
693 then show ?thesis |
|
694 using div_mult_mod_eq [of a 2] by (simp add: mod_2_eq_odd) |
|
695 qed |
|
696 |
|
697 lemma take_bit_rec: |
|
698 \<open>take_bit n a = (if n = 0 then 0 else take_bit (n - 1) (a div 2) * 2 + a mod 2)\<close> |
|
699 by (cases n) (simp_all add: take_bit_Suc) |
|
700 |
|
701 lemma take_bit_Suc_0 [simp]: |
|
702 \<open>take_bit (Suc 0) a = a mod 2\<close> |
|
703 by (simp add: take_bit_eq_mod) |
|
704 |
|
705 lemma take_bit_of_0 [simp]: |
|
706 "take_bit n 0 = 0" |
|
707 by (simp add: take_bit_eq_mod) |
|
708 |
|
709 lemma take_bit_of_1 [simp]: |
|
710 "take_bit n 1 = of_bool (n > 0)" |
|
711 by (cases n) (simp_all add: take_bit_Suc) |
|
712 |
|
713 lemma drop_bit_of_0 [simp]: |
|
714 "drop_bit n 0 = 0" |
|
715 by (simp add: drop_bit_eq_div) |
|
716 |
|
717 lemma drop_bit_of_1 [simp]: |
|
718 "drop_bit n 1 = of_bool (n = 0)" |
|
719 by (simp add: drop_bit_eq_div) |
|
720 |
|
721 lemma drop_bit_0 [simp]: |
|
722 "drop_bit 0 = id" |
|
723 by (simp add: fun_eq_iff drop_bit_eq_div) |
|
724 |
|
725 lemma drop_bit_Suc: |
|
726 "drop_bit (Suc n) a = drop_bit n (a div 2)" |
|
727 using div_exp_eq [of a 1] by (simp add: drop_bit_eq_div) |
|
728 |
|
729 lemma drop_bit_rec: |
|
730 "drop_bit n a = (if n = 0 then a else drop_bit (n - 1) (a div 2))" |
|
731 by (cases n) (simp_all add: drop_bit_Suc) |
|
732 |
|
733 lemma drop_bit_half: |
|
734 "drop_bit n (a div 2) = drop_bit n a div 2" |
|
735 by (induction n arbitrary: a) (simp_all add: drop_bit_Suc) |
|
736 |
|
737 lemma drop_bit_of_bool [simp]: |
|
738 "drop_bit n (of_bool b) = of_bool (n = 0 \<and> b)" |
|
739 by (cases n) simp_all |
|
740 |
|
741 lemma even_take_bit_eq [simp]: |
|
742 \<open>even (take_bit n a) \<longleftrightarrow> n = 0 \<or> even a\<close> |
|
743 by (simp add: take_bit_rec [of n a]) |
|
744 |
|
745 lemma take_bit_take_bit [simp]: |
|
746 "take_bit m (take_bit n a) = take_bit (min m n) a" |
|
747 by (simp add: take_bit_eq_mod mod_exp_eq ac_simps) |
|
748 |
|
749 lemma drop_bit_drop_bit [simp]: |
|
750 "drop_bit m (drop_bit n a) = drop_bit (m + n) a" |
|
751 by (simp add: drop_bit_eq_div power_add div_exp_eq ac_simps) |
|
752 |
|
753 lemma push_bit_take_bit: |
|
754 "push_bit m (take_bit n a) = take_bit (m + n) (push_bit m a)" |
|
755 apply (simp add: push_bit_eq_mult take_bit_eq_mod power_add ac_simps) |
|
756 using mult_exp_mod_exp_eq [of m \<open>m + n\<close> a] apply (simp add: ac_simps power_add) |
|
757 done |
|
758 |
|
759 lemma take_bit_push_bit: |
|
760 "take_bit m (push_bit n a) = push_bit n (take_bit (m - n) a)" |
|
761 proof (cases "m \<le> n") |
|
762 case True |
|
763 then show ?thesis |
|
764 apply (simp add:) |
|
765 apply (simp_all add: push_bit_eq_mult take_bit_eq_mod) |
|
766 apply (auto dest!: le_Suc_ex simp add: power_add ac_simps) |
|
767 using mult_exp_mod_exp_eq [of m m \<open>a * 2 ^ n\<close> for n] |
|
768 apply (simp add: ac_simps) |
|
769 done |
|
770 next |
|
771 case False |
|
772 then show ?thesis |
|
773 using push_bit_take_bit [of n "m - n" a] |
|
774 by simp |
|
775 qed |
|
776 |
|
777 lemma take_bit_drop_bit: |
|
778 "take_bit m (drop_bit n a) = drop_bit n (take_bit (m + n) a)" |
|
779 by (simp add: drop_bit_eq_div take_bit_eq_mod ac_simps div_exp_mod_exp_eq) |
|
780 |
|
781 lemma drop_bit_take_bit: |
|
782 "drop_bit m (take_bit n a) = take_bit (n - m) (drop_bit m a)" |
|
783 proof (cases "m \<le> n") |
|
784 case True |
|
785 then show ?thesis |
|
786 using take_bit_drop_bit [of "n - m" m a] by simp |
|
787 next |
|
788 case False |
|
789 then obtain q where \<open>m = n + q\<close> |
|
790 by (auto simp add: not_le dest: less_imp_Suc_add) |
|
791 then have \<open>drop_bit m (take_bit n a) = 0\<close> |
|
792 using div_exp_eq [of \<open>a mod 2 ^ n\<close> n q] |
|
793 by (simp add: take_bit_eq_mod drop_bit_eq_div) |
|
794 with False show ?thesis |
|
795 by simp |
|
796 qed |
|
797 |
|
798 lemma even_push_bit_iff [simp]: |
|
799 \<open>even (push_bit n a) \<longleftrightarrow> n \<noteq> 0 \<or> even a\<close> |
|
800 by (simp add: push_bit_eq_mult) auto |
|
801 |
|
802 lemma bit_push_bit_iff [bit_simps]: |
|
803 \<open>bit (push_bit m a) n \<longleftrightarrow> m \<le> n \<and> 2 ^ n \<noteq> 0 \<and> bit a (n - m)\<close> |
|
804 by (auto simp add: bit_iff_odd push_bit_eq_mult even_mult_exp_div_exp_iff) |
|
805 |
|
806 lemma bit_drop_bit_eq [bit_simps]: |
|
807 \<open>bit (drop_bit n a) = bit a \<circ> (+) n\<close> |
|
808 by (simp add: bit_iff_odd fun_eq_iff ac_simps flip: drop_bit_eq_div) |
|
809 |
|
810 lemma bit_take_bit_iff [bit_simps]: |
|
811 \<open>bit (take_bit m a) n \<longleftrightarrow> n < m \<and> bit a n\<close> |
|
812 by (simp add: bit_iff_odd drop_bit_take_bit not_le flip: drop_bit_eq_div) |
|
813 |
|
814 lemma stable_imp_drop_bit_eq: |
|
815 \<open>drop_bit n a = a\<close> |
|
816 if \<open>a div 2 = a\<close> |
|
817 by (induction n) (simp_all add: that drop_bit_Suc) |
|
818 |
|
819 lemma stable_imp_take_bit_eq: |
|
820 \<open>take_bit n a = (if even a then 0 else 2 ^ n - 1)\<close> |
|
821 if \<open>a div 2 = a\<close> |
|
822 proof (rule bit_eqI) |
|
823 fix m |
|
824 assume \<open>2 ^ m \<noteq> 0\<close> |
|
825 with that show \<open>bit (take_bit n a) m \<longleftrightarrow> bit (if even a then 0 else 2 ^ n - 1) m\<close> |
|
826 by (simp add: bit_take_bit_iff bit_mask_iff stable_imp_bit_iff_odd) |
|
827 qed |
|
828 |
|
829 lemma exp_dvdE: |
|
830 assumes \<open>2 ^ n dvd a\<close> |
|
831 obtains b where \<open>a = push_bit n b\<close> |
|
832 proof - |
|
833 from assms obtain b where \<open>a = 2 ^ n * b\<close> .. |
|
834 then have \<open>a = push_bit n b\<close> |
|
835 by (simp add: push_bit_eq_mult ac_simps) |
|
836 with that show thesis . |
|
837 qed |
|
838 |
|
839 lemma take_bit_eq_0_iff: |
|
840 \<open>take_bit n a = 0 \<longleftrightarrow> 2 ^ n dvd a\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
841 proof |
|
842 assume ?P |
|
843 then show ?Q |
|
844 by (simp add: take_bit_eq_mod mod_0_imp_dvd) |
|
845 next |
|
846 assume ?Q |
|
847 then obtain b where \<open>a = push_bit n b\<close> |
|
848 by (rule exp_dvdE) |
|
849 then show ?P |
|
850 by (simp add: take_bit_push_bit) |
|
851 qed |
|
852 |
|
853 lemma take_bit_tightened: |
|
854 \<open>take_bit m a = take_bit m b\<close> if \<open>take_bit n a = take_bit n b\<close> and \<open>m \<le> n\<close> |
|
855 proof - |
|
856 from that have \<open>take_bit m (take_bit n a) = take_bit m (take_bit n b)\<close> |
|
857 by simp |
|
858 then have \<open>take_bit (min m n) a = take_bit (min m n) b\<close> |
|
859 by simp |
|
860 with that show ?thesis |
|
861 by (simp add: min_def) |
|
862 qed |
|
863 |
|
864 lemma take_bit_eq_self_iff_drop_bit_eq_0: |
|
865 \<open>take_bit n a = a \<longleftrightarrow> drop_bit n a = 0\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
866 proof |
|
867 assume ?P |
|
868 show ?Q |
|
869 proof (rule bit_eqI) |
|
870 fix m |
|
871 from \<open>?P\<close> have \<open>a = take_bit n a\<close> .. |
|
872 also have \<open>\<not> bit (take_bit n a) (n + m)\<close> |
|
873 unfolding bit_simps |
|
874 by (simp add: bit_simps) |
|
875 finally show \<open>bit (drop_bit n a) m \<longleftrightarrow> bit 0 m\<close> |
|
876 by (simp add: bit_simps) |
|
877 qed |
|
878 next |
|
879 assume ?Q |
|
880 show ?P |
|
881 proof (rule bit_eqI) |
|
882 fix m |
|
883 from \<open>?Q\<close> have \<open>\<not> bit (drop_bit n a) (m - n)\<close> |
|
884 by simp |
|
885 then have \<open> \<not> bit a (n + (m - n))\<close> |
|
886 by (simp add: bit_simps) |
|
887 then show \<open>bit (take_bit n a) m \<longleftrightarrow> bit a m\<close> |
|
888 by (cases \<open>m < n\<close>) (auto simp add: bit_simps) |
|
889 qed |
|
890 qed |
|
891 |
|
892 lemma drop_bit_exp_eq: |
|
893 \<open>drop_bit m (2 ^ n) = of_bool (m \<le> n \<and> 2 ^ n \<noteq> 0) * 2 ^ (n - m)\<close> |
|
894 by (rule bit_eqI) (auto simp add: bit_simps) |
|
895 |
|
896 end |
|
897 |
|
898 instantiation nat :: semiring_bit_shifts |
|
899 begin |
|
900 |
|
901 definition push_bit_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
902 where \<open>push_bit_nat n m = m * 2 ^ n\<close> |
|
903 |
|
904 definition drop_bit_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
905 where \<open>drop_bit_nat n m = m div 2 ^ n\<close> |
|
906 |
|
907 definition take_bit_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
908 where \<open>take_bit_nat n m = m mod 2 ^ n\<close> |
|
909 |
|
910 instance |
|
911 by standard (simp_all add: push_bit_nat_def drop_bit_nat_def take_bit_nat_def) |
|
912 |
|
913 end |
|
914 |
|
915 context semiring_bit_shifts |
|
916 begin |
|
917 |
|
918 lemma push_bit_of_nat: |
|
919 \<open>push_bit n (of_nat m) = of_nat (push_bit n m)\<close> |
|
920 by (simp add: push_bit_eq_mult semiring_bit_shifts_class.push_bit_eq_mult) |
|
921 |
|
922 lemma of_nat_push_bit: |
|
923 \<open>of_nat (push_bit m n) = push_bit m (of_nat n)\<close> |
|
924 by (simp add: push_bit_eq_mult semiring_bit_shifts_class.push_bit_eq_mult) |
|
925 |
|
926 lemma take_bit_of_nat: |
|
927 \<open>take_bit n (of_nat m) = of_nat (take_bit n m)\<close> |
|
928 by (rule bit_eqI) (simp add: bit_take_bit_iff Bit_Operations.bit_take_bit_iff bit_of_nat_iff) |
|
929 |
|
930 lemma of_nat_take_bit: |
|
931 \<open>of_nat (take_bit n m) = take_bit n (of_nat m)\<close> |
|
932 by (rule bit_eqI) (simp add: bit_take_bit_iff Bit_Operations.bit_take_bit_iff bit_of_nat_iff) |
|
933 |
|
934 end |
|
935 |
|
936 instantiation int :: semiring_bit_shifts |
|
937 begin |
|
938 |
|
939 definition push_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
940 where \<open>push_bit_int n k = k * 2 ^ n\<close> |
|
941 |
|
942 definition drop_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
943 where \<open>drop_bit_int n k = k div 2 ^ n\<close> |
|
944 |
|
945 definition take_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
946 where \<open>take_bit_int n k = k mod 2 ^ n\<close> |
|
947 |
|
948 instance |
|
949 by standard (simp_all add: push_bit_int_def drop_bit_int_def take_bit_int_def) |
|
950 |
|
951 end |
|
952 |
|
953 lemma bit_push_bit_iff_nat: |
|
954 \<open>bit (push_bit m q) n \<longleftrightarrow> m \<le> n \<and> bit q (n - m)\<close> for q :: nat |
|
955 by (auto simp add: bit_push_bit_iff) |
|
956 |
|
957 lemma bit_push_bit_iff_int: |
|
958 \<open>bit (push_bit m k) n \<longleftrightarrow> m \<le> n \<and> bit k (n - m)\<close> for k :: int |
|
959 by (auto simp add: bit_push_bit_iff) |
|
960 |
|
961 lemma take_bit_nat_less_exp [simp]: |
|
962 \<open>take_bit n m < 2 ^ n\<close> for n m ::nat |
|
963 by (simp add: take_bit_eq_mod) |
|
964 |
|
965 lemma take_bit_nonnegative [simp]: |
|
966 \<open>take_bit n k \<ge> 0\<close> for k :: int |
|
967 by (simp add: take_bit_eq_mod) |
|
968 |
|
969 lemma not_take_bit_negative [simp]: |
|
970 \<open>\<not> take_bit n k < 0\<close> for k :: int |
|
971 by (simp add: not_less) |
|
972 |
|
973 lemma take_bit_int_less_exp [simp]: |
|
974 \<open>take_bit n k < 2 ^ n\<close> for k :: int |
|
975 by (simp add: take_bit_eq_mod) |
|
976 |
|
977 lemma take_bit_nat_eq_self_iff: |
|
978 \<open>take_bit n m = m \<longleftrightarrow> m < 2 ^ n\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
979 for n m :: nat |
|
980 proof |
|
981 assume ?P |
|
982 moreover note take_bit_nat_less_exp [of n m] |
|
983 ultimately show ?Q |
|
984 by simp |
|
985 next |
|
986 assume ?Q |
|
987 then show ?P |
|
988 by (simp add: take_bit_eq_mod) |
|
989 qed |
|
990 |
|
991 lemma take_bit_nat_eq_self: |
|
992 \<open>take_bit n m = m\<close> if \<open>m < 2 ^ n\<close> for m n :: nat |
|
993 using that by (simp add: take_bit_nat_eq_self_iff) |
|
994 |
|
995 lemma take_bit_int_eq_self_iff: |
|
996 \<open>take_bit n k = k \<longleftrightarrow> 0 \<le> k \<and> k < 2 ^ n\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
997 for k :: int |
|
998 proof |
|
999 assume ?P |
|
1000 moreover note take_bit_int_less_exp [of n k] take_bit_nonnegative [of n k] |
|
1001 ultimately show ?Q |
|
1002 by simp |
|
1003 next |
|
1004 assume ?Q |
|
1005 then show ?P |
|
1006 by (simp add: take_bit_eq_mod) |
|
1007 qed |
|
1008 |
|
1009 lemma take_bit_int_eq_self: |
|
1010 \<open>take_bit n k = k\<close> if \<open>0 \<le> k\<close> \<open>k < 2 ^ n\<close> for k :: int |
|
1011 using that by (simp add: take_bit_int_eq_self_iff) |
|
1012 |
|
1013 lemma take_bit_nat_less_eq_self [simp]: |
|
1014 \<open>take_bit n m \<le> m\<close> for n m :: nat |
|
1015 by (simp add: take_bit_eq_mod) |
|
1016 |
|
1017 lemma take_bit_nat_less_self_iff: |
|
1018 \<open>take_bit n m < m \<longleftrightarrow> 2 ^ n \<le> m\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
1019 for m n :: nat |
|
1020 proof |
|
1021 assume ?P |
|
1022 then have \<open>take_bit n m \<noteq> m\<close> |
|
1023 by simp |
|
1024 then show \<open>?Q\<close> |
|
1025 by (simp add: take_bit_nat_eq_self_iff) |
|
1026 next |
|
1027 have \<open>take_bit n m < 2 ^ n\<close> |
|
1028 by (fact take_bit_nat_less_exp) |
|
1029 also assume ?Q |
|
1030 finally show ?P . |
|
1031 qed |
|
1032 |
|
1033 class unique_euclidean_semiring_with_bit_shifts = |
|
1034 unique_euclidean_semiring_with_nat + semiring_bit_shifts |
|
1035 begin |
|
1036 |
|
1037 lemma take_bit_of_exp [simp]: |
|
1038 \<open>take_bit m (2 ^ n) = of_bool (n < m) * 2 ^ n\<close> |
|
1039 by (simp add: take_bit_eq_mod exp_mod_exp) |
|
1040 |
|
1041 lemma take_bit_of_2 [simp]: |
|
1042 \<open>take_bit n 2 = of_bool (2 \<le> n) * 2\<close> |
|
1043 using take_bit_of_exp [of n 1] by simp |
|
1044 |
|
1045 lemma take_bit_of_mask: |
|
1046 \<open>take_bit m (2 ^ n - 1) = 2 ^ min m n - 1\<close> |
|
1047 by (simp add: take_bit_eq_mod mask_mod_exp) |
|
1048 |
|
1049 lemma push_bit_eq_0_iff [simp]: |
|
1050 "push_bit n a = 0 \<longleftrightarrow> a = 0" |
|
1051 by (simp add: push_bit_eq_mult) |
|
1052 |
|
1053 lemma take_bit_add: |
|
1054 "take_bit n (take_bit n a + take_bit n b) = take_bit n (a + b)" |
|
1055 by (simp add: take_bit_eq_mod mod_simps) |
|
1056 |
|
1057 lemma take_bit_of_1_eq_0_iff [simp]: |
|
1058 "take_bit n 1 = 0 \<longleftrightarrow> n = 0" |
|
1059 by (simp add: take_bit_eq_mod) |
|
1060 |
|
1061 lemma take_bit_Suc_1 [simp]: |
|
1062 \<open>take_bit (Suc n) 1 = 1\<close> |
|
1063 by (simp add: take_bit_Suc) |
|
1064 |
|
1065 lemma take_bit_Suc_bit0 [simp]: |
|
1066 \<open>take_bit (Suc n) (numeral (Num.Bit0 k)) = take_bit n (numeral k) * 2\<close> |
|
1067 by (simp add: take_bit_Suc numeral_Bit0_div_2) |
|
1068 |
|
1069 lemma take_bit_Suc_bit1 [simp]: |
|
1070 \<open>take_bit (Suc n) (numeral (Num.Bit1 k)) = take_bit n (numeral k) * 2 + 1\<close> |
|
1071 by (simp add: take_bit_Suc numeral_Bit1_div_2 mod_2_eq_odd) |
|
1072 |
|
1073 lemma take_bit_numeral_1 [simp]: |
|
1074 \<open>take_bit (numeral l) 1 = 1\<close> |
|
1075 by (simp add: take_bit_rec [of \<open>numeral l\<close> 1]) |
|
1076 |
|
1077 lemma take_bit_numeral_bit0 [simp]: |
|
1078 \<open>take_bit (numeral l) (numeral (Num.Bit0 k)) = take_bit (pred_numeral l) (numeral k) * 2\<close> |
|
1079 by (simp add: take_bit_rec numeral_Bit0_div_2) |
|
1080 |
|
1081 lemma take_bit_numeral_bit1 [simp]: |
|
1082 \<open>take_bit (numeral l) (numeral (Num.Bit1 k)) = take_bit (pred_numeral l) (numeral k) * 2 + 1\<close> |
|
1083 by (simp add: take_bit_rec numeral_Bit1_div_2 mod_2_eq_odd) |
|
1084 |
|
1085 lemma drop_bit_Suc_bit0 [simp]: |
|
1086 \<open>drop_bit (Suc n) (numeral (Num.Bit0 k)) = drop_bit n (numeral k)\<close> |
|
1087 by (simp add: drop_bit_Suc numeral_Bit0_div_2) |
|
1088 |
|
1089 lemma drop_bit_Suc_bit1 [simp]: |
|
1090 \<open>drop_bit (Suc n) (numeral (Num.Bit1 k)) = drop_bit n (numeral k)\<close> |
|
1091 by (simp add: drop_bit_Suc numeral_Bit1_div_2) |
|
1092 |
|
1093 lemma drop_bit_numeral_bit0 [simp]: |
|
1094 \<open>drop_bit (numeral l) (numeral (Num.Bit0 k)) = drop_bit (pred_numeral l) (numeral k)\<close> |
|
1095 by (simp add: drop_bit_rec numeral_Bit0_div_2) |
|
1096 |
|
1097 lemma drop_bit_numeral_bit1 [simp]: |
|
1098 \<open>drop_bit (numeral l) (numeral (Num.Bit1 k)) = drop_bit (pred_numeral l) (numeral k)\<close> |
|
1099 by (simp add: drop_bit_rec numeral_Bit1_div_2) |
|
1100 |
|
1101 lemma drop_bit_of_nat: |
|
1102 "drop_bit n (of_nat m) = of_nat (drop_bit n m)" |
|
1103 by (simp add: drop_bit_eq_div Bit_Operations.drop_bit_eq_div of_nat_div [of m "2 ^ n"]) |
|
1104 |
|
1105 lemma bit_of_nat_iff_bit [bit_simps]: |
|
1106 \<open>bit (of_nat m) n \<longleftrightarrow> bit m n\<close> |
|
1107 proof - |
|
1108 have \<open>even (m div 2 ^ n) \<longleftrightarrow> even (of_nat (m div 2 ^ n))\<close> |
|
1109 by simp |
|
1110 also have \<open>of_nat (m div 2 ^ n) = of_nat m div of_nat (2 ^ n)\<close> |
|
1111 by (simp add: of_nat_div) |
|
1112 finally show ?thesis |
|
1113 by (simp add: bit_iff_odd semiring_bits_class.bit_iff_odd) |
|
1114 qed |
|
1115 |
|
1116 lemma of_nat_drop_bit: |
|
1117 \<open>of_nat (drop_bit m n) = drop_bit m (of_nat n)\<close> |
|
1118 by (simp add: drop_bit_eq_div semiring_bit_shifts_class.drop_bit_eq_div of_nat_div) |
|
1119 |
|
1120 lemma bit_push_bit_iff_of_nat_iff [bit_simps]: |
|
1121 \<open>bit (push_bit m (of_nat r)) n \<longleftrightarrow> m \<le> n \<and> bit (of_nat r) (n - m)\<close> |
|
1122 by (auto simp add: bit_push_bit_iff) |
|
1123 |
|
1124 lemma take_bit_sum: |
|
1125 "take_bit n a = (\<Sum>k = 0..<n. push_bit k (of_bool (bit a k)))" |
|
1126 for n :: nat |
|
1127 proof (induction n arbitrary: a) |
|
1128 case 0 |
|
1129 then show ?case |
|
1130 by simp |
|
1131 next |
|
1132 case (Suc n) |
|
1133 have "(\<Sum>k = 0..<Suc n. push_bit k (of_bool (bit a k))) = |
|
1134 of_bool (odd a) + (\<Sum>k = Suc 0..<Suc n. push_bit k (of_bool (bit a k)))" |
|
1135 by (simp add: sum.atLeast_Suc_lessThan ac_simps) |
|
1136 also have "(\<Sum>k = Suc 0..<Suc n. push_bit k (of_bool (bit a k))) |
|
1137 = (\<Sum>k = 0..<n. push_bit k (of_bool (bit (a div 2) k))) * 2" |
|
1138 by (simp only: sum.atLeast_Suc_lessThan_Suc_shift) (simp add: sum_distrib_right push_bit_double drop_bit_Suc bit_Suc) |
|
1139 finally show ?case |
|
1140 using Suc [of "a div 2"] by (simp add: ac_simps take_bit_Suc mod_2_eq_odd) |
|
1141 qed |
|
1142 |
|
1143 end |
|
1144 |
|
1145 instance nat :: unique_euclidean_semiring_with_bit_shifts .. |
|
1146 |
|
1147 instance int :: unique_euclidean_semiring_with_bit_shifts .. |
|
1148 |
|
1149 lemma bit_numeral_int_iff [bit_simps]: |
|
1150 \<open>bit (numeral m :: int) n \<longleftrightarrow> bit (numeral m :: nat) n\<close> |
|
1151 using bit_of_nat_iff_bit [of \<open>numeral m\<close> n] by simp |
|
1152 |
|
1153 lemma bit_not_int_iff': |
613 lemma bit_not_int_iff': |
1154 \<open>bit (- k - 1) n \<longleftrightarrow> \<not> bit k n\<close> |
614 \<open>bit (- k - 1) n \<longleftrightarrow> \<not> bit k n\<close> |
1155 for k :: int |
615 for k :: int |
1156 proof (induction n arbitrary: k) |
616 proof (induction n arbitrary: k) |
1157 case 0 |
617 case 0 |
1206 case False |
661 case False |
1207 then show ?thesis |
662 then show ?thesis |
1208 by simp |
663 by simp |
1209 qed |
664 qed |
1210 |
665 |
1211 lemma bit_numeral_int_simps [simp]: |
|
1212 \<open>bit (1 :: int) (numeral n) \<longleftrightarrow> bit (0 :: int) (pred_numeral n)\<close> |
|
1213 \<open>bit (numeral (num.Bit0 w) :: int) (numeral n) \<longleftrightarrow> bit (numeral w :: int) (pred_numeral n)\<close> |
|
1214 \<open>bit (numeral (num.Bit1 w) :: int) (numeral n) \<longleftrightarrow> bit (numeral w :: int) (pred_numeral n)\<close> |
|
1215 \<open>bit (numeral (Num.BitM w) :: int) (numeral n) \<longleftrightarrow> \<not> bit (- numeral w :: int) (pred_numeral n)\<close> |
|
1216 \<open>bit (- numeral (num.Bit0 w) :: int) (numeral n) \<longleftrightarrow> bit (- numeral w :: int) (pred_numeral n)\<close> |
|
1217 \<open>bit (- numeral (num.Bit1 w) :: int) (numeral n) \<longleftrightarrow> \<not> bit (numeral w :: int) (pred_numeral n)\<close> |
|
1218 \<open>bit (- numeral (Num.BitM w) :: int) (numeral n) \<longleftrightarrow> bit (- (numeral w) :: int) (pred_numeral n)\<close> |
|
1219 by (simp_all add: bit_1_iff numeral_eq_Suc bit_Suc add_One sub_inc_One_eq bit_minus_int_iff) |
|
1220 |
|
1221 lemma bit_numeral_Bit0_Suc_iff [simp]: |
|
1222 \<open>bit (numeral (Num.Bit0 m) :: int) (Suc n) \<longleftrightarrow> bit (numeral m :: int) n\<close> |
|
1223 by (simp add: bit_Suc) |
|
1224 |
|
1225 lemma bit_numeral_Bit1_Suc_iff [simp]: |
|
1226 \<open>bit (numeral (Num.Bit1 m) :: int) (Suc n) \<longleftrightarrow> bit (numeral m :: int) n\<close> |
|
1227 by (simp add: bit_Suc) |
|
1228 |
|
1229 lemma push_bit_nat_eq: |
|
1230 \<open>push_bit n (nat k) = nat (push_bit n k)\<close> |
|
1231 by (cases \<open>k \<ge> 0\<close>) (simp_all add: push_bit_eq_mult nat_mult_distrib not_le mult_nonneg_nonpos2) |
|
1232 |
|
1233 lemma drop_bit_nat_eq: |
|
1234 \<open>drop_bit n (nat k) = nat (drop_bit n k)\<close> |
|
1235 apply (cases \<open>k \<ge> 0\<close>) |
|
1236 apply (simp_all add: drop_bit_eq_div nat_div_distrib nat_power_eq not_le) |
|
1237 apply (simp add: divide_int_def) |
|
1238 done |
|
1239 |
|
1240 lemma take_bit_nat_eq: |
|
1241 \<open>take_bit n (nat k) = nat (take_bit n k)\<close> if \<open>k \<ge> 0\<close> |
|
1242 using that by (simp add: take_bit_eq_mod nat_mod_distrib nat_power_eq) |
|
1243 |
|
1244 lemma nat_take_bit_eq: |
|
1245 \<open>nat (take_bit n k) = take_bit n (nat k)\<close> |
|
1246 if \<open>k \<ge> 0\<close> |
|
1247 using that by (simp add: take_bit_eq_mod nat_mod_distrib nat_power_eq) |
|
1248 |
|
1249 lemma not_exp_less_eq_0_int [simp]: |
|
1250 \<open>\<not> 2 ^ n \<le> (0::int)\<close> |
|
1251 by (simp add: power_le_zero_eq) |
|
1252 |
|
1253 lemma half_nonnegative_int_iff [simp]: |
|
1254 \<open>k div 2 \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
1255 proof (cases \<open>k \<ge> 0\<close>) |
|
1256 case True |
|
1257 then show ?thesis |
|
1258 by (auto simp add: divide_int_def sgn_1_pos) |
|
1259 next |
|
1260 case False |
|
1261 then show ?thesis |
|
1262 by (auto simp add: divide_int_def not_le elim!: evenE) |
|
1263 qed |
|
1264 |
|
1265 lemma half_negative_int_iff [simp]: |
|
1266 \<open>k div 2 < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
1267 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
1268 |
|
1269 lemma push_bit_of_Suc_0 [simp]: |
|
1270 "push_bit n (Suc 0) = 2 ^ n" |
|
1271 using push_bit_of_1 [where ?'a = nat] by simp |
|
1272 |
|
1273 lemma take_bit_of_Suc_0 [simp]: |
|
1274 "take_bit n (Suc 0) = of_bool (0 < n)" |
|
1275 using take_bit_of_1 [where ?'a = nat] by simp |
|
1276 |
|
1277 lemma drop_bit_of_Suc_0 [simp]: |
|
1278 "drop_bit n (Suc 0) = of_bool (n = 0)" |
|
1279 using drop_bit_of_1 [where ?'a = nat] by simp |
|
1280 |
|
1281 lemma push_bit_minus_one: |
|
1282 "push_bit n (- 1 :: int) = - (2 ^ n)" |
|
1283 by (simp add: push_bit_eq_mult) |
|
1284 |
|
1285 lemma minus_1_div_exp_eq_int: |
|
1286 \<open>- 1 div (2 :: int) ^ n = - 1\<close> |
|
1287 by (induction n) (use div_exp_eq [symmetric, of \<open>- 1 :: int\<close> 1] in \<open>simp_all add: ac_simps\<close>) |
|
1288 |
|
1289 lemma drop_bit_minus_one [simp]: |
|
1290 \<open>drop_bit n (- 1 :: int) = - 1\<close> |
|
1291 by (simp add: drop_bit_eq_div minus_1_div_exp_eq_int) |
|
1292 |
|
1293 lemma take_bit_Suc_from_most: |
|
1294 \<open>take_bit (Suc n) k = 2 ^ n * of_bool (bit k n) + take_bit n k\<close> for k :: int |
|
1295 by (simp only: take_bit_eq_mod power_Suc2) (simp_all add: bit_iff_odd odd_iff_mod_2_eq_one zmod_zmult2_eq) |
|
1296 |
|
1297 lemma take_bit_minus: |
|
1298 \<open>take_bit n (- take_bit n k) = take_bit n (- k)\<close> |
|
1299 for k :: int |
|
1300 by (simp add: take_bit_eq_mod mod_minus_eq) |
|
1301 |
|
1302 lemma take_bit_diff: |
|
1303 \<open>take_bit n (take_bit n k - take_bit n l) = take_bit n (k - l)\<close> |
|
1304 for k l :: int |
|
1305 by (simp add: take_bit_eq_mod mod_diff_eq) |
|
1306 |
|
1307 lemma bit_imp_take_bit_positive: |
|
1308 \<open>0 < take_bit m k\<close> if \<open>n < m\<close> and \<open>bit k n\<close> for k :: int |
|
1309 proof (rule ccontr) |
|
1310 assume \<open>\<not> 0 < take_bit m k\<close> |
|
1311 then have \<open>take_bit m k = 0\<close> |
|
1312 by (auto simp add: not_less intro: order_antisym) |
|
1313 then have \<open>bit (take_bit m k) n = bit 0 n\<close> |
|
1314 by simp |
|
1315 with that show False |
|
1316 by (simp add: bit_take_bit_iff) |
|
1317 qed |
|
1318 |
|
1319 lemma take_bit_mult: |
|
1320 \<open>take_bit n (take_bit n k * take_bit n l) = take_bit n (k * l)\<close> |
|
1321 for k l :: int |
|
1322 by (simp add: take_bit_eq_mod mod_mult_eq) |
|
1323 |
|
1324 lemma (in ring_1) of_nat_nat_take_bit_eq [simp]: |
|
1325 \<open>of_nat (nat (take_bit n k)) = of_int (take_bit n k)\<close> |
|
1326 by simp |
|
1327 |
|
1328 lemma take_bit_minus_small_eq: |
|
1329 \<open>take_bit n (- k) = 2 ^ n - k\<close> if \<open>0 < k\<close> \<open>k \<le> 2 ^ n\<close> for k :: int |
|
1330 proof - |
|
1331 define m where \<open>m = nat k\<close> |
|
1332 with that have \<open>k = int m\<close> and \<open>0 < m\<close> and \<open>m \<le> 2 ^ n\<close> |
|
1333 by simp_all |
|
1334 have \<open>(2 ^ n - m) mod 2 ^ n = 2 ^ n - m\<close> |
|
1335 using \<open>0 < m\<close> by simp |
|
1336 then have \<open>int ((2 ^ n - m) mod 2 ^ n) = int (2 ^ n - m)\<close> |
|
1337 by simp |
|
1338 then have \<open>(2 ^ n - int m) mod 2 ^ n = 2 ^ n - int m\<close> |
|
1339 using \<open>m \<le> 2 ^ n\<close> by (simp only: of_nat_mod of_nat_diff) simp |
|
1340 with \<open>k = int m\<close> have \<open>(2 ^ n - k) mod 2 ^ n = 2 ^ n - k\<close> |
|
1341 by simp |
|
1342 then show ?thesis |
|
1343 by (simp add: take_bit_eq_mod) |
|
1344 qed |
|
1345 |
|
1346 lemma drop_bit_push_bit_int: |
|
1347 \<open>drop_bit m (push_bit n k) = drop_bit (m - n) (push_bit (n - m) k)\<close> for k :: int |
|
1348 by (cases \<open>m \<le> n\<close>) (auto simp add: mult.left_commute [of _ \<open>2 ^ n\<close>] mult.commute [of _ \<open>2 ^ n\<close>] mult.assoc |
|
1349 mult.commute [of k] drop_bit_eq_div push_bit_eq_mult not_le power_add dest!: le_Suc_ex less_imp_Suc_add) |
|
1350 |
|
1351 lemma push_bit_nonnegative_int_iff [simp]: |
|
1352 \<open>push_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
1353 by (simp add: push_bit_eq_mult zero_le_mult_iff) |
|
1354 |
|
1355 lemma push_bit_negative_int_iff [simp]: |
|
1356 \<open>push_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
1357 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
1358 |
|
1359 lemma drop_bit_nonnegative_int_iff [simp]: |
|
1360 \<open>drop_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
1361 by (induction n) (simp_all add: drop_bit_Suc drop_bit_half) |
|
1362 |
|
1363 lemma drop_bit_negative_int_iff [simp]: |
|
1364 \<open>drop_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
1365 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
1366 |
|
1367 |
666 |
1368 subsection \<open>Bit operations\<close> |
667 subsection \<open>Bit operations\<close> |
1369 |
668 |
1370 class semiring_bit_operations = semiring_bit_shifts + |
669 class semiring_bit_operations = semiring_bits + |
1371 fixes "and" :: \<open>'a \<Rightarrow> 'a \<Rightarrow> 'a\<close> (infixr \<open>AND\<close> 64) |
670 fixes "and" :: \<open>'a \<Rightarrow> 'a \<Rightarrow> 'a\<close> (infixr \<open>AND\<close> 64) |
1372 and or :: \<open>'a \<Rightarrow> 'a \<Rightarrow> 'a\<close> (infixr \<open>OR\<close> 59) |
671 and or :: \<open>'a \<Rightarrow> 'a \<Rightarrow> 'a\<close> (infixr \<open>OR\<close> 59) |
1373 and xor :: \<open>'a \<Rightarrow> 'a \<Rightarrow> 'a\<close> (infixr \<open>XOR\<close> 59) |
672 and xor :: \<open>'a \<Rightarrow> 'a \<Rightarrow> 'a\<close> (infixr \<open>XOR\<close> 59) |
1374 and mask :: \<open>nat \<Rightarrow> 'a\<close> |
673 and mask :: \<open>nat \<Rightarrow> 'a\<close> |
1375 and set_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
674 and set_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
1376 and unset_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
675 and unset_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
1377 and flip_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
676 and flip_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
|
677 and push_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
|
678 and drop_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
|
679 and take_bit :: \<open>nat \<Rightarrow> 'a \<Rightarrow> 'a\<close> |
1378 assumes bit_and_iff [bit_simps]: \<open>bit (a AND b) n \<longleftrightarrow> bit a n \<and> bit b n\<close> |
680 assumes bit_and_iff [bit_simps]: \<open>bit (a AND b) n \<longleftrightarrow> bit a n \<and> bit b n\<close> |
1379 and bit_or_iff [bit_simps]: \<open>bit (a OR b) n \<longleftrightarrow> bit a n \<or> bit b n\<close> |
681 and bit_or_iff [bit_simps]: \<open>bit (a OR b) n \<longleftrightarrow> bit a n \<or> bit b n\<close> |
1380 and bit_xor_iff [bit_simps]: \<open>bit (a XOR b) n \<longleftrightarrow> bit a n \<noteq> bit b n\<close> |
682 and bit_xor_iff [bit_simps]: \<open>bit (a XOR b) n \<longleftrightarrow> bit a n \<noteq> bit b n\<close> |
1381 and mask_eq_exp_minus_1: \<open>mask n = 2 ^ n - 1\<close> |
683 and mask_eq_exp_minus_1: \<open>mask n = 2 ^ n - 1\<close> |
1382 and set_bit_eq_or: \<open>set_bit n a = a OR push_bit n 1\<close> |
684 and set_bit_eq_or: \<open>set_bit n a = a OR push_bit n 1\<close> |
1383 and bit_unset_bit_iff [bit_simps]: \<open>bit (unset_bit m a) n \<longleftrightarrow> bit a n \<and> m \<noteq> n\<close> |
685 and bit_unset_bit_iff [bit_simps]: \<open>bit (unset_bit m a) n \<longleftrightarrow> bit a n \<and> m \<noteq> n\<close> |
1384 and flip_bit_eq_xor: \<open>flip_bit n a = a XOR push_bit n 1\<close> |
686 and flip_bit_eq_xor: \<open>flip_bit n a = a XOR push_bit n 1\<close> |
|
687 and push_bit_eq_mult: \<open>push_bit n a = a * 2 ^ n\<close> |
|
688 and drop_bit_eq_div: \<open>drop_bit n a = a div 2 ^ n\<close> |
|
689 and take_bit_eq_mod: \<open>take_bit n a = a mod 2 ^ n\<close> |
1385 begin |
690 begin |
1386 |
691 |
1387 text \<open> |
692 text \<open> |
1388 We want the bitwise operations to bind slightly weaker |
693 We want the bitwise operations to bind slightly weaker |
1389 than \<open>+\<close> and \<open>-\<close>. |
694 than \<open>+\<close> and \<open>-\<close>. |
1390 For the sake of code generation |
695 |
1391 the operations \<^const>\<open>and\<close>, \<^const>\<open>or\<close> and \<^const>\<open>xor\<close> |
696 Logically, \<^const>\<open>push_bit\<close>, |
1392 are specified as definitional class operations. |
697 \<^const>\<open>drop_bit\<close> and \<^const>\<open>take_bit\<close> are just aliases; having them |
|
698 as separate operations makes proofs easier, otherwise proof automation |
|
699 would fiddle with concrete expressions \<^term>\<open>2 ^ n\<close> in a way obfuscating the basic |
|
700 algebraic relationships between those operations. |
|
701 |
|
702 For the sake of code generation operations |
|
703 are specified as definitional class operations, |
|
704 taking into account that specific instances of these can be implemented |
|
705 differently wrt. code generation. |
1393 \<close> |
706 \<close> |
1394 |
707 |
1395 sublocale "and": semilattice \<open>(AND)\<close> |
708 sublocale "and": semilattice \<open>(AND)\<close> |
1396 by standard (auto simp add: bit_eq_iff bit_and_iff) |
709 by standard (auto simp add: bit_eq_iff bit_and_iff) |
1397 |
710 |
1872 |
1446 |
1873 end |
1447 end |
1874 |
1448 |
1875 |
1449 |
1876 subsection \<open>Instance \<^typ>\<open>int\<close>\<close> |
1450 subsection \<open>Instance \<^typ>\<open>int\<close>\<close> |
|
1451 |
|
1452 instantiation int :: ring_bit_operations |
|
1453 begin |
|
1454 |
|
1455 definition not_int :: \<open>int \<Rightarrow> int\<close> |
|
1456 where \<open>not_int k = - k - 1\<close> |
|
1457 |
|
1458 lemma not_int_rec: |
|
1459 \<open>NOT k = of_bool (even k) + 2 * NOT (k div 2)\<close> for k :: int |
|
1460 by (auto simp add: not_int_def elim: oddE) |
|
1461 |
|
1462 lemma even_not_iff_int: |
|
1463 \<open>even (NOT k) \<longleftrightarrow> odd k\<close> for k :: int |
|
1464 by (simp add: not_int_def) |
|
1465 |
|
1466 lemma not_int_div_2: |
|
1467 \<open>NOT k div 2 = NOT (k div 2)\<close> for k :: int |
|
1468 by (cases k) (simp_all add: not_int_def divide_int_def nat_add_distrib) |
|
1469 |
|
1470 lemma bit_not_int_iff [bit_simps]: |
|
1471 \<open>bit (NOT k) n \<longleftrightarrow> \<not> bit k n\<close> |
|
1472 for k :: int |
|
1473 by (simp add: bit_not_int_iff' not_int_def) |
|
1474 |
|
1475 function and_int :: \<open>int \<Rightarrow> int \<Rightarrow> int\<close> |
|
1476 where \<open>(k::int) AND l = (if k \<in> {0, - 1} \<and> l \<in> {0, - 1} |
|
1477 then - of_bool (odd k \<and> odd l) |
|
1478 else of_bool (odd k \<and> odd l) + 2 * ((k div 2) AND (l div 2)))\<close> |
|
1479 by auto |
|
1480 |
|
1481 termination proof (relation \<open>measure (\<lambda>(k, l). nat (\<bar>k\<bar> + \<bar>l\<bar>))\<close>) |
|
1482 show \<open>wf (measure (\<lambda>(k, l). nat (\<bar>k\<bar> + \<bar>l\<bar>)))\<close> |
|
1483 by simp |
|
1484 show \<open>((k div 2, l div 2), k, l) \<in> measure (\<lambda>(k, l). nat (\<bar>k\<bar> + \<bar>l\<bar>))\<close> |
|
1485 if \<open>\<not> (k \<in> {0, - 1} \<and> l \<in> {0, - 1})\<close> for k l |
|
1486 proof - |
|
1487 have less_eq: \<open>\<bar>k div 2\<bar> \<le> \<bar>k\<bar>\<close> for k :: int |
|
1488 by (cases k) (simp_all add: divide_int_def nat_add_distrib) |
|
1489 have less: \<open>\<bar>k div 2\<bar> < \<bar>k\<bar>\<close> if \<open>k \<notin> {0, - 1}\<close> for k :: int |
|
1490 proof (cases k) |
|
1491 case (nonneg n) |
|
1492 with that show ?thesis |
|
1493 by (simp add: int_div_less_self) |
|
1494 next |
|
1495 case (neg n) |
|
1496 with that have \<open>n \<noteq> 0\<close> |
|
1497 by simp |
|
1498 then have \<open>n div 2 < n\<close> |
|
1499 by (simp add: div_less_iff_less_mult) |
|
1500 with neg that show ?thesis |
|
1501 by (simp add: divide_int_def nat_add_distrib) |
|
1502 qed |
|
1503 from that have *: \<open>k \<notin> {0, - 1} \<or> l \<notin> {0, - 1}\<close> |
|
1504 by simp |
|
1505 then have \<open>0 < \<bar>k\<bar> + \<bar>l\<bar>\<close> |
|
1506 by auto |
|
1507 moreover from * have \<open>\<bar>k div 2\<bar> + \<bar>l div 2\<bar> < \<bar>k\<bar> + \<bar>l\<bar>\<close> |
|
1508 proof |
|
1509 assume \<open>k \<notin> {0, - 1}\<close> |
|
1510 then have \<open>\<bar>k div 2\<bar> < \<bar>k\<bar>\<close> |
|
1511 by (rule less) |
|
1512 with less_eq [of l] show ?thesis |
|
1513 by auto |
|
1514 next |
|
1515 assume \<open>l \<notin> {0, - 1}\<close> |
|
1516 then have \<open>\<bar>l div 2\<bar> < \<bar>l\<bar>\<close> |
|
1517 by (rule less) |
|
1518 with less_eq [of k] show ?thesis |
|
1519 by auto |
|
1520 qed |
|
1521 ultimately show ?thesis |
|
1522 by simp |
|
1523 qed |
|
1524 qed |
|
1525 |
|
1526 declare and_int.simps [simp del] |
|
1527 |
|
1528 lemma and_int_rec: |
|
1529 \<open>k AND l = of_bool (odd k \<and> odd l) + 2 * ((k div 2) AND (l div 2))\<close> |
|
1530 for k l :: int |
|
1531 proof (cases \<open>k \<in> {0, - 1} \<and> l \<in> {0, - 1}\<close>) |
|
1532 case True |
|
1533 then show ?thesis |
|
1534 by auto (simp_all add: and_int.simps) |
|
1535 next |
|
1536 case False |
|
1537 then show ?thesis |
|
1538 by (auto simp add: ac_simps and_int.simps [of k l]) |
|
1539 qed |
|
1540 |
|
1541 lemma bit_and_int_iff: |
|
1542 \<open>bit (k AND l) n \<longleftrightarrow> bit k n \<and> bit l n\<close> for k l :: int |
|
1543 proof (induction n arbitrary: k l) |
|
1544 case 0 |
|
1545 then show ?case |
|
1546 by (simp add: and_int_rec [of k l]) |
|
1547 next |
|
1548 case (Suc n) |
|
1549 then show ?case |
|
1550 by (simp add: and_int_rec [of k l] bit_Suc) |
|
1551 qed |
|
1552 |
|
1553 lemma even_and_iff_int: |
|
1554 \<open>even (k AND l) \<longleftrightarrow> even k \<or> even l\<close> for k l :: int |
|
1555 using bit_and_int_iff [of k l 0] by auto |
|
1556 |
|
1557 definition or_int :: \<open>int \<Rightarrow> int \<Rightarrow> int\<close> |
|
1558 where \<open>k OR l = NOT (NOT k AND NOT l)\<close> for k l :: int |
|
1559 |
|
1560 lemma or_int_rec: |
|
1561 \<open>k OR l = of_bool (odd k \<or> odd l) + 2 * ((k div 2) OR (l div 2))\<close> |
|
1562 for k l :: int |
|
1563 using and_int_rec [of \<open>NOT k\<close> \<open>NOT l\<close>] |
|
1564 by (simp add: or_int_def even_not_iff_int not_int_div_2) |
|
1565 (simp_all add: not_int_def) |
|
1566 |
|
1567 lemma bit_or_int_iff: |
|
1568 \<open>bit (k OR l) n \<longleftrightarrow> bit k n \<or> bit l n\<close> for k l :: int |
|
1569 by (simp add: or_int_def bit_not_int_iff bit_and_int_iff) |
|
1570 |
|
1571 definition xor_int :: \<open>int \<Rightarrow> int \<Rightarrow> int\<close> |
|
1572 where \<open>k XOR l = k AND NOT l OR NOT k AND l\<close> for k l :: int |
|
1573 |
|
1574 lemma xor_int_rec: |
|
1575 \<open>k XOR l = of_bool (odd k \<noteq> odd l) + 2 * ((k div 2) XOR (l div 2))\<close> |
|
1576 for k l :: int |
|
1577 by (simp add: xor_int_def or_int_rec [of \<open>k AND NOT l\<close> \<open>NOT k AND l\<close>] even_and_iff_int even_not_iff_int) |
|
1578 (simp add: and_int_rec [of \<open>NOT k\<close> \<open>l\<close>] and_int_rec [of \<open>k\<close> \<open>NOT l\<close>] not_int_div_2) |
|
1579 |
|
1580 lemma bit_xor_int_iff: |
|
1581 \<open>bit (k XOR l) n \<longleftrightarrow> bit k n \<noteq> bit l n\<close> for k l :: int |
|
1582 by (auto simp add: xor_int_def bit_or_int_iff bit_and_int_iff bit_not_int_iff) |
|
1583 |
|
1584 definition mask_int :: \<open>nat \<Rightarrow> int\<close> |
|
1585 where \<open>mask n = (2 :: int) ^ n - 1\<close> |
|
1586 |
|
1587 definition push_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
1588 where \<open>push_bit_int n k = k * 2 ^ n\<close> |
|
1589 |
|
1590 definition drop_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
1591 where \<open>drop_bit_int n k = k div 2 ^ n\<close> |
|
1592 |
|
1593 definition take_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
1594 where \<open>take_bit_int n k = k mod 2 ^ n\<close> |
|
1595 |
|
1596 definition set_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
1597 where \<open>set_bit n k = k OR push_bit n 1\<close> for k :: int |
|
1598 |
|
1599 definition unset_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
1600 where \<open>unset_bit n k = k AND NOT (push_bit n 1)\<close> for k :: int |
|
1601 |
|
1602 definition flip_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
1603 where \<open>flip_bit n k = k XOR push_bit n 1\<close> for k :: int |
|
1604 |
|
1605 instance proof |
|
1606 fix k l :: int and m n :: nat |
|
1607 show \<open>- k = NOT (k - 1)\<close> |
|
1608 by (simp add: not_int_def) |
|
1609 show \<open>bit (k AND l) n \<longleftrightarrow> bit k n \<and> bit l n\<close> |
|
1610 by (fact bit_and_int_iff) |
|
1611 show \<open>bit (k OR l) n \<longleftrightarrow> bit k n \<or> bit l n\<close> |
|
1612 by (fact bit_or_int_iff) |
|
1613 show \<open>bit (k XOR l) n \<longleftrightarrow> bit k n \<noteq> bit l n\<close> |
|
1614 by (fact bit_xor_int_iff) |
|
1615 show \<open>bit (unset_bit m k) n \<longleftrightarrow> bit k n \<and> m \<noteq> n\<close> |
|
1616 proof - |
|
1617 have \<open>unset_bit m k = k AND NOT (push_bit m 1)\<close> |
|
1618 by (simp add: unset_bit_int_def) |
|
1619 also have \<open>NOT (push_bit m 1 :: int) = - (push_bit m 1 + 1)\<close> |
|
1620 by (simp add: not_int_def) |
|
1621 finally show ?thesis by (simp only: bit_simps bit_and_int_iff) |
|
1622 (auto simp add: bit_simps bit_not_int_iff' push_bit_int_def) |
|
1623 qed |
|
1624 qed (simp_all add: bit_not_int_iff mask_int_def set_bit_int_def flip_bit_int_def |
|
1625 push_bit_int_def drop_bit_int_def take_bit_int_def) |
|
1626 |
|
1627 end |
|
1628 |
|
1629 lemma bit_push_bit_iff_int: |
|
1630 \<open>bit (push_bit m k) n \<longleftrightarrow> m \<le> n \<and> bit k (n - m)\<close> for k :: int |
|
1631 by (auto simp add: bit_push_bit_iff) |
|
1632 |
|
1633 lemma take_bit_nonnegative [simp]: |
|
1634 \<open>take_bit n k \<ge> 0\<close> for k :: int |
|
1635 by (simp add: take_bit_eq_mod) |
|
1636 |
|
1637 lemma not_take_bit_negative [simp]: |
|
1638 \<open>\<not> take_bit n k < 0\<close> for k :: int |
|
1639 by (simp add: not_less) |
|
1640 |
|
1641 lemma take_bit_int_less_exp [simp]: |
|
1642 \<open>take_bit n k < 2 ^ n\<close> for k :: int |
|
1643 by (simp add: take_bit_eq_mod) |
|
1644 |
|
1645 lemma take_bit_int_eq_self_iff: |
|
1646 \<open>take_bit n k = k \<longleftrightarrow> 0 \<le> k \<and> k < 2 ^ n\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
1647 for k :: int |
|
1648 proof |
|
1649 assume ?P |
|
1650 moreover note take_bit_int_less_exp [of n k] take_bit_nonnegative [of n k] |
|
1651 ultimately show ?Q |
|
1652 by simp |
|
1653 next |
|
1654 assume ?Q |
|
1655 then show ?P |
|
1656 by (simp add: take_bit_eq_mod) |
|
1657 qed |
|
1658 |
|
1659 lemma take_bit_int_eq_self: |
|
1660 \<open>take_bit n k = k\<close> if \<open>0 \<le> k\<close> \<open>k < 2 ^ n\<close> for k :: int |
|
1661 using that by (simp add: take_bit_int_eq_self_iff) |
|
1662 |
|
1663 lemma mask_half_int: |
|
1664 \<open>mask n div 2 = (mask (n - 1) :: int)\<close> |
|
1665 by (cases n) (simp_all add: mask_eq_exp_minus_1 algebra_simps) |
|
1666 |
|
1667 lemma mask_nonnegative_int [simp]: |
|
1668 \<open>mask n \<ge> (0::int)\<close> |
|
1669 by (simp add: mask_eq_exp_minus_1) |
|
1670 |
|
1671 lemma not_mask_negative_int [simp]: |
|
1672 \<open>\<not> mask n < (0::int)\<close> |
|
1673 by (simp add: not_less) |
|
1674 |
|
1675 lemma not_nonnegative_int_iff [simp]: |
|
1676 \<open>NOT k \<ge> 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
1677 by (simp add: not_int_def) |
|
1678 |
|
1679 lemma not_negative_int_iff [simp]: |
|
1680 \<open>NOT k < 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
1681 by (subst Not_eq_iff [symmetric]) (simp add: not_less not_le) |
|
1682 |
|
1683 lemma and_nonnegative_int_iff [simp]: |
|
1684 \<open>k AND l \<ge> 0 \<longleftrightarrow> k \<ge> 0 \<or> l \<ge> 0\<close> for k l :: int |
|
1685 proof (induction k arbitrary: l rule: int_bit_induct) |
|
1686 case zero |
|
1687 then show ?case |
|
1688 by simp |
|
1689 next |
|
1690 case minus |
|
1691 then show ?case |
|
1692 by simp |
|
1693 next |
|
1694 case (even k) |
|
1695 then show ?case |
|
1696 using and_int_rec [of \<open>k * 2\<close> l] |
|
1697 by (simp add: pos_imp_zdiv_nonneg_iff zero_le_mult_iff) |
|
1698 next |
|
1699 case (odd k) |
|
1700 from odd have \<open>0 \<le> k AND l div 2 \<longleftrightarrow> 0 \<le> k \<or> 0 \<le> l div 2\<close> |
|
1701 by simp |
|
1702 then have \<open>0 \<le> (1 + k * 2) div 2 AND l div 2 \<longleftrightarrow> 0 \<le> (1 + k * 2) div 2 \<or> 0 \<le> l div 2\<close> |
|
1703 by simp |
|
1704 with and_int_rec [of \<open>1 + k * 2\<close> l] |
|
1705 show ?case |
|
1706 by (auto simp add: zero_le_mult_iff not_le) |
|
1707 qed |
|
1708 |
|
1709 lemma and_negative_int_iff [simp]: |
|
1710 \<open>k AND l < 0 \<longleftrightarrow> k < 0 \<and> l < 0\<close> for k l :: int |
|
1711 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
1712 |
|
1713 lemma and_less_eq: |
|
1714 \<open>k AND l \<le> k\<close> if \<open>l < 0\<close> for k l :: int |
|
1715 using that proof (induction k arbitrary: l rule: int_bit_induct) |
|
1716 case zero |
|
1717 then show ?case |
|
1718 by simp |
|
1719 next |
|
1720 case minus |
|
1721 then show ?case |
|
1722 by simp |
|
1723 next |
|
1724 case (even k) |
|
1725 from even.IH [of \<open>l div 2\<close>] even.hyps even.prems |
|
1726 show ?case |
|
1727 by (simp add: and_int_rec [of _ l]) |
|
1728 next |
|
1729 case (odd k) |
|
1730 from odd.IH [of \<open>l div 2\<close>] odd.hyps odd.prems |
|
1731 show ?case |
|
1732 by (simp add: and_int_rec [of _ l]) linarith |
|
1733 qed |
|
1734 |
|
1735 lemma or_nonnegative_int_iff [simp]: |
|
1736 \<open>k OR l \<ge> 0 \<longleftrightarrow> k \<ge> 0 \<and> l \<ge> 0\<close> for k l :: int |
|
1737 by (simp only: or_eq_not_not_and not_nonnegative_int_iff) simp |
|
1738 |
|
1739 lemma or_negative_int_iff [simp]: |
|
1740 \<open>k OR l < 0 \<longleftrightarrow> k < 0 \<or> l < 0\<close> for k l :: int |
|
1741 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
1742 |
|
1743 lemma or_greater_eq: |
|
1744 \<open>k OR l \<ge> k\<close> if \<open>l \<ge> 0\<close> for k l :: int |
|
1745 using that proof (induction k arbitrary: l rule: int_bit_induct) |
|
1746 case zero |
|
1747 then show ?case |
|
1748 by simp |
|
1749 next |
|
1750 case minus |
|
1751 then show ?case |
|
1752 by simp |
|
1753 next |
|
1754 case (even k) |
|
1755 from even.IH [of \<open>l div 2\<close>] even.hyps even.prems |
|
1756 show ?case |
|
1757 by (simp add: or_int_rec [of _ l]) linarith |
|
1758 next |
|
1759 case (odd k) |
|
1760 from odd.IH [of \<open>l div 2\<close>] odd.hyps odd.prems |
|
1761 show ?case |
|
1762 by (simp add: or_int_rec [of _ l]) |
|
1763 qed |
|
1764 |
|
1765 lemma xor_nonnegative_int_iff [simp]: |
|
1766 \<open>k XOR l \<ge> 0 \<longleftrightarrow> (k \<ge> 0 \<longleftrightarrow> l \<ge> 0)\<close> for k l :: int |
|
1767 by (simp only: bit.xor_def or_nonnegative_int_iff) auto |
|
1768 |
|
1769 lemma xor_negative_int_iff [simp]: |
|
1770 \<open>k XOR l < 0 \<longleftrightarrow> (k < 0) \<noteq> (l < 0)\<close> for k l :: int |
|
1771 by (subst Not_eq_iff [symmetric]) (auto simp add: not_less) |
|
1772 |
|
1773 lemma OR_upper: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1774 fixes x y :: int |
|
1775 assumes \<open>0 \<le> x\<close> \<open>x < 2 ^ n\<close> \<open>y < 2 ^ n\<close> |
|
1776 shows \<open>x OR y < 2 ^ n\<close> |
|
1777 using assms proof (induction x arbitrary: y n rule: int_bit_induct) |
|
1778 case zero |
|
1779 then show ?case |
|
1780 by simp |
|
1781 next |
|
1782 case minus |
|
1783 then show ?case |
|
1784 by simp |
|
1785 next |
|
1786 case (even x) |
|
1787 from even.IH [of \<open>n - 1\<close> \<open>y div 2\<close>] even.prems even.hyps |
|
1788 show ?case |
|
1789 by (cases n) (auto simp add: or_int_rec [of \<open>_ * 2\<close>] elim: oddE) |
|
1790 next |
|
1791 case (odd x) |
|
1792 from odd.IH [of \<open>n - 1\<close> \<open>y div 2\<close>] odd.prems odd.hyps |
|
1793 show ?case |
|
1794 by (cases n) (auto simp add: or_int_rec [of \<open>1 + _ * 2\<close>], linarith) |
|
1795 qed |
|
1796 |
|
1797 lemma XOR_upper: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1798 fixes x y :: int |
|
1799 assumes \<open>0 \<le> x\<close> \<open>x < 2 ^ n\<close> \<open>y < 2 ^ n\<close> |
|
1800 shows \<open>x XOR y < 2 ^ n\<close> |
|
1801 using assms proof (induction x arbitrary: y n rule: int_bit_induct) |
|
1802 case zero |
|
1803 then show ?case |
|
1804 by simp |
|
1805 next |
|
1806 case minus |
|
1807 then show ?case |
|
1808 by simp |
|
1809 next |
|
1810 case (even x) |
|
1811 from even.IH [of \<open>n - 1\<close> \<open>y div 2\<close>] even.prems even.hyps |
|
1812 show ?case |
|
1813 by (cases n) (auto simp add: xor_int_rec [of \<open>_ * 2\<close>] elim: oddE) |
|
1814 next |
|
1815 case (odd x) |
|
1816 from odd.IH [of \<open>n - 1\<close> \<open>y div 2\<close>] odd.prems odd.hyps |
|
1817 show ?case |
|
1818 by (cases n) (auto simp add: xor_int_rec [of \<open>1 + _ * 2\<close>]) |
|
1819 qed |
|
1820 |
|
1821 lemma AND_lower [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1822 fixes x y :: int |
|
1823 assumes \<open>0 \<le> x\<close> |
|
1824 shows \<open>0 \<le> x AND y\<close> |
|
1825 using assms by simp |
|
1826 |
|
1827 lemma OR_lower [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1828 fixes x y :: int |
|
1829 assumes \<open>0 \<le> x\<close> \<open>0 \<le> y\<close> |
|
1830 shows \<open>0 \<le> x OR y\<close> |
|
1831 using assms by simp |
|
1832 |
|
1833 lemma XOR_lower [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1834 fixes x y :: int |
|
1835 assumes \<open>0 \<le> x\<close> \<open>0 \<le> y\<close> |
|
1836 shows \<open>0 \<le> x XOR y\<close> |
|
1837 using assms by simp |
|
1838 |
|
1839 lemma AND_upper1 [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1840 fixes x y :: int |
|
1841 assumes \<open>0 \<le> x\<close> |
|
1842 shows \<open>x AND y \<le> x\<close> |
|
1843 using assms proof (induction x arbitrary: y rule: int_bit_induct) |
|
1844 case (odd k) |
|
1845 then have \<open>k AND y div 2 \<le> k\<close> |
|
1846 by simp |
|
1847 then show ?case |
|
1848 by (simp add: and_int_rec [of \<open>1 + _ * 2\<close>]) |
|
1849 qed (simp_all add: and_int_rec [of \<open>_ * 2\<close>]) |
|
1850 |
|
1851 lemmas AND_upper1' [simp] = order_trans [OF AND_upper1] \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1852 lemmas AND_upper1'' [simp] = order_le_less_trans [OF AND_upper1] \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1853 |
|
1854 lemma AND_upper2 [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1855 fixes x y :: int |
|
1856 assumes \<open>0 \<le> y\<close> |
|
1857 shows \<open>x AND y \<le> y\<close> |
|
1858 using assms AND_upper1 [of y x] by (simp add: ac_simps) |
|
1859 |
|
1860 lemmas AND_upper2' [simp] = order_trans [OF AND_upper2] \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1861 lemmas AND_upper2'' [simp] = order_le_less_trans [OF AND_upper2] \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
1862 |
|
1863 lemma plus_and_or: \<open>(x AND y) + (x OR y) = x + y\<close> for x y :: int |
|
1864 proof (induction x arbitrary: y rule: int_bit_induct) |
|
1865 case zero |
|
1866 then show ?case |
|
1867 by simp |
|
1868 next |
|
1869 case minus |
|
1870 then show ?case |
|
1871 by simp |
|
1872 next |
|
1873 case (even x) |
|
1874 from even.IH [of \<open>y div 2\<close>] |
|
1875 show ?case |
|
1876 by (auto simp add: and_int_rec [of _ y] or_int_rec [of _ y] elim: oddE) |
|
1877 next |
|
1878 case (odd x) |
|
1879 from odd.IH [of \<open>y div 2\<close>] |
|
1880 show ?case |
|
1881 by (auto simp add: and_int_rec [of _ y] or_int_rec [of _ y] elim: oddE) |
|
1882 qed |
|
1883 |
|
1884 lemma push_bit_minus_one: |
|
1885 "push_bit n (- 1 :: int) = - (2 ^ n)" |
|
1886 by (simp add: push_bit_eq_mult) |
|
1887 |
|
1888 lemma minus_1_div_exp_eq_int: |
|
1889 \<open>- 1 div (2 :: int) ^ n = - 1\<close> |
|
1890 by (induction n) (use div_exp_eq [symmetric, of \<open>- 1 :: int\<close> 1] in \<open>simp_all add: ac_simps\<close>) |
|
1891 |
|
1892 lemma drop_bit_minus_one [simp]: |
|
1893 \<open>drop_bit n (- 1 :: int) = - 1\<close> |
|
1894 by (simp add: drop_bit_eq_div minus_1_div_exp_eq_int) |
|
1895 |
|
1896 lemma take_bit_Suc_from_most: |
|
1897 \<open>take_bit (Suc n) k = 2 ^ n * of_bool (bit k n) + take_bit n k\<close> for k :: int |
|
1898 by (simp only: take_bit_eq_mod power_Suc2) (simp_all add: bit_iff_odd odd_iff_mod_2_eq_one zmod_zmult2_eq) |
|
1899 |
|
1900 lemma take_bit_minus: |
|
1901 \<open>take_bit n (- take_bit n k) = take_bit n (- k)\<close> |
|
1902 for k :: int |
|
1903 by (simp add: take_bit_eq_mod mod_minus_eq) |
|
1904 |
|
1905 lemma take_bit_diff: |
|
1906 \<open>take_bit n (take_bit n k - take_bit n l) = take_bit n (k - l)\<close> |
|
1907 for k l :: int |
|
1908 by (simp add: take_bit_eq_mod mod_diff_eq) |
|
1909 |
|
1910 lemma bit_imp_take_bit_positive: |
|
1911 \<open>0 < take_bit m k\<close> if \<open>n < m\<close> and \<open>bit k n\<close> for k :: int |
|
1912 proof (rule ccontr) |
|
1913 assume \<open>\<not> 0 < take_bit m k\<close> |
|
1914 then have \<open>take_bit m k = 0\<close> |
|
1915 by (auto simp add: not_less intro: order_antisym) |
|
1916 then have \<open>bit (take_bit m k) n = bit 0 n\<close> |
|
1917 by simp |
|
1918 with that show False |
|
1919 by (simp add: bit_take_bit_iff) |
|
1920 qed |
|
1921 |
|
1922 lemma take_bit_mult: |
|
1923 \<open>take_bit n (take_bit n k * take_bit n l) = take_bit n (k * l)\<close> |
|
1924 for k l :: int |
|
1925 by (simp add: take_bit_eq_mod mod_mult_eq) |
|
1926 |
|
1927 lemma (in ring_1) of_nat_nat_take_bit_eq [simp]: |
|
1928 \<open>of_nat (nat (take_bit n k)) = of_int (take_bit n k)\<close> |
|
1929 by simp |
|
1930 |
|
1931 lemma take_bit_minus_small_eq: |
|
1932 \<open>take_bit n (- k) = 2 ^ n - k\<close> if \<open>0 < k\<close> \<open>k \<le> 2 ^ n\<close> for k :: int |
|
1933 proof - |
|
1934 define m where \<open>m = nat k\<close> |
|
1935 with that have \<open>k = int m\<close> and \<open>0 < m\<close> and \<open>m \<le> 2 ^ n\<close> |
|
1936 by simp_all |
|
1937 have \<open>(2 ^ n - m) mod 2 ^ n = 2 ^ n - m\<close> |
|
1938 using \<open>0 < m\<close> by simp |
|
1939 then have \<open>int ((2 ^ n - m) mod 2 ^ n) = int (2 ^ n - m)\<close> |
|
1940 by simp |
|
1941 then have \<open>(2 ^ n - int m) mod 2 ^ n = 2 ^ n - int m\<close> |
|
1942 using \<open>m \<le> 2 ^ n\<close> by (simp only: of_nat_mod of_nat_diff) simp |
|
1943 with \<open>k = int m\<close> have \<open>(2 ^ n - k) mod 2 ^ n = 2 ^ n - k\<close> |
|
1944 by simp |
|
1945 then show ?thesis |
|
1946 by (simp add: take_bit_eq_mod) |
|
1947 qed |
|
1948 |
|
1949 lemma drop_bit_push_bit_int: |
|
1950 \<open>drop_bit m (push_bit n k) = drop_bit (m - n) (push_bit (n - m) k)\<close> for k :: int |
|
1951 by (cases \<open>m \<le> n\<close>) (auto simp add: mult.left_commute [of _ \<open>2 ^ n\<close>] mult.commute [of _ \<open>2 ^ n\<close>] mult.assoc |
|
1952 mult.commute [of k] drop_bit_eq_div push_bit_eq_mult not_le power_add dest!: le_Suc_ex less_imp_Suc_add) |
|
1953 |
|
1954 lemma push_bit_nonnegative_int_iff [simp]: |
|
1955 \<open>push_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
1956 by (simp add: push_bit_eq_mult zero_le_mult_iff power_le_zero_eq) |
|
1957 |
|
1958 lemma push_bit_negative_int_iff [simp]: |
|
1959 \<open>push_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
1960 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
1961 |
|
1962 lemma drop_bit_nonnegative_int_iff [simp]: |
|
1963 \<open>drop_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
1964 by (induction n) (auto simp add: drop_bit_Suc drop_bit_half) |
|
1965 |
|
1966 lemma drop_bit_negative_int_iff [simp]: |
|
1967 \<open>drop_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
1968 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
1969 |
|
1970 lemma set_bit_nonnegative_int_iff [simp]: |
|
1971 \<open>set_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
1972 by (simp add: set_bit_def) |
|
1973 |
|
1974 lemma set_bit_negative_int_iff [simp]: |
|
1975 \<open>set_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
1976 by (simp add: set_bit_def) |
|
1977 |
|
1978 lemma unset_bit_nonnegative_int_iff [simp]: |
|
1979 \<open>unset_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
1980 by (simp add: unset_bit_def) |
|
1981 |
|
1982 lemma unset_bit_negative_int_iff [simp]: |
|
1983 \<open>unset_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
1984 by (simp add: unset_bit_def) |
|
1985 |
|
1986 lemma flip_bit_nonnegative_int_iff [simp]: |
|
1987 \<open>flip_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
1988 by (simp add: flip_bit_def) |
|
1989 |
|
1990 lemma flip_bit_negative_int_iff [simp]: |
|
1991 \<open>flip_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
1992 by (simp add: flip_bit_def) |
|
1993 |
|
1994 lemma set_bit_greater_eq: |
|
1995 \<open>set_bit n k \<ge> k\<close> for k :: int |
|
1996 by (simp add: set_bit_def or_greater_eq) |
|
1997 |
|
1998 lemma unset_bit_less_eq: |
|
1999 \<open>unset_bit n k \<le> k\<close> for k :: int |
|
2000 by (simp add: unset_bit_def and_less_eq) |
|
2001 |
|
2002 lemma set_bit_eq: |
|
2003 \<open>set_bit n k = k + of_bool (\<not> bit k n) * 2 ^ n\<close> for k :: int |
|
2004 proof (rule bit_eqI) |
|
2005 fix m |
|
2006 show \<open>bit (set_bit n k) m \<longleftrightarrow> bit (k + of_bool (\<not> bit k n) * 2 ^ n) m\<close> |
|
2007 proof (cases \<open>m = n\<close>) |
|
2008 case True |
|
2009 then show ?thesis |
|
2010 apply (simp add: bit_set_bit_iff) |
|
2011 apply (simp add: bit_iff_odd div_plus_div_distrib_dvd_right) |
|
2012 done |
|
2013 next |
|
2014 case False |
|
2015 then show ?thesis |
|
2016 apply (clarsimp simp add: bit_set_bit_iff) |
|
2017 apply (subst disjunctive_add) |
|
2018 apply (clarsimp simp add: bit_exp_iff) |
|
2019 apply (clarsimp simp add: bit_or_iff bit_exp_iff) |
|
2020 done |
|
2021 qed |
|
2022 qed |
|
2023 |
|
2024 lemma unset_bit_eq: |
|
2025 \<open>unset_bit n k = k - of_bool (bit k n) * 2 ^ n\<close> for k :: int |
|
2026 proof (rule bit_eqI) |
|
2027 fix m |
|
2028 show \<open>bit (unset_bit n k) m \<longleftrightarrow> bit (k - of_bool (bit k n) * 2 ^ n) m\<close> |
|
2029 proof (cases \<open>m = n\<close>) |
|
2030 case True |
|
2031 then show ?thesis |
|
2032 apply (simp add: bit_unset_bit_iff) |
|
2033 apply (simp add: bit_iff_odd) |
|
2034 using div_plus_div_distrib_dvd_right [of \<open>2 ^ n\<close> \<open>- (2 ^ n)\<close> k] |
|
2035 apply (simp add: dvd_neg_div) |
|
2036 done |
|
2037 next |
|
2038 case False |
|
2039 then show ?thesis |
|
2040 apply (clarsimp simp add: bit_unset_bit_iff) |
|
2041 apply (subst disjunctive_diff) |
|
2042 apply (clarsimp simp add: bit_exp_iff) |
|
2043 apply (clarsimp simp add: bit_and_iff bit_not_iff bit_exp_iff) |
|
2044 done |
|
2045 qed |
|
2046 qed |
|
2047 |
|
2048 lemma and_int_unfold [code]: |
|
2049 \<open>k AND l = (if k = 0 \<or> l = 0 then 0 else if k = - 1 then l else if l = - 1 then k |
|
2050 else (k mod 2) * (l mod 2) + 2 * ((k div 2) AND (l div 2)))\<close> for k l :: int |
|
2051 by (auto simp add: and_int_rec [of k l] zmult_eq_1_iff elim: oddE) |
|
2052 |
|
2053 lemma or_int_unfold [code]: |
|
2054 \<open>k OR l = (if k = - 1 \<or> l = - 1 then - 1 else if k = 0 then l else if l = 0 then k |
|
2055 else max (k mod 2) (l mod 2) + 2 * ((k div 2) OR (l div 2)))\<close> for k l :: int |
|
2056 by (auto simp add: or_int_rec [of k l] elim: oddE) |
|
2057 |
|
2058 lemma xor_int_unfold [code]: |
|
2059 \<open>k XOR l = (if k = - 1 then NOT l else if l = - 1 then NOT k else if k = 0 then l else if l = 0 then k |
|
2060 else \<bar>k mod 2 - l mod 2\<bar> + 2 * ((k div 2) XOR (l div 2)))\<close> for k l :: int |
|
2061 by (auto simp add: xor_int_rec [of k l] not_int_def elim!: oddE) |
|
2062 |
|
2063 |
|
2064 subsection \<open>Instance \<^typ>\<open>nat\<close>\<close> |
|
2065 |
|
2066 instantiation nat :: semiring_bit_operations |
|
2067 begin |
|
2068 |
|
2069 definition and_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
2070 where \<open>m AND n = nat (int m AND int n)\<close> for m n :: nat |
|
2071 |
|
2072 definition or_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
2073 where \<open>m OR n = nat (int m OR int n)\<close> for m n :: nat |
|
2074 |
|
2075 definition xor_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
2076 where \<open>m XOR n = nat (int m XOR int n)\<close> for m n :: nat |
|
2077 |
|
2078 definition mask_nat :: \<open>nat \<Rightarrow> nat\<close> |
|
2079 where \<open>mask n = (2 :: nat) ^ n - 1\<close> |
|
2080 |
|
2081 definition push_bit_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
2082 where \<open>push_bit_nat n m = m * 2 ^ n\<close> |
|
2083 |
|
2084 definition drop_bit_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
2085 where \<open>drop_bit_nat n m = m div 2 ^ n\<close> |
|
2086 |
|
2087 definition take_bit_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
2088 where \<open>take_bit_nat n m = m mod 2 ^ n\<close> |
|
2089 |
|
2090 definition set_bit_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
2091 where \<open>set_bit m n = n OR push_bit m 1\<close> for m n :: nat |
|
2092 |
|
2093 definition unset_bit_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
2094 where \<open>unset_bit m n = nat (unset_bit m (int n))\<close> for m n :: nat |
|
2095 |
|
2096 definition flip_bit_nat :: \<open>nat \<Rightarrow> nat \<Rightarrow> nat\<close> |
|
2097 where \<open>flip_bit m n = n XOR push_bit m 1\<close> for m n :: nat |
|
2098 |
|
2099 instance proof |
|
2100 fix m n q :: nat |
|
2101 show \<open>bit (m AND n) q \<longleftrightarrow> bit m q \<and> bit n q\<close> |
|
2102 by (simp add: and_nat_def bit_simps) |
|
2103 show \<open>bit (m OR n) q \<longleftrightarrow> bit m q \<or> bit n q\<close> |
|
2104 by (simp add: or_nat_def bit_simps) |
|
2105 show \<open>bit (m XOR n) q \<longleftrightarrow> bit m q \<noteq> bit n q\<close> |
|
2106 by (simp add: xor_nat_def bit_simps) |
|
2107 show \<open>bit (unset_bit m n) q \<longleftrightarrow> bit n q \<and> m \<noteq> q\<close> |
|
2108 by (simp add: unset_bit_nat_def bit_simps) |
|
2109 qed (simp_all add: mask_nat_def set_bit_nat_def flip_bit_nat_def push_bit_nat_def drop_bit_nat_def take_bit_nat_def) |
|
2110 |
|
2111 end |
|
2112 |
|
2113 lemma take_bit_nat_less_exp [simp]: |
|
2114 \<open>take_bit n m < 2 ^ n\<close> for n m ::nat |
|
2115 by (simp add: take_bit_eq_mod) |
|
2116 |
|
2117 lemma take_bit_nat_eq_self_iff: |
|
2118 \<open>take_bit n m = m \<longleftrightarrow> m < 2 ^ n\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
2119 for n m :: nat |
|
2120 proof |
|
2121 assume ?P |
|
2122 moreover note take_bit_nat_less_exp [of n m] |
|
2123 ultimately show ?Q |
|
2124 by simp |
|
2125 next |
|
2126 assume ?Q |
|
2127 then show ?P |
|
2128 by (simp add: take_bit_eq_mod) |
|
2129 qed |
|
2130 |
|
2131 lemma take_bit_nat_eq_self: |
|
2132 \<open>take_bit n m = m\<close> if \<open>m < 2 ^ n\<close> for m n :: nat |
|
2133 using that by (simp add: take_bit_nat_eq_self_iff) |
|
2134 |
|
2135 lemma take_bit_nat_less_eq_self [simp]: |
|
2136 \<open>take_bit n m \<le> m\<close> for n m :: nat |
|
2137 by (simp add: take_bit_eq_mod) |
|
2138 |
|
2139 lemma take_bit_nat_less_self_iff: |
|
2140 \<open>take_bit n m < m \<longleftrightarrow> 2 ^ n \<le> m\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
2141 for m n :: nat |
|
2142 proof |
|
2143 assume ?P |
|
2144 then have \<open>take_bit n m \<noteq> m\<close> |
|
2145 by simp |
|
2146 then show \<open>?Q\<close> |
|
2147 by (simp add: take_bit_nat_eq_self_iff) |
|
2148 next |
|
2149 have \<open>take_bit n m < 2 ^ n\<close> |
|
2150 by (fact take_bit_nat_less_exp) |
|
2151 also assume ?Q |
|
2152 finally show ?P . |
|
2153 qed |
|
2154 |
|
2155 lemma bit_push_bit_iff_nat: |
|
2156 \<open>bit (push_bit m q) n \<longleftrightarrow> m \<le> n \<and> bit q (n - m)\<close> for q :: nat |
|
2157 by (auto simp add: bit_push_bit_iff) |
|
2158 |
|
2159 lemma and_nat_rec: |
|
2160 \<open>m AND n = of_bool (odd m \<and> odd n) + 2 * ((m div 2) AND (n div 2))\<close> for m n :: nat |
|
2161 apply (simp add: and_nat_def and_int_rec [of \<open>int m\<close> \<open>int n\<close>] zdiv_int nat_add_distrib nat_mult_distrib) |
|
2162 apply (subst nat_add_distrib) |
|
2163 apply auto |
|
2164 done |
|
2165 |
|
2166 lemma or_nat_rec: |
|
2167 \<open>m OR n = of_bool (odd m \<or> odd n) + 2 * ((m div 2) OR (n div 2))\<close> for m n :: nat |
|
2168 apply (simp add: or_nat_def or_int_rec [of \<open>int m\<close> \<open>int n\<close>] zdiv_int nat_add_distrib nat_mult_distrib) |
|
2169 apply (subst nat_add_distrib) |
|
2170 apply auto |
|
2171 done |
|
2172 |
|
2173 lemma xor_nat_rec: |
|
2174 \<open>m XOR n = of_bool (odd m \<noteq> odd n) + 2 * ((m div 2) XOR (n div 2))\<close> for m n :: nat |
|
2175 apply (simp add: xor_nat_def xor_int_rec [of \<open>int m\<close> \<open>int n\<close>] zdiv_int nat_add_distrib nat_mult_distrib) |
|
2176 apply (subst nat_add_distrib) |
|
2177 apply auto |
|
2178 done |
|
2179 |
|
2180 lemma Suc_0_and_eq [simp]: |
|
2181 \<open>Suc 0 AND n = n mod 2\<close> |
|
2182 using one_and_eq [of n] by simp |
|
2183 |
|
2184 lemma and_Suc_0_eq [simp]: |
|
2185 \<open>n AND Suc 0 = n mod 2\<close> |
|
2186 using and_one_eq [of n] by simp |
|
2187 |
|
2188 lemma Suc_0_or_eq: |
|
2189 \<open>Suc 0 OR n = n + of_bool (even n)\<close> |
|
2190 using one_or_eq [of n] by simp |
|
2191 |
|
2192 lemma or_Suc_0_eq: |
|
2193 \<open>n OR Suc 0 = n + of_bool (even n)\<close> |
|
2194 using or_one_eq [of n] by simp |
|
2195 |
|
2196 lemma Suc_0_xor_eq: |
|
2197 \<open>Suc 0 XOR n = n + of_bool (even n) - of_bool (odd n)\<close> |
|
2198 using one_xor_eq [of n] by simp |
|
2199 |
|
2200 lemma xor_Suc_0_eq: |
|
2201 \<open>n XOR Suc 0 = n + of_bool (even n) - of_bool (odd n)\<close> |
|
2202 using xor_one_eq [of n] by simp |
|
2203 |
|
2204 lemma and_nat_unfold [code]: |
|
2205 \<open>m AND n = (if m = 0 \<or> n = 0 then 0 else (m mod 2) * (n mod 2) + 2 * ((m div 2) AND (n div 2)))\<close> |
|
2206 for m n :: nat |
|
2207 by (auto simp add: and_nat_rec [of m n] elim: oddE) |
|
2208 |
|
2209 lemma or_nat_unfold [code]: |
|
2210 \<open>m OR n = (if m = 0 then n else if n = 0 then m |
|
2211 else max (m mod 2) (n mod 2) + 2 * ((m div 2) OR (n div 2)))\<close> for m n :: nat |
|
2212 by (auto simp add: or_nat_rec [of m n] elim: oddE) |
|
2213 |
|
2214 lemma xor_nat_unfold [code]: |
|
2215 \<open>m XOR n = (if m = 0 then n else if n = 0 then m |
|
2216 else (m mod 2 + n mod 2) mod 2 + 2 * ((m div 2) XOR (n div 2)))\<close> for m n :: nat |
|
2217 by (auto simp add: xor_nat_rec [of m n] elim!: oddE) |
|
2218 |
|
2219 lemma [code]: |
|
2220 \<open>unset_bit 0 m = 2 * (m div 2)\<close> |
|
2221 \<open>unset_bit (Suc n) m = m mod 2 + 2 * unset_bit n (m div 2)\<close> |
|
2222 by (simp_all add: unset_bit_Suc) |
|
2223 |
|
2224 |
|
2225 subsection \<open>Common algebraic structure\<close> |
|
2226 |
|
2227 class unique_euclidean_semiring_with_bit_operations = |
|
2228 unique_euclidean_semiring_with_nat + semiring_bit_operations |
|
2229 begin |
|
2230 |
|
2231 lemma take_bit_of_exp [simp]: |
|
2232 \<open>take_bit m (2 ^ n) = of_bool (n < m) * 2 ^ n\<close> |
|
2233 by (simp add: take_bit_eq_mod exp_mod_exp) |
|
2234 |
|
2235 lemma take_bit_of_2 [simp]: |
|
2236 \<open>take_bit n 2 = of_bool (2 \<le> n) * 2\<close> |
|
2237 using take_bit_of_exp [of n 1] by simp |
|
2238 |
|
2239 lemma take_bit_of_mask: |
|
2240 \<open>take_bit m (2 ^ n - 1) = 2 ^ min m n - 1\<close> |
|
2241 by (simp add: take_bit_eq_mod mask_mod_exp) |
|
2242 |
|
2243 lemma push_bit_eq_0_iff [simp]: |
|
2244 "push_bit n a = 0 \<longleftrightarrow> a = 0" |
|
2245 by (simp add: push_bit_eq_mult) |
|
2246 |
|
2247 lemma take_bit_add: |
|
2248 "take_bit n (take_bit n a + take_bit n b) = take_bit n (a + b)" |
|
2249 by (simp add: take_bit_eq_mod mod_simps) |
|
2250 |
|
2251 lemma take_bit_of_1_eq_0_iff [simp]: |
|
2252 "take_bit n 1 = 0 \<longleftrightarrow> n = 0" |
|
2253 by (simp add: take_bit_eq_mod) |
|
2254 |
|
2255 lemma take_bit_Suc_1 [simp]: |
|
2256 \<open>take_bit (Suc n) 1 = 1\<close> |
|
2257 by (simp add: take_bit_Suc) |
|
2258 |
|
2259 lemma take_bit_Suc_bit0 [simp]: |
|
2260 \<open>take_bit (Suc n) (numeral (Num.Bit0 k)) = take_bit n (numeral k) * 2\<close> |
|
2261 by (simp add: take_bit_Suc numeral_Bit0_div_2) |
|
2262 |
|
2263 lemma take_bit_Suc_bit1 [simp]: |
|
2264 \<open>take_bit (Suc n) (numeral (Num.Bit1 k)) = take_bit n (numeral k) * 2 + 1\<close> |
|
2265 by (simp add: take_bit_Suc numeral_Bit1_div_2 mod_2_eq_odd) |
|
2266 |
|
2267 lemma take_bit_numeral_1 [simp]: |
|
2268 \<open>take_bit (numeral l) 1 = 1\<close> |
|
2269 by (simp add: take_bit_rec [of \<open>numeral l\<close> 1]) |
|
2270 |
|
2271 lemma take_bit_numeral_bit0 [simp]: |
|
2272 \<open>take_bit (numeral l) (numeral (Num.Bit0 k)) = take_bit (pred_numeral l) (numeral k) * 2\<close> |
|
2273 by (simp add: take_bit_rec numeral_Bit0_div_2) |
|
2274 |
|
2275 lemma take_bit_numeral_bit1 [simp]: |
|
2276 \<open>take_bit (numeral l) (numeral (Num.Bit1 k)) = take_bit (pred_numeral l) (numeral k) * 2 + 1\<close> |
|
2277 by (simp add: take_bit_rec numeral_Bit1_div_2 mod_2_eq_odd) |
|
2278 |
|
2279 lemma drop_bit_Suc_bit0 [simp]: |
|
2280 \<open>drop_bit (Suc n) (numeral (Num.Bit0 k)) = drop_bit n (numeral k)\<close> |
|
2281 by (simp add: drop_bit_Suc numeral_Bit0_div_2) |
|
2282 |
|
2283 lemma drop_bit_Suc_bit1 [simp]: |
|
2284 \<open>drop_bit (Suc n) (numeral (Num.Bit1 k)) = drop_bit n (numeral k)\<close> |
|
2285 by (simp add: drop_bit_Suc numeral_Bit1_div_2) |
|
2286 |
|
2287 lemma drop_bit_numeral_bit0 [simp]: |
|
2288 \<open>drop_bit (numeral l) (numeral (Num.Bit0 k)) = drop_bit (pred_numeral l) (numeral k)\<close> |
|
2289 by (simp add: drop_bit_rec numeral_Bit0_div_2) |
|
2290 |
|
2291 lemma drop_bit_numeral_bit1 [simp]: |
|
2292 \<open>drop_bit (numeral l) (numeral (Num.Bit1 k)) = drop_bit (pred_numeral l) (numeral k)\<close> |
|
2293 by (simp add: drop_bit_rec numeral_Bit1_div_2) |
|
2294 |
|
2295 lemma drop_bit_of_nat: |
|
2296 "drop_bit n (of_nat m) = of_nat (drop_bit n m)" |
|
2297 by (simp add: drop_bit_eq_div Bit_Operations.drop_bit_eq_div of_nat_div [of m "2 ^ n"]) |
|
2298 |
|
2299 lemma bit_of_nat_iff_bit [bit_simps]: |
|
2300 \<open>bit (of_nat m) n \<longleftrightarrow> bit m n\<close> |
|
2301 proof - |
|
2302 have \<open>even (m div 2 ^ n) \<longleftrightarrow> even (of_nat (m div 2 ^ n))\<close> |
|
2303 by simp |
|
2304 also have \<open>of_nat (m div 2 ^ n) = of_nat m div of_nat (2 ^ n)\<close> |
|
2305 by (simp add: of_nat_div) |
|
2306 finally show ?thesis |
|
2307 by (simp add: bit_iff_odd semiring_bits_class.bit_iff_odd) |
|
2308 qed |
|
2309 |
|
2310 lemma of_nat_drop_bit: |
|
2311 \<open>of_nat (drop_bit m n) = drop_bit m (of_nat n)\<close> |
|
2312 by (simp add: drop_bit_eq_div Bit_Operations.drop_bit_eq_div of_nat_div) |
|
2313 |
|
2314 lemma bit_push_bit_iff_of_nat_iff [bit_simps]: |
|
2315 \<open>bit (push_bit m (of_nat r)) n \<longleftrightarrow> m \<le> n \<and> bit (of_nat r) (n - m)\<close> |
|
2316 by (auto simp add: bit_push_bit_iff) |
|
2317 |
|
2318 lemma take_bit_sum: |
|
2319 "take_bit n a = (\<Sum>k = 0..<n. push_bit k (of_bool (bit a k)))" |
|
2320 for n :: nat |
|
2321 proof (induction n arbitrary: a) |
|
2322 case 0 |
|
2323 then show ?case |
|
2324 by simp |
|
2325 next |
|
2326 case (Suc n) |
|
2327 have "(\<Sum>k = 0..<Suc n. push_bit k (of_bool (bit a k))) = |
|
2328 of_bool (odd a) + (\<Sum>k = Suc 0..<Suc n. push_bit k (of_bool (bit a k)))" |
|
2329 by (simp add: sum.atLeast_Suc_lessThan ac_simps) |
|
2330 also have "(\<Sum>k = Suc 0..<Suc n. push_bit k (of_bool (bit a k))) |
|
2331 = (\<Sum>k = 0..<n. push_bit k (of_bool (bit (a div 2) k))) * 2" |
|
2332 by (simp only: sum.atLeast_Suc_lessThan_Suc_shift) (simp add: sum_distrib_right push_bit_double drop_bit_Suc bit_Suc) |
|
2333 finally show ?case |
|
2334 using Suc [of "a div 2"] by (simp add: ac_simps take_bit_Suc mod_2_eq_odd) |
|
2335 qed |
|
2336 |
|
2337 end |
|
2338 |
|
2339 instance nat :: unique_euclidean_semiring_with_bit_operations .. |
|
2340 |
|
2341 instance int :: unique_euclidean_semiring_with_bit_operations .. |
|
2342 |
|
2343 |
|
2344 subsection \<open>More properties\<close> |
|
2345 |
|
2346 lemma take_bit_eq_mask_iff: |
|
2347 \<open>take_bit n k = mask n \<longleftrightarrow> take_bit n (k + 1) = 0\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
2348 for k :: int |
|
2349 proof |
|
2350 assume ?P |
|
2351 then have \<open>take_bit n (take_bit n k + take_bit n 1) = 0\<close> |
|
2352 by (simp add: mask_eq_exp_minus_1 take_bit_eq_0_iff) |
|
2353 then show ?Q |
|
2354 by (simp only: take_bit_add) |
|
2355 next |
|
2356 assume ?Q |
|
2357 then have \<open>take_bit n (k + 1) - 1 = - 1\<close> |
|
2358 by simp |
|
2359 then have \<open>take_bit n (take_bit n (k + 1) - 1) = take_bit n (- 1)\<close> |
|
2360 by simp |
|
2361 moreover have \<open>take_bit n (take_bit n (k + 1) - 1) = take_bit n k\<close> |
|
2362 by (simp add: take_bit_eq_mod mod_simps) |
|
2363 ultimately show ?P |
|
2364 by (simp add: take_bit_minus_one_eq_mask) |
|
2365 qed |
|
2366 |
|
2367 lemma take_bit_eq_mask_iff_exp_dvd: |
|
2368 \<open>take_bit n k = mask n \<longleftrightarrow> 2 ^ n dvd k + 1\<close> |
|
2369 for k :: int |
|
2370 by (simp add: take_bit_eq_mask_iff flip: take_bit_eq_0_iff) |
|
2371 |
|
2372 context ring_bit_operations |
|
2373 begin |
|
2374 |
|
2375 lemma even_of_int_iff: |
|
2376 \<open>even (of_int k) \<longleftrightarrow> even k\<close> |
|
2377 by (induction k rule: int_bit_induct) simp_all |
|
2378 |
|
2379 lemma bit_of_int_iff [bit_simps]: |
|
2380 \<open>bit (of_int k) n \<longleftrightarrow> (2::'a) ^ n \<noteq> 0 \<and> bit k n\<close> |
|
2381 proof (cases \<open>(2::'a) ^ n = 0\<close>) |
|
2382 case True |
|
2383 then show ?thesis |
|
2384 by (simp add: exp_eq_0_imp_not_bit) |
|
2385 next |
|
2386 case False |
|
2387 then have \<open>bit (of_int k) n \<longleftrightarrow> bit k n\<close> |
|
2388 proof (induction k arbitrary: n rule: int_bit_induct) |
|
2389 case zero |
|
2390 then show ?case |
|
2391 by simp |
|
2392 next |
|
2393 case minus |
|
2394 then show ?case |
|
2395 by simp |
|
2396 next |
|
2397 case (even k) |
|
2398 then show ?case |
|
2399 using bit_double_iff [of \<open>of_int k\<close> n] Bit_Operations.bit_double_iff [of k n] |
|
2400 by (cases n) (auto simp add: ac_simps dest: mult_not_zero) |
|
2401 next |
|
2402 case (odd k) |
|
2403 then show ?case |
|
2404 using bit_double_iff [of \<open>of_int k\<close> n] |
|
2405 by (cases n) (auto simp add: ac_simps bit_double_iff even_bit_succ_iff Bit_Operations.bit_Suc dest: mult_not_zero) |
|
2406 qed |
|
2407 with False show ?thesis |
|
2408 by simp |
|
2409 qed |
|
2410 |
|
2411 lemma push_bit_of_int: |
|
2412 \<open>push_bit n (of_int k) = of_int (push_bit n k)\<close> |
|
2413 by (simp add: push_bit_eq_mult Bit_Operations.push_bit_eq_mult) |
|
2414 |
|
2415 lemma of_int_push_bit: |
|
2416 \<open>of_int (push_bit n k) = push_bit n (of_int k)\<close> |
|
2417 by (simp add: push_bit_eq_mult Bit_Operations.push_bit_eq_mult) |
|
2418 |
|
2419 lemma take_bit_of_int: |
|
2420 \<open>take_bit n (of_int k) = of_int (take_bit n k)\<close> |
|
2421 by (rule bit_eqI) (simp add: bit_take_bit_iff Bit_Operations.bit_take_bit_iff bit_of_int_iff) |
|
2422 |
|
2423 lemma of_int_take_bit: |
|
2424 \<open>of_int (take_bit n k) = take_bit n (of_int k)\<close> |
|
2425 by (rule bit_eqI) (simp add: bit_take_bit_iff Bit_Operations.bit_take_bit_iff bit_of_int_iff) |
|
2426 |
|
2427 lemma of_int_not_eq: |
|
2428 \<open>of_int (NOT k) = NOT (of_int k)\<close> |
|
2429 by (rule bit_eqI) (simp add: bit_not_iff Bit_Operations.bit_not_iff bit_of_int_iff) |
|
2430 |
|
2431 lemma of_int_and_eq: |
|
2432 \<open>of_int (k AND l) = of_int k AND of_int l\<close> |
|
2433 by (rule bit_eqI) (simp add: bit_of_int_iff bit_and_iff Bit_Operations.bit_and_iff) |
|
2434 |
|
2435 lemma of_int_or_eq: |
|
2436 \<open>of_int (k OR l) = of_int k OR of_int l\<close> |
|
2437 by (rule bit_eqI) (simp add: bit_of_int_iff bit_or_iff Bit_Operations.bit_or_iff) |
|
2438 |
|
2439 lemma of_int_xor_eq: |
|
2440 \<open>of_int (k XOR l) = of_int k XOR of_int l\<close> |
|
2441 by (rule bit_eqI) (simp add: bit_of_int_iff bit_xor_iff Bit_Operations.bit_xor_iff) |
|
2442 |
|
2443 lemma of_int_mask_eq: |
|
2444 \<open>of_int (mask n) = mask n\<close> |
|
2445 by (induction n) (simp_all add: mask_Suc_double Bit_Operations.mask_Suc_double of_int_or_eq) |
|
2446 |
|
2447 end |
|
2448 |
|
2449 lemma take_bit_incr_eq: |
|
2450 \<open>take_bit n (k + 1) = 1 + take_bit n k\<close> if \<open>take_bit n k \<noteq> 2 ^ n - 1\<close> |
|
2451 for k :: int |
|
2452 proof - |
|
2453 from that have \<open>2 ^ n \<noteq> k mod 2 ^ n + 1\<close> |
|
2454 by (simp add: take_bit_eq_mod) |
|
2455 moreover have \<open>k mod 2 ^ n < 2 ^ n\<close> |
|
2456 by simp |
|
2457 ultimately have *: \<open>k mod 2 ^ n + 1 < 2 ^ n\<close> |
|
2458 by linarith |
|
2459 have \<open>(k + 1) mod 2 ^ n = (k mod 2 ^ n + 1) mod 2 ^ n\<close> |
|
2460 by (simp add: mod_simps) |
|
2461 also have \<open>\<dots> = k mod 2 ^ n + 1\<close> |
|
2462 using * by (simp add: zmod_trivial_iff) |
|
2463 finally have \<open>(k + 1) mod 2 ^ n = k mod 2 ^ n + 1\<close> . |
|
2464 then show ?thesis |
|
2465 by (simp add: take_bit_eq_mod) |
|
2466 qed |
|
2467 |
|
2468 lemma take_bit_decr_eq: |
|
2469 \<open>take_bit n (k - 1) = take_bit n k - 1\<close> if \<open>take_bit n k \<noteq> 0\<close> |
|
2470 for k :: int |
|
2471 proof - |
|
2472 from that have \<open>k mod 2 ^ n \<noteq> 0\<close> |
|
2473 by (simp add: take_bit_eq_mod) |
|
2474 moreover have \<open>k mod 2 ^ n \<ge> 0\<close> \<open>k mod 2 ^ n < 2 ^ n\<close> |
|
2475 by simp_all |
|
2476 ultimately have *: \<open>k mod 2 ^ n > 0\<close> |
|
2477 by linarith |
|
2478 have \<open>(k - 1) mod 2 ^ n = (k mod 2 ^ n - 1) mod 2 ^ n\<close> |
|
2479 by (simp add: mod_simps) |
|
2480 also have \<open>\<dots> = k mod 2 ^ n - 1\<close> |
|
2481 by (simp add: zmod_trivial_iff) |
|
2482 (use \<open>k mod 2 ^ n < 2 ^ n\<close> * in linarith) |
|
2483 finally have \<open>(k - 1) mod 2 ^ n = k mod 2 ^ n - 1\<close> . |
|
2484 then show ?thesis |
|
2485 by (simp add: take_bit_eq_mod) |
|
2486 qed |
|
2487 |
|
2488 lemma take_bit_int_greater_eq: |
|
2489 \<open>k + 2 ^ n \<le> take_bit n k\<close> if \<open>k < 0\<close> for k :: int |
|
2490 proof - |
|
2491 have \<open>k + 2 ^ n \<le> take_bit n (k + 2 ^ n)\<close> |
|
2492 proof (cases \<open>k > - (2 ^ n)\<close>) |
|
2493 case False |
|
2494 then have \<open>k + 2 ^ n \<le> 0\<close> |
|
2495 by simp |
|
2496 also note take_bit_nonnegative |
|
2497 finally show ?thesis . |
|
2498 next |
|
2499 case True |
|
2500 with that have \<open>0 \<le> k + 2 ^ n\<close> and \<open>k + 2 ^ n < 2 ^ n\<close> |
|
2501 by simp_all |
|
2502 then show ?thesis |
|
2503 by (simp only: take_bit_eq_mod mod_pos_pos_trivial) |
|
2504 qed |
|
2505 then show ?thesis |
|
2506 by (simp add: take_bit_eq_mod) |
|
2507 qed |
|
2508 |
|
2509 lemma take_bit_int_less_eq: |
|
2510 \<open>take_bit n k \<le> k - 2 ^ n\<close> if \<open>2 ^ n \<le> k\<close> and \<open>n > 0\<close> for k :: int |
|
2511 using that zmod_le_nonneg_dividend [of \<open>k - 2 ^ n\<close> \<open>2 ^ n\<close>] |
|
2512 by (simp add: take_bit_eq_mod) |
|
2513 |
|
2514 lemma take_bit_int_less_eq_self_iff: |
|
2515 \<open>take_bit n k \<le> k \<longleftrightarrow> 0 \<le> k\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
2516 for k :: int |
|
2517 proof |
|
2518 assume ?P |
|
2519 show ?Q |
|
2520 proof (rule ccontr) |
|
2521 assume \<open>\<not> 0 \<le> k\<close> |
|
2522 then have \<open>k < 0\<close> |
|
2523 by simp |
|
2524 with \<open>?P\<close> |
|
2525 have \<open>take_bit n k < 0\<close> |
|
2526 by (rule le_less_trans) |
|
2527 then show False |
|
2528 by simp |
|
2529 qed |
|
2530 next |
|
2531 assume ?Q |
|
2532 then show ?P |
|
2533 by (simp add: take_bit_eq_mod zmod_le_nonneg_dividend) |
|
2534 qed |
|
2535 |
|
2536 lemma take_bit_int_less_self_iff: |
|
2537 \<open>take_bit n k < k \<longleftrightarrow> 2 ^ n \<le> k\<close> |
|
2538 for k :: int |
|
2539 by (auto simp add: less_le take_bit_int_less_eq_self_iff take_bit_int_eq_self_iff |
|
2540 intro: order_trans [of 0 \<open>2 ^ n\<close> k]) |
|
2541 |
|
2542 lemma take_bit_int_greater_self_iff: |
|
2543 \<open>k < take_bit n k \<longleftrightarrow> k < 0\<close> |
|
2544 for k :: int |
|
2545 using take_bit_int_less_eq_self_iff [of n k] by auto |
|
2546 |
|
2547 lemma take_bit_int_greater_eq_self_iff: |
|
2548 \<open>k \<le> take_bit n k \<longleftrightarrow> k < 2 ^ n\<close> |
|
2549 for k :: int |
|
2550 by (auto simp add: le_less take_bit_int_greater_self_iff take_bit_int_eq_self_iff |
|
2551 dest: sym not_sym intro: less_trans [of k 0 \<open>2 ^ n\<close>]) |
|
2552 |
|
2553 lemma minus_numeral_inc_eq: |
|
2554 \<open>- numeral (Num.inc n) = NOT (numeral n :: int)\<close> |
|
2555 by (simp add: not_int_def sub_inc_One_eq add_One) |
|
2556 |
|
2557 lemma sub_one_eq_not_neg: |
|
2558 \<open>Num.sub n num.One = NOT (- numeral n :: int)\<close> |
|
2559 by (simp add: not_int_def) |
|
2560 |
|
2561 lemma bit_numeral_int_iff [bit_simps]: |
|
2562 \<open>bit (numeral m :: int) n \<longleftrightarrow> bit (numeral m :: nat) n\<close> |
|
2563 using bit_of_nat_iff_bit [of \<open>numeral m\<close> n] by simp |
|
2564 |
|
2565 lemma bit_minus_int_iff [bit_simps]: |
|
2566 \<open>bit (- k) n \<longleftrightarrow> \<not> bit (k - 1) n\<close> |
|
2567 for k :: int |
|
2568 using bit_not_int_iff' [of \<open>k - 1\<close>] by simp |
|
2569 |
|
2570 lemma bit_numeral_int_simps [simp]: |
|
2571 \<open>bit (1 :: int) (numeral n) \<longleftrightarrow> bit (0 :: int) (pred_numeral n)\<close> |
|
2572 \<open>bit (numeral (num.Bit0 w) :: int) (numeral n) \<longleftrightarrow> bit (numeral w :: int) (pred_numeral n)\<close> |
|
2573 \<open>bit (numeral (num.Bit1 w) :: int) (numeral n) \<longleftrightarrow> bit (numeral w :: int) (pred_numeral n)\<close> |
|
2574 \<open>bit (numeral (Num.BitM w) :: int) (numeral n) \<longleftrightarrow> \<not> bit (- numeral w :: int) (pred_numeral n)\<close> |
|
2575 \<open>bit (- numeral (num.Bit0 w) :: int) (numeral n) \<longleftrightarrow> bit (- numeral w :: int) (pred_numeral n)\<close> |
|
2576 \<open>bit (- numeral (num.Bit1 w) :: int) (numeral n) \<longleftrightarrow> \<not> bit (numeral w :: int) (pred_numeral n)\<close> |
|
2577 \<open>bit (- numeral (Num.BitM w) :: int) (numeral n) \<longleftrightarrow> bit (- (numeral w) :: int) (pred_numeral n)\<close> |
|
2578 by (simp_all add: bit_1_iff numeral_eq_Suc bit_Suc add_One sub_inc_One_eq bit_minus_int_iff) |
|
2579 |
|
2580 lemma bit_numeral_Bit0_Suc_iff [simp]: |
|
2581 \<open>bit (numeral (Num.Bit0 m) :: int) (Suc n) \<longleftrightarrow> bit (numeral m :: int) n\<close> |
|
2582 by (simp add: bit_Suc) |
|
2583 |
|
2584 lemma bit_numeral_Bit1_Suc_iff [simp]: |
|
2585 \<open>bit (numeral (Num.Bit1 m) :: int) (Suc n) \<longleftrightarrow> bit (numeral m :: int) n\<close> |
|
2586 by (simp add: bit_Suc) |
|
2587 |
|
2588 lemma int_not_numerals [simp]: |
|
2589 \<open>NOT (numeral (Num.Bit0 n) :: int) = - numeral (Num.Bit1 n)\<close> |
|
2590 \<open>NOT (numeral (Num.Bit1 n) :: int) = - numeral (Num.inc (num.Bit1 n))\<close> |
|
2591 \<open>NOT (numeral (Num.BitM n) :: int) = - numeral (num.Bit0 n)\<close> |
|
2592 \<open>NOT (- numeral (Num.Bit0 n) :: int) = numeral (Num.BitM n)\<close> |
|
2593 \<open>NOT (- numeral (Num.Bit1 n) :: int) = numeral (Num.Bit0 n)\<close> |
|
2594 by (simp_all add: not_int_def add_One inc_BitM_eq) |
|
2595 |
|
2596 text \<open>FIXME: The rule sets below are very large (24 rules for each |
|
2597 operator). Is there a simpler way to do this?\<close> |
|
2598 |
|
2599 context |
|
2600 begin |
|
2601 |
|
2602 private lemma eqI: |
|
2603 \<open>k = l\<close> |
|
2604 if num: \<open>\<And>n. bit k (numeral n) \<longleftrightarrow> bit l (numeral n)\<close> |
|
2605 and even: \<open>even k \<longleftrightarrow> even l\<close> |
|
2606 for k l :: int |
|
2607 proof (rule bit_eqI) |
|
2608 fix n |
|
2609 show \<open>bit k n \<longleftrightarrow> bit l n\<close> |
|
2610 proof (cases n) |
|
2611 case 0 |
|
2612 with even show ?thesis |
|
2613 by simp |
|
2614 next |
|
2615 case (Suc n) |
|
2616 with num [of \<open>num_of_nat (Suc n)\<close>] show ?thesis |
|
2617 by (simp only: numeral_num_of_nat) |
|
2618 qed |
|
2619 qed |
|
2620 |
|
2621 lemma int_and_numerals [simp]: |
|
2622 \<open>numeral (Num.Bit0 x) AND numeral (Num.Bit0 y) = (2 :: int) * (numeral x AND numeral y)\<close> |
|
2623 \<open>numeral (Num.Bit0 x) AND numeral (Num.Bit1 y) = (2 :: int) * (numeral x AND numeral y)\<close> |
|
2624 \<open>numeral (Num.Bit1 x) AND numeral (Num.Bit0 y) = (2 :: int) * (numeral x AND numeral y)\<close> |
|
2625 \<open>numeral (Num.Bit1 x) AND numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x AND numeral y)\<close> |
|
2626 \<open>numeral (Num.Bit0 x) AND - numeral (Num.Bit0 y) = (2 :: int) * (numeral x AND - numeral y)\<close> |
|
2627 \<open>numeral (Num.Bit0 x) AND - numeral (Num.Bit1 y) = (2 :: int) * (numeral x AND - numeral (y + Num.One))\<close> |
|
2628 \<open>numeral (Num.Bit1 x) AND - numeral (Num.Bit0 y) = (2 :: int) * (numeral x AND - numeral y)\<close> |
|
2629 \<open>numeral (Num.Bit1 x) AND - numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x AND - numeral (y + Num.One))\<close> |
|
2630 \<open>- numeral (Num.Bit0 x) AND numeral (Num.Bit0 y) = (2 :: int) * (- numeral x AND numeral y)\<close> |
|
2631 \<open>- numeral (Num.Bit0 x) AND numeral (Num.Bit1 y) = (2 :: int) * (- numeral x AND numeral y)\<close> |
|
2632 \<open>- numeral (Num.Bit1 x) AND numeral (Num.Bit0 y) = (2 :: int) * (- numeral (x + Num.One) AND numeral y)\<close> |
|
2633 \<open>- numeral (Num.Bit1 x) AND numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral (x + Num.One) AND numeral y)\<close> |
|
2634 \<open>- numeral (Num.Bit0 x) AND - numeral (Num.Bit0 y) = (2 :: int) * (- numeral x AND - numeral y)\<close> |
|
2635 \<open>- numeral (Num.Bit0 x) AND - numeral (Num.Bit1 y) = (2 :: int) * (- numeral x AND - numeral (y + Num.One))\<close> |
|
2636 \<open>- numeral (Num.Bit1 x) AND - numeral (Num.Bit0 y) = (2 :: int) * (- numeral (x + Num.One) AND - numeral y)\<close> |
|
2637 \<open>- numeral (Num.Bit1 x) AND - numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral (x + Num.One) AND - numeral (y + Num.One))\<close> |
|
2638 \<open>(1::int) AND numeral (Num.Bit0 y) = 0\<close> |
|
2639 \<open>(1::int) AND numeral (Num.Bit1 y) = 1\<close> |
|
2640 \<open>(1::int) AND - numeral (Num.Bit0 y) = 0\<close> |
|
2641 \<open>(1::int) AND - numeral (Num.Bit1 y) = 1\<close> |
|
2642 \<open>numeral (Num.Bit0 x) AND (1::int) = 0\<close> |
|
2643 \<open>numeral (Num.Bit1 x) AND (1::int) = 1\<close> |
|
2644 \<open>- numeral (Num.Bit0 x) AND (1::int) = 0\<close> |
|
2645 \<open>- numeral (Num.Bit1 x) AND (1::int) = 1\<close> |
|
2646 by (auto simp add: bit_and_iff bit_minus_iff even_and_iff bit_double_iff even_bit_succ_iff add_One sub_inc_One_eq intro: eqI) |
|
2647 |
|
2648 lemma int_or_numerals [simp]: |
|
2649 \<open>numeral (Num.Bit0 x) OR numeral (Num.Bit0 y) = (2 :: int) * (numeral x OR numeral y)\<close> |
|
2650 \<open>numeral (Num.Bit0 x) OR numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x OR numeral y)\<close> |
|
2651 \<open>numeral (Num.Bit1 x) OR numeral (Num.Bit0 y) = 1 + (2 :: int) * (numeral x OR numeral y)\<close> |
|
2652 \<open>numeral (Num.Bit1 x) OR numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x OR numeral y)\<close> |
|
2653 \<open>numeral (Num.Bit0 x) OR - numeral (Num.Bit0 y) = (2 :: int) * (numeral x OR - numeral y)\<close> |
|
2654 \<open>numeral (Num.Bit0 x) OR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x OR - numeral (y + Num.One))\<close> |
|
2655 \<open>numeral (Num.Bit1 x) OR - numeral (Num.Bit0 y) = 1 + (2 :: int) * (numeral x OR - numeral y)\<close> |
|
2656 \<open>numeral (Num.Bit1 x) OR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x OR - numeral (y + Num.One))\<close> |
|
2657 \<open>- numeral (Num.Bit0 x) OR numeral (Num.Bit0 y) = (2 :: int) * (- numeral x OR numeral y)\<close> |
|
2658 \<open>- numeral (Num.Bit0 x) OR numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral x OR numeral y)\<close> |
|
2659 \<open>- numeral (Num.Bit1 x) OR numeral (Num.Bit0 y) = 1 + (2 :: int) * (- numeral (x + Num.One) OR numeral y)\<close> |
|
2660 \<open>- numeral (Num.Bit1 x) OR numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral (x + Num.One) OR numeral y)\<close> |
|
2661 \<open>- numeral (Num.Bit0 x) OR - numeral (Num.Bit0 y) = (2 :: int) * (- numeral x OR - numeral y)\<close> |
|
2662 \<open>- numeral (Num.Bit0 x) OR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral x OR - numeral (y + Num.One))\<close> |
|
2663 \<open>- numeral (Num.Bit1 x) OR - numeral (Num.Bit0 y) = 1 + (2 :: int) * (- numeral (x + Num.One) OR - numeral y)\<close> |
|
2664 \<open>- numeral (Num.Bit1 x) OR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral (x + Num.One) OR - numeral (y + Num.One))\<close> |
|
2665 \<open>(1::int) OR numeral (Num.Bit0 y) = numeral (Num.Bit1 y)\<close> |
|
2666 \<open>(1::int) OR numeral (Num.Bit1 y) = numeral (Num.Bit1 y)\<close> |
|
2667 \<open>(1::int) OR - numeral (Num.Bit0 y) = - numeral (Num.BitM y)\<close> |
|
2668 \<open>(1::int) OR - numeral (Num.Bit1 y) = - numeral (Num.Bit1 y)\<close> |
|
2669 \<open>numeral (Num.Bit0 x) OR (1::int) = numeral (Num.Bit1 x)\<close> |
|
2670 \<open>numeral (Num.Bit1 x) OR (1::int) = numeral (Num.Bit1 x)\<close> |
|
2671 \<open>- numeral (Num.Bit0 x) OR (1::int) = - numeral (Num.BitM x)\<close> |
|
2672 \<open>- numeral (Num.Bit1 x) OR (1::int) = - numeral (Num.Bit1 x)\<close> |
|
2673 by (auto simp add: bit_or_iff bit_minus_iff even_or_iff bit_double_iff even_bit_succ_iff add_One sub_inc_One_eq sub_BitM_One_eq intro: eqI) |
|
2674 |
|
2675 lemma int_xor_numerals [simp]: |
|
2676 \<open>numeral (Num.Bit0 x) XOR numeral (Num.Bit0 y) = (2 :: int) * (numeral x XOR numeral y)\<close> |
|
2677 \<open>numeral (Num.Bit0 x) XOR numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x XOR numeral y)\<close> |
|
2678 \<open>numeral (Num.Bit1 x) XOR numeral (Num.Bit0 y) = 1 + (2 :: int) * (numeral x XOR numeral y)\<close> |
|
2679 \<open>numeral (Num.Bit1 x) XOR numeral (Num.Bit1 y) = (2 :: int) * (numeral x XOR numeral y)\<close> |
|
2680 \<open>numeral (Num.Bit0 x) XOR - numeral (Num.Bit0 y) = (2 :: int) * (numeral x XOR - numeral y)\<close> |
|
2681 \<open>numeral (Num.Bit0 x) XOR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x XOR - numeral (y + Num.One))\<close> |
|
2682 \<open>numeral (Num.Bit1 x) XOR - numeral (Num.Bit0 y) = 1 + (2 :: int) * (numeral x XOR - numeral y)\<close> |
|
2683 \<open>numeral (Num.Bit1 x) XOR - numeral (Num.Bit1 y) = (2 :: int) * (numeral x XOR - numeral (y + Num.One))\<close> |
|
2684 \<open>- numeral (Num.Bit0 x) XOR numeral (Num.Bit0 y) = (2 :: int) * (- numeral x XOR numeral y)\<close> |
|
2685 \<open>- numeral (Num.Bit0 x) XOR numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral x XOR numeral y)\<close> |
|
2686 \<open>- numeral (Num.Bit1 x) XOR numeral (Num.Bit0 y) = 1 + (2 :: int) * (- numeral (x + Num.One) XOR numeral y)\<close> |
|
2687 \<open>- numeral (Num.Bit1 x) XOR numeral (Num.Bit1 y) = (2 :: int) * (- numeral (x + Num.One) XOR numeral y)\<close> |
|
2688 \<open>- numeral (Num.Bit0 x) XOR - numeral (Num.Bit0 y) = (2 :: int) * (- numeral x XOR - numeral y)\<close> |
|
2689 \<open>- numeral (Num.Bit0 x) XOR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral x XOR - numeral (y + Num.One))\<close> |
|
2690 \<open>- numeral (Num.Bit1 x) XOR - numeral (Num.Bit0 y) = 1 + (2 :: int) * (- numeral (x + Num.One) XOR - numeral y)\<close> |
|
2691 \<open>- numeral (Num.Bit1 x) XOR - numeral (Num.Bit1 y) = (2 :: int) * (- numeral (x + Num.One) XOR - numeral (y + Num.One))\<close> |
|
2692 \<open>(1::int) XOR numeral (Num.Bit0 y) = numeral (Num.Bit1 y)\<close> |
|
2693 \<open>(1::int) XOR numeral (Num.Bit1 y) = numeral (Num.Bit0 y)\<close> |
|
2694 \<open>(1::int) XOR - numeral (Num.Bit0 y) = - numeral (Num.BitM y)\<close> |
|
2695 \<open>(1::int) XOR - numeral (Num.Bit1 y) = - numeral (Num.Bit0 (y + Num.One))\<close> |
|
2696 \<open>numeral (Num.Bit0 x) XOR (1::int) = numeral (Num.Bit1 x)\<close> |
|
2697 \<open>numeral (Num.Bit1 x) XOR (1::int) = numeral (Num.Bit0 x)\<close> |
|
2698 \<open>- numeral (Num.Bit0 x) XOR (1::int) = - numeral (Num.BitM x)\<close> |
|
2699 \<open>- numeral (Num.Bit1 x) XOR (1::int) = - numeral (Num.Bit0 (x + Num.One))\<close> |
|
2700 by (auto simp add: bit_xor_iff bit_minus_iff even_xor_iff bit_double_iff even_bit_succ_iff add_One sub_inc_One_eq sub_BitM_One_eq intro: eqI) |
|
2701 |
|
2702 end |
|
2703 |
|
2704 context semiring_bit_operations |
|
2705 begin |
|
2706 |
|
2707 lemma push_bit_of_nat: |
|
2708 \<open>push_bit n (of_nat m) = of_nat (push_bit n m)\<close> |
|
2709 by (simp add: push_bit_eq_mult Bit_Operations.push_bit_eq_mult) |
|
2710 |
|
2711 lemma of_nat_push_bit: |
|
2712 \<open>of_nat (push_bit m n) = push_bit m (of_nat n)\<close> |
|
2713 by (simp add: push_bit_eq_mult Bit_Operations.push_bit_eq_mult) |
|
2714 |
|
2715 lemma take_bit_of_nat: |
|
2716 \<open>take_bit n (of_nat m) = of_nat (take_bit n m)\<close> |
|
2717 by (rule bit_eqI) (simp add: bit_take_bit_iff Bit_Operations.bit_take_bit_iff bit_of_nat_iff) |
|
2718 |
|
2719 lemma of_nat_take_bit: |
|
2720 \<open>of_nat (take_bit n m) = take_bit n (of_nat m)\<close> |
|
2721 by (rule bit_eqI) (simp add: bit_take_bit_iff Bit_Operations.bit_take_bit_iff bit_of_nat_iff) |
|
2722 |
|
2723 end |
|
2724 |
|
2725 lemma push_bit_nat_eq: |
|
2726 \<open>push_bit n (nat k) = nat (push_bit n k)\<close> |
|
2727 by (cases \<open>k \<ge> 0\<close>) (simp_all add: push_bit_eq_mult nat_mult_distrib not_le mult_nonneg_nonpos2) |
|
2728 |
|
2729 lemma drop_bit_nat_eq: |
|
2730 \<open>drop_bit n (nat k) = nat (drop_bit n k)\<close> |
|
2731 apply (cases \<open>k \<ge> 0\<close>) |
|
2732 apply (simp_all add: drop_bit_eq_div nat_div_distrib nat_power_eq not_le) |
|
2733 apply (simp add: divide_int_def) |
|
2734 done |
|
2735 |
|
2736 lemma take_bit_nat_eq: |
|
2737 \<open>take_bit n (nat k) = nat (take_bit n k)\<close> if \<open>k \<ge> 0\<close> |
|
2738 using that by (simp add: take_bit_eq_mod nat_mod_distrib nat_power_eq) |
|
2739 |
|
2740 lemma nat_take_bit_eq: |
|
2741 \<open>nat (take_bit n k) = take_bit n (nat k)\<close> |
|
2742 if \<open>k \<ge> 0\<close> |
|
2743 using that by (simp add: take_bit_eq_mod nat_mod_distrib nat_power_eq) |
|
2744 |
|
2745 lemma not_exp_less_eq_0_int [simp]: |
|
2746 \<open>\<not> 2 ^ n \<le> (0::int)\<close> |
|
2747 by (simp add: power_le_zero_eq) |
|
2748 |
|
2749 lemma half_nonnegative_int_iff [simp]: |
|
2750 \<open>k div 2 \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
2751 proof (cases \<open>k \<ge> 0\<close>) |
|
2752 case True |
|
2753 then show ?thesis |
|
2754 by (auto simp add: divide_int_def sgn_1_pos) |
|
2755 next |
|
2756 case False |
|
2757 then show ?thesis |
|
2758 by (auto simp add: divide_int_def not_le elim!: evenE) |
|
2759 qed |
|
2760 |
|
2761 lemma half_negative_int_iff [simp]: |
|
2762 \<open>k div 2 < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
2763 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
2764 |
|
2765 lemma push_bit_of_Suc_0 [simp]: |
|
2766 "push_bit n (Suc 0) = 2 ^ n" |
|
2767 using push_bit_of_1 [where ?'a = nat] by simp |
|
2768 |
|
2769 lemma take_bit_of_Suc_0 [simp]: |
|
2770 "take_bit n (Suc 0) = of_bool (0 < n)" |
|
2771 using take_bit_of_1 [where ?'a = nat] by simp |
|
2772 |
|
2773 lemma drop_bit_of_Suc_0 [simp]: |
|
2774 "drop_bit n (Suc 0) = of_bool (n = 0)" |
|
2775 using drop_bit_of_1 [where ?'a = nat] by simp |
1877 |
2776 |
1878 lemma int_bit_bound: |
2777 lemma int_bit_bound: |
1879 fixes k :: int |
2778 fixes k :: int |
1880 obtains n where \<open>\<And>m. n \<le> m \<Longrightarrow> bit k m \<longleftrightarrow> bit k n\<close> |
2779 obtains n where \<open>\<And>m. n \<le> m \<Longrightarrow> bit k m \<longleftrightarrow> bit k n\<close> |
1881 and \<open>n > 0 \<Longrightarrow> bit k (n - 1) \<noteq> bit k n\<close> |
2780 and \<open>n > 0 \<Longrightarrow> bit k (n - 1) \<noteq> bit k n\<close> |
1946 using \<open>\<And>m. n \<le> m \<Longrightarrow> bit k m = bit k n\<close> apply blast |
2845 using \<open>\<And>m. n \<le> m \<Longrightarrow> bit k m = bit k n\<close> apply blast |
1947 using \<open>bit k (Max N) \<noteq> bit k n\<close> n_def by auto |
2846 using \<open>bit k (Max N) \<noteq> bit k n\<close> n_def by auto |
1948 qed |
2847 qed |
1949 qed |
2848 qed |
1950 |
2849 |
1951 instantiation int :: ring_bit_operations |
2850 context semiring_bit_operations |
1952 begin |
2851 begin |
1953 |
2852 |
1954 definition not_int :: \<open>int \<Rightarrow> int\<close> |
2853 lemma of_nat_and_eq: |
1955 where \<open>not_int k = - k - 1\<close> |
2854 \<open>of_nat (m AND n) = of_nat m AND of_nat n\<close> |
1956 |
2855 by (rule bit_eqI) (simp add: bit_of_nat_iff bit_and_iff Bit_Operations.bit_and_iff) |
1957 lemma not_int_rec: |
2856 |
1958 \<open>NOT k = of_bool (even k) + 2 * NOT (k div 2)\<close> for k :: int |
2857 lemma of_nat_or_eq: |
1959 by (auto simp add: not_int_def elim: oddE) |
2858 \<open>of_nat (m OR n) = of_nat m OR of_nat n\<close> |
1960 |
2859 by (rule bit_eqI) (simp add: bit_of_nat_iff bit_or_iff Bit_Operations.bit_or_iff) |
1961 lemma even_not_iff_int: |
2860 |
1962 \<open>even (NOT k) \<longleftrightarrow> odd k\<close> for k :: int |
2861 lemma of_nat_xor_eq: |
1963 by (simp add: not_int_def) |
2862 \<open>of_nat (m XOR n) = of_nat m XOR of_nat n\<close> |
1964 |
2863 by (rule bit_eqI) (simp add: bit_of_nat_iff bit_xor_iff Bit_Operations.bit_xor_iff) |
1965 lemma not_int_div_2: |
|
1966 \<open>NOT k div 2 = NOT (k div 2)\<close> for k :: int |
|
1967 by (cases k) (simp_all add: not_int_def divide_int_def nat_add_distrib) |
|
1968 |
|
1969 lemma bit_not_int_iff [bit_simps]: |
|
1970 \<open>bit (NOT k) n \<longleftrightarrow> \<not> bit k n\<close> |
|
1971 for k :: int |
|
1972 by (simp add: bit_not_int_iff' not_int_def) |
|
1973 |
|
1974 function and_int :: \<open>int \<Rightarrow> int \<Rightarrow> int\<close> |
|
1975 where \<open>(k::int) AND l = (if k \<in> {0, - 1} \<and> l \<in> {0, - 1} |
|
1976 then - of_bool (odd k \<and> odd l) |
|
1977 else of_bool (odd k \<and> odd l) + 2 * ((k div 2) AND (l div 2)))\<close> |
|
1978 by auto |
|
1979 |
|
1980 termination proof (relation \<open>measure (\<lambda>(k, l). nat (\<bar>k\<bar> + \<bar>l\<bar>))\<close>) |
|
1981 show \<open>wf (measure (\<lambda>(k, l). nat (\<bar>k\<bar> + \<bar>l\<bar>)))\<close> |
|
1982 by simp |
|
1983 show \<open>((k div 2, l div 2), k, l) \<in> measure (\<lambda>(k, l). nat (\<bar>k\<bar> + \<bar>l\<bar>))\<close> |
|
1984 if \<open>\<not> (k \<in> {0, - 1} \<and> l \<in> {0, - 1})\<close> for k l |
|
1985 proof - |
|
1986 have less_eq: \<open>\<bar>k div 2\<bar> \<le> \<bar>k\<bar>\<close> for k :: int |
|
1987 by (cases k) (simp_all add: divide_int_def nat_add_distrib) |
|
1988 have less: \<open>\<bar>k div 2\<bar> < \<bar>k\<bar>\<close> if \<open>k \<notin> {0, - 1}\<close> for k :: int |
|
1989 proof (cases k) |
|
1990 case (nonneg n) |
|
1991 with that show ?thesis |
|
1992 by (simp add: int_div_less_self) |
|
1993 next |
|
1994 case (neg n) |
|
1995 with that have \<open>n \<noteq> 0\<close> |
|
1996 by simp |
|
1997 then have \<open>n div 2 < n\<close> |
|
1998 by (simp add: div_less_iff_less_mult) |
|
1999 with neg that show ?thesis |
|
2000 by (simp add: divide_int_def nat_add_distrib) |
|
2001 qed |
|
2002 from that have *: \<open>k \<notin> {0, - 1} \<or> l \<notin> {0, - 1}\<close> |
|
2003 by simp |
|
2004 then have \<open>0 < \<bar>k\<bar> + \<bar>l\<bar>\<close> |
|
2005 by auto |
|
2006 moreover from * have \<open>\<bar>k div 2\<bar> + \<bar>l div 2\<bar> < \<bar>k\<bar> + \<bar>l\<bar>\<close> |
|
2007 proof |
|
2008 assume \<open>k \<notin> {0, - 1}\<close> |
|
2009 then have \<open>\<bar>k div 2\<bar> < \<bar>k\<bar>\<close> |
|
2010 by (rule less) |
|
2011 with less_eq [of l] show ?thesis |
|
2012 by auto |
|
2013 next |
|
2014 assume \<open>l \<notin> {0, - 1}\<close> |
|
2015 then have \<open>\<bar>l div 2\<bar> < \<bar>l\<bar>\<close> |
|
2016 by (rule less) |
|
2017 with less_eq [of k] show ?thesis |
|
2018 by auto |
|
2019 qed |
|
2020 ultimately show ?thesis |
|
2021 by simp |
|
2022 qed |
|
2023 qed |
|
2024 |
|
2025 declare and_int.simps [simp del] |
|
2026 |
|
2027 lemma and_int_rec: |
|
2028 \<open>k AND l = of_bool (odd k \<and> odd l) + 2 * ((k div 2) AND (l div 2))\<close> |
|
2029 for k l :: int |
|
2030 proof (cases \<open>k \<in> {0, - 1} \<and> l \<in> {0, - 1}\<close>) |
|
2031 case True |
|
2032 then show ?thesis |
|
2033 by auto (simp_all add: and_int.simps) |
|
2034 next |
|
2035 case False |
|
2036 then show ?thesis |
|
2037 by (auto simp add: ac_simps and_int.simps [of k l]) |
|
2038 qed |
|
2039 |
|
2040 lemma bit_and_int_iff: |
|
2041 \<open>bit (k AND l) n \<longleftrightarrow> bit k n \<and> bit l n\<close> for k l :: int |
|
2042 proof (induction n arbitrary: k l) |
|
2043 case 0 |
|
2044 then show ?case |
|
2045 by (simp add: and_int_rec [of k l]) |
|
2046 next |
|
2047 case (Suc n) |
|
2048 then show ?case |
|
2049 by (simp add: and_int_rec [of k l] bit_Suc) |
|
2050 qed |
|
2051 |
|
2052 lemma even_and_iff_int: |
|
2053 \<open>even (k AND l) \<longleftrightarrow> even k \<or> even l\<close> for k l :: int |
|
2054 using bit_and_int_iff [of k l 0] by auto |
|
2055 |
|
2056 definition or_int :: \<open>int \<Rightarrow> int \<Rightarrow> int\<close> |
|
2057 where \<open>k OR l = NOT (NOT k AND NOT l)\<close> for k l :: int |
|
2058 |
|
2059 lemma or_int_rec: |
|
2060 \<open>k OR l = of_bool (odd k \<or> odd l) + 2 * ((k div 2) OR (l div 2))\<close> |
|
2061 for k l :: int |
|
2062 using and_int_rec [of \<open>NOT k\<close> \<open>NOT l\<close>] |
|
2063 by (simp add: or_int_def even_not_iff_int not_int_div_2) |
|
2064 (simp_all add: not_int_def) |
|
2065 |
|
2066 lemma bit_or_int_iff: |
|
2067 \<open>bit (k OR l) n \<longleftrightarrow> bit k n \<or> bit l n\<close> for k l :: int |
|
2068 by (simp add: or_int_def bit_not_int_iff bit_and_int_iff) |
|
2069 |
|
2070 definition xor_int :: \<open>int \<Rightarrow> int \<Rightarrow> int\<close> |
|
2071 where \<open>k XOR l = k AND NOT l OR NOT k AND l\<close> for k l :: int |
|
2072 |
|
2073 lemma xor_int_rec: |
|
2074 \<open>k XOR l = of_bool (odd k \<noteq> odd l) + 2 * ((k div 2) XOR (l div 2))\<close> |
|
2075 for k l :: int |
|
2076 by (simp add: xor_int_def or_int_rec [of \<open>k AND NOT l\<close> \<open>NOT k AND l\<close>] even_and_iff_int even_not_iff_int) |
|
2077 (simp add: and_int_rec [of \<open>NOT k\<close> \<open>l\<close>] and_int_rec [of \<open>k\<close> \<open>NOT l\<close>] not_int_div_2) |
|
2078 |
|
2079 lemma bit_xor_int_iff: |
|
2080 \<open>bit (k XOR l) n \<longleftrightarrow> bit k n \<noteq> bit l n\<close> for k l :: int |
|
2081 by (auto simp add: xor_int_def bit_or_int_iff bit_and_int_iff bit_not_int_iff) |
|
2082 |
|
2083 definition mask_int :: \<open>nat \<Rightarrow> int\<close> |
|
2084 where \<open>mask n = (2 :: int) ^ n - 1\<close> |
|
2085 |
|
2086 definition set_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
2087 where \<open>set_bit n k = k OR push_bit n 1\<close> for k :: int |
|
2088 |
|
2089 definition unset_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
2090 where \<open>unset_bit n k = k AND NOT (push_bit n 1)\<close> for k :: int |
|
2091 |
|
2092 definition flip_bit_int :: \<open>nat \<Rightarrow> int \<Rightarrow> int\<close> |
|
2093 where \<open>flip_bit n k = k XOR push_bit n 1\<close> for k :: int |
|
2094 |
|
2095 instance proof |
|
2096 fix k l :: int and m n :: nat |
|
2097 show \<open>- k = NOT (k - 1)\<close> |
|
2098 by (simp add: not_int_def) |
|
2099 show \<open>bit (k AND l) n \<longleftrightarrow> bit k n \<and> bit l n\<close> |
|
2100 by (fact bit_and_int_iff) |
|
2101 show \<open>bit (k OR l) n \<longleftrightarrow> bit k n \<or> bit l n\<close> |
|
2102 by (fact bit_or_int_iff) |
|
2103 show \<open>bit (k XOR l) n \<longleftrightarrow> bit k n \<noteq> bit l n\<close> |
|
2104 by (fact bit_xor_int_iff) |
|
2105 show \<open>bit (unset_bit m k) n \<longleftrightarrow> bit k n \<and> m \<noteq> n\<close> |
|
2106 proof - |
|
2107 have \<open>unset_bit m k = k AND NOT (push_bit m 1)\<close> |
|
2108 by (simp add: unset_bit_int_def) |
|
2109 also have \<open>NOT (push_bit m 1 :: int) = - (push_bit m 1 + 1)\<close> |
|
2110 by (simp add: not_int_def) |
|
2111 finally show ?thesis by (simp only: bit_simps bit_and_int_iff) (auto simp add: bit_simps) |
|
2112 qed |
|
2113 qed (simp_all add: bit_not_int_iff mask_int_def set_bit_int_def flip_bit_int_def) |
|
2114 |
2864 |
2115 end |
2865 end |
2116 |
|
2117 lemma mask_half_int: |
|
2118 \<open>mask n div 2 = (mask (n - 1) :: int)\<close> |
|
2119 by (cases n) (simp_all add: mask_eq_exp_minus_1 algebra_simps) |
|
2120 |
|
2121 lemma mask_nonnegative_int [simp]: |
|
2122 \<open>mask n \<ge> (0::int)\<close> |
|
2123 by (simp add: mask_eq_exp_minus_1) |
|
2124 |
|
2125 lemma not_mask_negative_int [simp]: |
|
2126 \<open>\<not> mask n < (0::int)\<close> |
|
2127 by (simp add: not_less) |
|
2128 |
|
2129 lemma not_nonnegative_int_iff [simp]: |
|
2130 \<open>NOT k \<ge> 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
2131 by (simp add: not_int_def) |
|
2132 |
|
2133 lemma not_negative_int_iff [simp]: |
|
2134 \<open>NOT k < 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
2135 by (subst Not_eq_iff [symmetric]) (simp add: not_less not_le) |
|
2136 |
|
2137 lemma and_nonnegative_int_iff [simp]: |
|
2138 \<open>k AND l \<ge> 0 \<longleftrightarrow> k \<ge> 0 \<or> l \<ge> 0\<close> for k l :: int |
|
2139 proof (induction k arbitrary: l rule: int_bit_induct) |
|
2140 case zero |
|
2141 then show ?case |
|
2142 by simp |
|
2143 next |
|
2144 case minus |
|
2145 then show ?case |
|
2146 by simp |
|
2147 next |
|
2148 case (even k) |
|
2149 then show ?case |
|
2150 using and_int_rec [of \<open>k * 2\<close> l] |
|
2151 by (simp add: pos_imp_zdiv_nonneg_iff zero_le_mult_iff) |
|
2152 next |
|
2153 case (odd k) |
|
2154 from odd have \<open>0 \<le> k AND l div 2 \<longleftrightarrow> 0 \<le> k \<or> 0 \<le> l div 2\<close> |
|
2155 by simp |
|
2156 then have \<open>0 \<le> (1 + k * 2) div 2 AND l div 2 \<longleftrightarrow> 0 \<le> (1 + k * 2) div 2 \<or> 0 \<le> l div 2\<close> |
|
2157 by simp |
|
2158 with and_int_rec [of \<open>1 + k * 2\<close> l] |
|
2159 show ?case |
|
2160 by (auto simp add: zero_le_mult_iff not_le) |
|
2161 qed |
|
2162 |
|
2163 lemma and_negative_int_iff [simp]: |
|
2164 \<open>k AND l < 0 \<longleftrightarrow> k < 0 \<and> l < 0\<close> for k l :: int |
|
2165 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
2166 |
|
2167 lemma and_less_eq: |
|
2168 \<open>k AND l \<le> k\<close> if \<open>l < 0\<close> for k l :: int |
|
2169 using that proof (induction k arbitrary: l rule: int_bit_induct) |
|
2170 case zero |
|
2171 then show ?case |
|
2172 by simp |
|
2173 next |
|
2174 case minus |
|
2175 then show ?case |
|
2176 by simp |
|
2177 next |
|
2178 case (even k) |
|
2179 from even.IH [of \<open>l div 2\<close>] even.hyps even.prems |
|
2180 show ?case |
|
2181 by (simp add: and_int_rec [of _ l]) |
|
2182 next |
|
2183 case (odd k) |
|
2184 from odd.IH [of \<open>l div 2\<close>] odd.hyps odd.prems |
|
2185 show ?case |
|
2186 by (simp add: and_int_rec [of _ l]) |
|
2187 qed |
|
2188 |
|
2189 lemma or_nonnegative_int_iff [simp]: |
|
2190 \<open>k OR l \<ge> 0 \<longleftrightarrow> k \<ge> 0 \<and> l \<ge> 0\<close> for k l :: int |
|
2191 by (simp only: or_eq_not_not_and not_nonnegative_int_iff) simp |
|
2192 |
|
2193 lemma or_negative_int_iff [simp]: |
|
2194 \<open>k OR l < 0 \<longleftrightarrow> k < 0 \<or> l < 0\<close> for k l :: int |
|
2195 by (subst Not_eq_iff [symmetric]) (simp add: not_less) |
|
2196 |
|
2197 lemma or_greater_eq: |
|
2198 \<open>k OR l \<ge> k\<close> if \<open>l \<ge> 0\<close> for k l :: int |
|
2199 using that proof (induction k arbitrary: l rule: int_bit_induct) |
|
2200 case zero |
|
2201 then show ?case |
|
2202 by simp |
|
2203 next |
|
2204 case minus |
|
2205 then show ?case |
|
2206 by simp |
|
2207 next |
|
2208 case (even k) |
|
2209 from even.IH [of \<open>l div 2\<close>] even.hyps even.prems |
|
2210 show ?case |
|
2211 by (simp add: or_int_rec [of _ l]) |
|
2212 next |
|
2213 case (odd k) |
|
2214 from odd.IH [of \<open>l div 2\<close>] odd.hyps odd.prems |
|
2215 show ?case |
|
2216 by (simp add: or_int_rec [of _ l]) |
|
2217 qed |
|
2218 |
|
2219 lemma xor_nonnegative_int_iff [simp]: |
|
2220 \<open>k XOR l \<ge> 0 \<longleftrightarrow> (k \<ge> 0 \<longleftrightarrow> l \<ge> 0)\<close> for k l :: int |
|
2221 by (simp only: bit.xor_def or_nonnegative_int_iff) auto |
|
2222 |
|
2223 lemma xor_negative_int_iff [simp]: |
|
2224 \<open>k XOR l < 0 \<longleftrightarrow> (k < 0) \<noteq> (l < 0)\<close> for k l :: int |
|
2225 by (subst Not_eq_iff [symmetric]) (auto simp add: not_less) |
|
2226 |
|
2227 lemma OR_upper: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2228 fixes x y :: int |
|
2229 assumes \<open>0 \<le> x\<close> \<open>x < 2 ^ n\<close> \<open>y < 2 ^ n\<close> |
|
2230 shows \<open>x OR y < 2 ^ n\<close> |
|
2231 using assms proof (induction x arbitrary: y n rule: int_bit_induct) |
|
2232 case zero |
|
2233 then show ?case |
|
2234 by simp |
|
2235 next |
|
2236 case minus |
|
2237 then show ?case |
|
2238 by simp |
|
2239 next |
|
2240 case (even x) |
|
2241 from even.IH [of \<open>n - 1\<close> \<open>y div 2\<close>] even.prems even.hyps |
|
2242 show ?case |
|
2243 by (cases n) (auto simp add: or_int_rec [of \<open>_ * 2\<close>] elim: oddE) |
|
2244 next |
|
2245 case (odd x) |
|
2246 from odd.IH [of \<open>n - 1\<close> \<open>y div 2\<close>] odd.prems odd.hyps |
|
2247 show ?case |
|
2248 by (cases n) (auto simp add: or_int_rec [of \<open>1 + _ * 2\<close>], linarith) |
|
2249 qed |
|
2250 |
|
2251 lemma XOR_upper: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2252 fixes x y :: int |
|
2253 assumes \<open>0 \<le> x\<close> \<open>x < 2 ^ n\<close> \<open>y < 2 ^ n\<close> |
|
2254 shows \<open>x XOR y < 2 ^ n\<close> |
|
2255 using assms proof (induction x arbitrary: y n rule: int_bit_induct) |
|
2256 case zero |
|
2257 then show ?case |
|
2258 by simp |
|
2259 next |
|
2260 case minus |
|
2261 then show ?case |
|
2262 by simp |
|
2263 next |
|
2264 case (even x) |
|
2265 from even.IH [of \<open>n - 1\<close> \<open>y div 2\<close>] even.prems even.hyps |
|
2266 show ?case |
|
2267 by (cases n) (auto simp add: xor_int_rec [of \<open>_ * 2\<close>] elim: oddE) |
|
2268 next |
|
2269 case (odd x) |
|
2270 from odd.IH [of \<open>n - 1\<close> \<open>y div 2\<close>] odd.prems odd.hyps |
|
2271 show ?case |
|
2272 by (cases n) (auto simp add: xor_int_rec [of \<open>1 + _ * 2\<close>]) |
|
2273 qed |
|
2274 |
|
2275 lemma AND_lower [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2276 fixes x y :: int |
|
2277 assumes \<open>0 \<le> x\<close> |
|
2278 shows \<open>0 \<le> x AND y\<close> |
|
2279 using assms by simp |
|
2280 |
|
2281 lemma OR_lower [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2282 fixes x y :: int |
|
2283 assumes \<open>0 \<le> x\<close> \<open>0 \<le> y\<close> |
|
2284 shows \<open>0 \<le> x OR y\<close> |
|
2285 using assms by simp |
|
2286 |
|
2287 lemma XOR_lower [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2288 fixes x y :: int |
|
2289 assumes \<open>0 \<le> x\<close> \<open>0 \<le> y\<close> |
|
2290 shows \<open>0 \<le> x XOR y\<close> |
|
2291 using assms by simp |
|
2292 |
|
2293 lemma AND_upper1 [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2294 fixes x y :: int |
|
2295 assumes \<open>0 \<le> x\<close> |
|
2296 shows \<open>x AND y \<le> x\<close> |
|
2297 using assms proof (induction x arbitrary: y rule: int_bit_induct) |
|
2298 case (odd k) |
|
2299 then have \<open>k AND y div 2 \<le> k\<close> |
|
2300 by simp |
|
2301 then show ?case |
|
2302 by (simp add: and_int_rec [of \<open>1 + _ * 2\<close>]) |
|
2303 qed (simp_all add: and_int_rec [of \<open>_ * 2\<close>]) |
|
2304 |
|
2305 lemmas AND_upper1' [simp] = order_trans [OF AND_upper1] \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2306 lemmas AND_upper1'' [simp] = order_le_less_trans [OF AND_upper1] \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2307 |
|
2308 lemma AND_upper2 [simp]: \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2309 fixes x y :: int |
|
2310 assumes \<open>0 \<le> y\<close> |
|
2311 shows \<open>x AND y \<le> y\<close> |
|
2312 using assms AND_upper1 [of y x] by (simp add: ac_simps) |
|
2313 |
|
2314 lemmas AND_upper2' [simp] = order_trans [OF AND_upper2] \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2315 lemmas AND_upper2'' [simp] = order_le_less_trans [OF AND_upper2] \<^marker>\<open>contributor \<open>Stefan Berghofer\<close>\<close> |
|
2316 |
|
2317 lemma plus_and_or: \<open>(x AND y) + (x OR y) = x + y\<close> for x y :: int |
|
2318 proof (induction x arbitrary: y rule: int_bit_induct) |
|
2319 case zero |
|
2320 then show ?case |
|
2321 by simp |
|
2322 next |
|
2323 case minus |
|
2324 then show ?case |
|
2325 by simp |
|
2326 next |
|
2327 case (even x) |
|
2328 from even.IH [of \<open>y div 2\<close>] |
|
2329 show ?case |
|
2330 by (auto simp add: and_int_rec [of _ y] or_int_rec [of _ y] elim: oddE) |
|
2331 next |
|
2332 case (odd x) |
|
2333 from odd.IH [of \<open>y div 2\<close>] |
|
2334 show ?case |
|
2335 by (auto simp add: and_int_rec [of _ y] or_int_rec [of _ y] elim: oddE) |
|
2336 qed |
|
2337 |
|
2338 lemma set_bit_nonnegative_int_iff [simp]: |
|
2339 \<open>set_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
2340 by (simp add: set_bit_def) |
|
2341 |
|
2342 lemma set_bit_negative_int_iff [simp]: |
|
2343 \<open>set_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
2344 by (simp add: set_bit_def) |
|
2345 |
|
2346 lemma unset_bit_nonnegative_int_iff [simp]: |
|
2347 \<open>unset_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
2348 by (simp add: unset_bit_def) |
|
2349 |
|
2350 lemma unset_bit_negative_int_iff [simp]: |
|
2351 \<open>unset_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
2352 by (simp add: unset_bit_def) |
|
2353 |
|
2354 lemma flip_bit_nonnegative_int_iff [simp]: |
|
2355 \<open>flip_bit n k \<ge> 0 \<longleftrightarrow> k \<ge> 0\<close> for k :: int |
|
2356 by (simp add: flip_bit_def) |
|
2357 |
|
2358 lemma flip_bit_negative_int_iff [simp]: |
|
2359 \<open>flip_bit n k < 0 \<longleftrightarrow> k < 0\<close> for k :: int |
|
2360 by (simp add: flip_bit_def) |
|
2361 |
|
2362 lemma set_bit_greater_eq: |
|
2363 \<open>set_bit n k \<ge> k\<close> for k :: int |
|
2364 by (simp add: set_bit_def or_greater_eq) |
|
2365 |
|
2366 lemma unset_bit_less_eq: |
|
2367 \<open>unset_bit n k \<le> k\<close> for k :: int |
|
2368 by (simp add: unset_bit_def and_less_eq) |
|
2369 |
|
2370 lemma set_bit_eq: |
|
2371 \<open>set_bit n k = k + of_bool (\<not> bit k n) * 2 ^ n\<close> for k :: int |
|
2372 proof (rule bit_eqI) |
|
2373 fix m |
|
2374 show \<open>bit (set_bit n k) m \<longleftrightarrow> bit (k + of_bool (\<not> bit k n) * 2 ^ n) m\<close> |
|
2375 proof (cases \<open>m = n\<close>) |
|
2376 case True |
|
2377 then show ?thesis |
|
2378 apply (simp add: bit_set_bit_iff) |
|
2379 apply (simp add: bit_iff_odd div_plus_div_distrib_dvd_right) |
|
2380 done |
|
2381 next |
|
2382 case False |
|
2383 then show ?thesis |
|
2384 apply (clarsimp simp add: bit_set_bit_iff) |
|
2385 apply (subst disjunctive_add) |
|
2386 apply (clarsimp simp add: bit_exp_iff) |
|
2387 apply (clarsimp simp add: bit_or_iff bit_exp_iff) |
|
2388 done |
|
2389 qed |
|
2390 qed |
|
2391 |
|
2392 lemma unset_bit_eq: |
|
2393 \<open>unset_bit n k = k - of_bool (bit k n) * 2 ^ n\<close> for k :: int |
|
2394 proof (rule bit_eqI) |
|
2395 fix m |
|
2396 show \<open>bit (unset_bit n k) m \<longleftrightarrow> bit (k - of_bool (bit k n) * 2 ^ n) m\<close> |
|
2397 proof (cases \<open>m = n\<close>) |
|
2398 case True |
|
2399 then show ?thesis |
|
2400 apply (simp add: bit_unset_bit_iff) |
|
2401 apply (simp add: bit_iff_odd) |
|
2402 using div_plus_div_distrib_dvd_right [of \<open>2 ^ n\<close> \<open>- (2 ^ n)\<close> k] |
|
2403 apply (simp add: dvd_neg_div) |
|
2404 done |
|
2405 next |
|
2406 case False |
|
2407 then show ?thesis |
|
2408 apply (clarsimp simp add: bit_unset_bit_iff) |
|
2409 apply (subst disjunctive_diff) |
|
2410 apply (clarsimp simp add: bit_exp_iff) |
|
2411 apply (clarsimp simp add: bit_and_iff bit_not_iff bit_exp_iff) |
|
2412 done |
|
2413 qed |
|
2414 qed |
|
2415 |
|
2416 lemma take_bit_eq_mask_iff: |
|
2417 \<open>take_bit n k = mask n \<longleftrightarrow> take_bit n (k + 1) = 0\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
2418 for k :: int |
|
2419 proof |
|
2420 assume ?P |
|
2421 then have \<open>take_bit n (take_bit n k + take_bit n 1) = 0\<close> |
|
2422 by (simp add: mask_eq_exp_minus_1) |
|
2423 then show ?Q |
|
2424 by (simp only: take_bit_add) |
|
2425 next |
|
2426 assume ?Q |
|
2427 then have \<open>take_bit n (k + 1) - 1 = - 1\<close> |
|
2428 by simp |
|
2429 then have \<open>take_bit n (take_bit n (k + 1) - 1) = take_bit n (- 1)\<close> |
|
2430 by simp |
|
2431 moreover have \<open>take_bit n (take_bit n (k + 1) - 1) = take_bit n k\<close> |
|
2432 by (simp add: take_bit_eq_mod mod_simps) |
|
2433 ultimately show ?P |
|
2434 by (simp add: take_bit_minus_one_eq_mask) |
|
2435 qed |
|
2436 |
|
2437 lemma take_bit_eq_mask_iff_exp_dvd: |
|
2438 \<open>take_bit n k = mask n \<longleftrightarrow> 2 ^ n dvd k + 1\<close> |
|
2439 for k :: int |
|
2440 by (simp add: take_bit_eq_mask_iff flip: take_bit_eq_0_iff) |
|
2441 |
2866 |
2442 context ring_bit_operations |
2867 context ring_bit_operations |
2443 begin |
2868 begin |
2444 |
2869 |
2445 lemma even_of_int_iff: |
2870 lemma of_nat_mask_eq: |
2446 \<open>even (of_int k) \<longleftrightarrow> even k\<close> |
2871 \<open>of_nat (mask n) = mask n\<close> |
2447 by (induction k rule: int_bit_induct) simp_all |
2872 by (induction n) (simp_all add: mask_Suc_double Bit_Operations.mask_Suc_double of_nat_or_eq) |
2448 |
|
2449 lemma bit_of_int_iff [bit_simps]: |
|
2450 \<open>bit (of_int k) n \<longleftrightarrow> (2::'a) ^ n \<noteq> 0 \<and> bit k n\<close> |
|
2451 proof (cases \<open>(2::'a) ^ n = 0\<close>) |
|
2452 case True |
|
2453 then show ?thesis |
|
2454 by (simp add: exp_eq_0_imp_not_bit) |
|
2455 next |
|
2456 case False |
|
2457 then have \<open>bit (of_int k) n \<longleftrightarrow> bit k n\<close> |
|
2458 proof (induction k arbitrary: n rule: int_bit_induct) |
|
2459 case zero |
|
2460 then show ?case |
|
2461 by simp |
|
2462 next |
|
2463 case minus |
|
2464 then show ?case |
|
2465 by simp |
|
2466 next |
|
2467 case (even k) |
|
2468 then show ?case |
|
2469 using bit_double_iff [of \<open>of_int k\<close> n] Bit_Operations.bit_double_iff [of k n] |
|
2470 by (cases n) (auto simp add: ac_simps dest: mult_not_zero) |
|
2471 next |
|
2472 case (odd k) |
|
2473 then show ?case |
|
2474 using bit_double_iff [of \<open>of_int k\<close> n] |
|
2475 by (cases n) (auto simp add: ac_simps bit_double_iff even_bit_succ_iff Bit_Operations.bit_Suc dest: mult_not_zero) |
|
2476 qed |
|
2477 with False show ?thesis |
|
2478 by simp |
|
2479 qed |
|
2480 |
|
2481 lemma push_bit_of_int: |
|
2482 \<open>push_bit n (of_int k) = of_int (push_bit n k)\<close> |
|
2483 by (simp add: push_bit_eq_mult semiring_bit_shifts_class.push_bit_eq_mult) |
|
2484 |
|
2485 lemma of_int_push_bit: |
|
2486 \<open>of_int (push_bit n k) = push_bit n (of_int k)\<close> |
|
2487 by (simp add: push_bit_eq_mult semiring_bit_shifts_class.push_bit_eq_mult) |
|
2488 |
|
2489 lemma take_bit_of_int: |
|
2490 \<open>take_bit n (of_int k) = of_int (take_bit n k)\<close> |
|
2491 by (rule bit_eqI) (simp add: bit_take_bit_iff Bit_Operations.bit_take_bit_iff bit_of_int_iff) |
|
2492 |
|
2493 lemma of_int_take_bit: |
|
2494 \<open>of_int (take_bit n k) = take_bit n (of_int k)\<close> |
|
2495 by (rule bit_eqI) (simp add: bit_take_bit_iff Bit_Operations.bit_take_bit_iff bit_of_int_iff) |
|
2496 |
|
2497 lemma of_int_not_eq: |
|
2498 \<open>of_int (NOT k) = NOT (of_int k)\<close> |
|
2499 by (rule bit_eqI) (simp add: bit_not_iff Bit_Operations.bit_not_iff bit_of_int_iff) |
|
2500 |
|
2501 lemma of_int_and_eq: |
|
2502 \<open>of_int (k AND l) = of_int k AND of_int l\<close> |
|
2503 by (rule bit_eqI) (simp add: bit_of_int_iff bit_and_iff Bit_Operations.bit_and_iff) |
|
2504 |
|
2505 lemma of_int_or_eq: |
|
2506 \<open>of_int (k OR l) = of_int k OR of_int l\<close> |
|
2507 by (rule bit_eqI) (simp add: bit_of_int_iff bit_or_iff Bit_Operations.bit_or_iff) |
|
2508 |
|
2509 lemma of_int_xor_eq: |
|
2510 \<open>of_int (k XOR l) = of_int k XOR of_int l\<close> |
|
2511 by (rule bit_eqI) (simp add: bit_of_int_iff bit_xor_iff Bit_Operations.bit_xor_iff) |
|
2512 |
|
2513 lemma of_int_mask_eq: |
|
2514 \<open>of_int (mask n) = mask n\<close> |
|
2515 by (induction n) (simp_all add: mask_Suc_double Bit_Operations.mask_Suc_double of_int_or_eq) |
|
2516 |
2873 |
2517 end |
2874 end |
2518 |
2875 |
2519 lemma take_bit_incr_eq: |
2876 lemma Suc_mask_eq_exp: |
2520 \<open>take_bit n (k + 1) = 1 + take_bit n k\<close> if \<open>take_bit n k \<noteq> 2 ^ n - 1\<close> |
2877 \<open>Suc (mask n) = 2 ^ n\<close> |
2521 for k :: int |
2878 by (simp add: mask_eq_exp_minus_1) |
|
2879 |
|
2880 lemma less_eq_mask: |
|
2881 \<open>n \<le> mask n\<close> |
|
2882 by (simp add: mask_eq_exp_minus_1 le_diff_conv2) |
|
2883 (metis Suc_mask_eq_exp diff_Suc_1 diff_le_diff_pow diff_zero le_refl not_less_eq_eq power_0) |
|
2884 |
|
2885 lemma less_mask: |
|
2886 \<open>n < mask n\<close> if \<open>Suc 0 < n\<close> |
2522 proof - |
2887 proof - |
2523 from that have \<open>2 ^ n \<noteq> k mod 2 ^ n + 1\<close> |
2888 define m where \<open>m = n - 2\<close> |
2524 by (simp add: take_bit_eq_mod) |
2889 with that have *: \<open>n = m + 2\<close> |
2525 moreover have \<open>k mod 2 ^ n < 2 ^ n\<close> |
2890 by simp |
2526 by simp |
2891 have \<open>Suc (Suc (Suc m)) < 4 * 2 ^ m\<close> |
2527 ultimately have *: \<open>k mod 2 ^ n + 1 < 2 ^ n\<close> |
2892 by (induction m) simp_all |
2528 by linarith |
2893 then have \<open>Suc (m + 2) < Suc (mask (m + 2))\<close> |
2529 have \<open>(k + 1) mod 2 ^ n = (k mod 2 ^ n + 1) mod 2 ^ n\<close> |
2894 by (simp add: Suc_mask_eq_exp) |
2530 by (simp add: mod_simps) |
2895 then have \<open>m + 2 < mask (m + 2)\<close> |
2531 also have \<open>\<dots> = k mod 2 ^ n + 1\<close> |
2896 by (simp add: less_le) |
2532 using * by (simp add: zmod_trivial_iff) |
2897 with * show ?thesis |
2533 finally have \<open>(k + 1) mod 2 ^ n = k mod 2 ^ n + 1\<close> . |
2898 by simp |
2534 then show ?thesis |
2899 qed |
2535 by (simp add: take_bit_eq_mod) |
|
2536 qed |
|
2537 |
|
2538 lemma take_bit_decr_eq: |
|
2539 \<open>take_bit n (k - 1) = take_bit n k - 1\<close> if \<open>take_bit n k \<noteq> 0\<close> |
|
2540 for k :: int |
|
2541 proof - |
|
2542 from that have \<open>k mod 2 ^ n \<noteq> 0\<close> |
|
2543 by (simp add: take_bit_eq_mod) |
|
2544 moreover have \<open>k mod 2 ^ n \<ge> 0\<close> \<open>k mod 2 ^ n < 2 ^ n\<close> |
|
2545 by simp_all |
|
2546 ultimately have *: \<open>k mod 2 ^ n > 0\<close> |
|
2547 by linarith |
|
2548 have \<open>(k - 1) mod 2 ^ n = (k mod 2 ^ n - 1) mod 2 ^ n\<close> |
|
2549 by (simp add: mod_simps) |
|
2550 also have \<open>\<dots> = k mod 2 ^ n - 1\<close> |
|
2551 by (simp add: zmod_trivial_iff) |
|
2552 (use \<open>k mod 2 ^ n < 2 ^ n\<close> * in linarith) |
|
2553 finally have \<open>(k - 1) mod 2 ^ n = k mod 2 ^ n - 1\<close> . |
|
2554 then show ?thesis |
|
2555 by (simp add: take_bit_eq_mod) |
|
2556 qed |
|
2557 |
|
2558 lemma take_bit_int_greater_eq: |
|
2559 \<open>k + 2 ^ n \<le> take_bit n k\<close> if \<open>k < 0\<close> for k :: int |
|
2560 proof - |
|
2561 have \<open>k + 2 ^ n \<le> take_bit n (k + 2 ^ n)\<close> |
|
2562 proof (cases \<open>k > - (2 ^ n)\<close>) |
|
2563 case False |
|
2564 then have \<open>k + 2 ^ n \<le> 0\<close> |
|
2565 by simp |
|
2566 also note take_bit_nonnegative |
|
2567 finally show ?thesis . |
|
2568 next |
|
2569 case True |
|
2570 with that have \<open>0 \<le> k + 2 ^ n\<close> and \<open>k + 2 ^ n < 2 ^ n\<close> |
|
2571 by simp_all |
|
2572 then show ?thesis |
|
2573 by (simp only: take_bit_eq_mod mod_pos_pos_trivial) |
|
2574 qed |
|
2575 then show ?thesis |
|
2576 by (simp add: take_bit_eq_mod) |
|
2577 qed |
|
2578 |
|
2579 lemma take_bit_int_less_eq: |
|
2580 \<open>take_bit n k \<le> k - 2 ^ n\<close> if \<open>2 ^ n \<le> k\<close> and \<open>n > 0\<close> for k :: int |
|
2581 using that zmod_le_nonneg_dividend [of \<open>k - 2 ^ n\<close> \<open>2 ^ n\<close>] |
|
2582 by (simp add: take_bit_eq_mod) |
|
2583 |
|
2584 lemma take_bit_int_less_eq_self_iff: |
|
2585 \<open>take_bit n k \<le> k \<longleftrightarrow> 0 \<le> k\<close> (is \<open>?P \<longleftrightarrow> ?Q\<close>) |
|
2586 for k :: int |
|
2587 proof |
|
2588 assume ?P |
|
2589 show ?Q |
|
2590 proof (rule ccontr) |
|
2591 assume \<open>\<not> 0 \<le> k\<close> |
|
2592 then have \<open>k < 0\<close> |
|
2593 by simp |
|
2594 with \<open>?P\<close> |
|
2595 have \<open>take_bit n k < 0\<close> |
|
2596 by (rule le_less_trans) |
|
2597 then show False |
|
2598 by simp |
|
2599 qed |
|
2600 next |
|
2601 assume ?Q |
|
2602 then show ?P |
|
2603 by (simp add: take_bit_eq_mod zmod_le_nonneg_dividend) |
|
2604 qed |
|
2605 |
|
2606 lemma take_bit_int_less_self_iff: |
|
2607 \<open>take_bit n k < k \<longleftrightarrow> 2 ^ n \<le> k\<close> |
|
2608 for k :: int |
|
2609 by (auto simp add: less_le take_bit_int_less_eq_self_iff take_bit_int_eq_self_iff |
|
2610 intro: order_trans [of 0 \<open>2 ^ n\<close> k]) |
|
2611 |
|
2612 lemma take_bit_int_greater_self_iff: |
|
2613 \<open>k < take_bit n k \<longleftrightarrow> k < 0\<close> |
|
2614 for k :: int |
|
2615 using take_bit_int_less_eq_self_iff [of n k] by auto |
|
2616 |
|
2617 lemma take_bit_int_greater_eq_self_iff: |
|
2618 \<open>k \<le> take_bit n k \<longleftrightarrow> k < 2 ^ n\<close> |
|
2619 for k :: int |
|
2620 by (auto simp add: le_less take_bit_int_greater_self_iff take_bit_int_eq_self_iff |
|
2621 dest: sym not_sym intro: less_trans [of k 0 \<open>2 ^ n\<close>]) |
|
2622 |
|
2623 lemma minus_numeral_inc_eq: |
|
2624 \<open>- numeral (Num.inc n) = NOT (numeral n :: int)\<close> |
|
2625 by (simp add: not_int_def sub_inc_One_eq add_One) |
|
2626 |
|
2627 lemma sub_one_eq_not_neg: |
|
2628 \<open>Num.sub n num.One = NOT (- numeral n :: int)\<close> |
|
2629 by (simp add: not_int_def) |
|
2630 |
|
2631 lemma int_not_numerals [simp]: |
|
2632 \<open>NOT (numeral (Num.Bit0 n) :: int) = - numeral (Num.Bit1 n)\<close> |
|
2633 \<open>NOT (numeral (Num.Bit1 n) :: int) = - numeral (Num.inc (num.Bit1 n))\<close> |
|
2634 \<open>NOT (numeral (Num.BitM n) :: int) = - numeral (num.Bit0 n)\<close> |
|
2635 \<open>NOT (- numeral (Num.Bit0 n) :: int) = numeral (Num.BitM n)\<close> |
|
2636 \<open>NOT (- numeral (Num.Bit1 n) :: int) = numeral (Num.Bit0 n)\<close> |
|
2637 by (simp_all add: not_int_def add_One inc_BitM_eq) |
|
2638 |
|
2639 text \<open>FIXME: The rule sets below are very large (24 rules for each |
|
2640 operator). Is there a simpler way to do this?\<close> |
|
2641 |
|
2642 context |
|
2643 begin |
|
2644 |
|
2645 private lemma eqI: |
|
2646 \<open>k = l\<close> |
|
2647 if num: \<open>\<And>n. bit k (numeral n) \<longleftrightarrow> bit l (numeral n)\<close> |
|
2648 and even: \<open>even k \<longleftrightarrow> even l\<close> |
|
2649 for k l :: int |
|
2650 proof (rule bit_eqI) |
|
2651 fix n |
|
2652 show \<open>bit k n \<longleftrightarrow> bit l n\<close> |
|
2653 proof (cases n) |
|
2654 case 0 |
|
2655 with even show ?thesis |
|
2656 by simp |
|
2657 next |
|
2658 case (Suc n) |
|
2659 with num [of \<open>num_of_nat (Suc n)\<close>] show ?thesis |
|
2660 by (simp only: numeral_num_of_nat) |
|
2661 qed |
|
2662 qed |
|
2663 |
|
2664 lemma int_and_numerals [simp]: |
|
2665 \<open>numeral (Num.Bit0 x) AND numeral (Num.Bit0 y) = (2 :: int) * (numeral x AND numeral y)\<close> |
|
2666 \<open>numeral (Num.Bit0 x) AND numeral (Num.Bit1 y) = (2 :: int) * (numeral x AND numeral y)\<close> |
|
2667 \<open>numeral (Num.Bit1 x) AND numeral (Num.Bit0 y) = (2 :: int) * (numeral x AND numeral y)\<close> |
|
2668 \<open>numeral (Num.Bit1 x) AND numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x AND numeral y)\<close> |
|
2669 \<open>numeral (Num.Bit0 x) AND - numeral (Num.Bit0 y) = (2 :: int) * (numeral x AND - numeral y)\<close> |
|
2670 \<open>numeral (Num.Bit0 x) AND - numeral (Num.Bit1 y) = (2 :: int) * (numeral x AND - numeral (y + Num.One))\<close> |
|
2671 \<open>numeral (Num.Bit1 x) AND - numeral (Num.Bit0 y) = (2 :: int) * (numeral x AND - numeral y)\<close> |
|
2672 \<open>numeral (Num.Bit1 x) AND - numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x AND - numeral (y + Num.One))\<close> |
|
2673 \<open>- numeral (Num.Bit0 x) AND numeral (Num.Bit0 y) = (2 :: int) * (- numeral x AND numeral y)\<close> |
|
2674 \<open>- numeral (Num.Bit0 x) AND numeral (Num.Bit1 y) = (2 :: int) * (- numeral x AND numeral y)\<close> |
|
2675 \<open>- numeral (Num.Bit1 x) AND numeral (Num.Bit0 y) = (2 :: int) * (- numeral (x + Num.One) AND numeral y)\<close> |
|
2676 \<open>- numeral (Num.Bit1 x) AND numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral (x + Num.One) AND numeral y)\<close> |
|
2677 \<open>- numeral (Num.Bit0 x) AND - numeral (Num.Bit0 y) = (2 :: int) * (- numeral x AND - numeral y)\<close> |
|
2678 \<open>- numeral (Num.Bit0 x) AND - numeral (Num.Bit1 y) = (2 :: int) * (- numeral x AND - numeral (y + Num.One))\<close> |
|
2679 \<open>- numeral (Num.Bit1 x) AND - numeral (Num.Bit0 y) = (2 :: int) * (- numeral (x + Num.One) AND - numeral y)\<close> |
|
2680 \<open>- numeral (Num.Bit1 x) AND - numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral (x + Num.One) AND - numeral (y + Num.One))\<close> |
|
2681 \<open>(1::int) AND numeral (Num.Bit0 y) = 0\<close> |
|
2682 \<open>(1::int) AND numeral (Num.Bit1 y) = 1\<close> |
|
2683 \<open>(1::int) AND - numeral (Num.Bit0 y) = 0\<close> |
|
2684 \<open>(1::int) AND - numeral (Num.Bit1 y) = 1\<close> |
|
2685 \<open>numeral (Num.Bit0 x) AND (1::int) = 0\<close> |
|
2686 \<open>numeral (Num.Bit1 x) AND (1::int) = 1\<close> |
|
2687 \<open>- numeral (Num.Bit0 x) AND (1::int) = 0\<close> |
|
2688 \<open>- numeral (Num.Bit1 x) AND (1::int) = 1\<close> |
|
2689 by (auto simp add: bit_and_iff bit_minus_iff even_and_iff bit_double_iff even_bit_succ_iff add_One sub_inc_One_eq intro: eqI) |
|
2690 |
|
2691 lemma int_or_numerals [simp]: |
|
2692 \<open>numeral (Num.Bit0 x) OR numeral (Num.Bit0 y) = (2 :: int) * (numeral x OR numeral y)\<close> |
|
2693 \<open>numeral (Num.Bit0 x) OR numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x OR numeral y)\<close> |
|
2694 \<open>numeral (Num.Bit1 x) OR numeral (Num.Bit0 y) = 1 + (2 :: int) * (numeral x OR numeral y)\<close> |
|
2695 \<open>numeral (Num.Bit1 x) OR numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x OR numeral y)\<close> |
|
2696 \<open>numeral (Num.Bit0 x) OR - numeral (Num.Bit0 y) = (2 :: int) * (numeral x OR - numeral y)\<close> |
|
2697 \<open>numeral (Num.Bit0 x) OR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x OR - numeral (y + Num.One))\<close> |
|
2698 \<open>numeral (Num.Bit1 x) OR - numeral (Num.Bit0 y) = 1 + (2 :: int) * (numeral x OR - numeral y)\<close> |
|
2699 \<open>numeral (Num.Bit1 x) OR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x OR - numeral (y + Num.One))\<close> |
|
2700 \<open>- numeral (Num.Bit0 x) OR numeral (Num.Bit0 y) = (2 :: int) * (- numeral x OR numeral y)\<close> |
|
2701 \<open>- numeral (Num.Bit0 x) OR numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral x OR numeral y)\<close> |
|
2702 \<open>- numeral (Num.Bit1 x) OR numeral (Num.Bit0 y) = 1 + (2 :: int) * (- numeral (x + Num.One) OR numeral y)\<close> |
|
2703 \<open>- numeral (Num.Bit1 x) OR numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral (x + Num.One) OR numeral y)\<close> |
|
2704 \<open>- numeral (Num.Bit0 x) OR - numeral (Num.Bit0 y) = (2 :: int) * (- numeral x OR - numeral y)\<close> |
|
2705 \<open>- numeral (Num.Bit0 x) OR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral x OR - numeral (y + Num.One))\<close> |
|
2706 \<open>- numeral (Num.Bit1 x) OR - numeral (Num.Bit0 y) = 1 + (2 :: int) * (- numeral (x + Num.One) OR - numeral y)\<close> |
|
2707 \<open>- numeral (Num.Bit1 x) OR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral (x + Num.One) OR - numeral (y + Num.One))\<close> |
|
2708 \<open>(1::int) OR numeral (Num.Bit0 y) = numeral (Num.Bit1 y)\<close> |
|
2709 \<open>(1::int) OR numeral (Num.Bit1 y) = numeral (Num.Bit1 y)\<close> |
|
2710 \<open>(1::int) OR - numeral (Num.Bit0 y) = - numeral (Num.BitM y)\<close> |
|
2711 \<open>(1::int) OR - numeral (Num.Bit1 y) = - numeral (Num.Bit1 y)\<close> |
|
2712 \<open>numeral (Num.Bit0 x) OR (1::int) = numeral (Num.Bit1 x)\<close> |
|
2713 \<open>numeral (Num.Bit1 x) OR (1::int) = numeral (Num.Bit1 x)\<close> |
|
2714 \<open>- numeral (Num.Bit0 x) OR (1::int) = - numeral (Num.BitM x)\<close> |
|
2715 \<open>- numeral (Num.Bit1 x) OR (1::int) = - numeral (Num.Bit1 x)\<close> |
|
2716 by (auto simp add: bit_or_iff bit_minus_iff even_or_iff bit_double_iff even_bit_succ_iff add_One sub_inc_One_eq sub_BitM_One_eq intro: eqI) |
|
2717 |
|
2718 lemma int_xor_numerals [simp]: |
|
2719 \<open>numeral (Num.Bit0 x) XOR numeral (Num.Bit0 y) = (2 :: int) * (numeral x XOR numeral y)\<close> |
|
2720 \<open>numeral (Num.Bit0 x) XOR numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x XOR numeral y)\<close> |
|
2721 \<open>numeral (Num.Bit1 x) XOR numeral (Num.Bit0 y) = 1 + (2 :: int) * (numeral x XOR numeral y)\<close> |
|
2722 \<open>numeral (Num.Bit1 x) XOR numeral (Num.Bit1 y) = (2 :: int) * (numeral x XOR numeral y)\<close> |
|
2723 \<open>numeral (Num.Bit0 x) XOR - numeral (Num.Bit0 y) = (2 :: int) * (numeral x XOR - numeral y)\<close> |
|
2724 \<open>numeral (Num.Bit0 x) XOR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (numeral x XOR - numeral (y + Num.One))\<close> |
|
2725 \<open>numeral (Num.Bit1 x) XOR - numeral (Num.Bit0 y) = 1 + (2 :: int) * (numeral x XOR - numeral y)\<close> |
|
2726 \<open>numeral (Num.Bit1 x) XOR - numeral (Num.Bit1 y) = (2 :: int) * (numeral x XOR - numeral (y + Num.One))\<close> |
|
2727 \<open>- numeral (Num.Bit0 x) XOR numeral (Num.Bit0 y) = (2 :: int) * (- numeral x XOR numeral y)\<close> |
|
2728 \<open>- numeral (Num.Bit0 x) XOR numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral x XOR numeral y)\<close> |
|
2729 \<open>- numeral (Num.Bit1 x) XOR numeral (Num.Bit0 y) = 1 + (2 :: int) * (- numeral (x + Num.One) XOR numeral y)\<close> |
|
2730 \<open>- numeral (Num.Bit1 x) XOR numeral (Num.Bit1 y) = (2 :: int) * (- numeral (x + Num.One) XOR numeral y)\<close> |
|
2731 \<open>- numeral (Num.Bit0 x) XOR - numeral (Num.Bit0 y) = (2 :: int) * (- numeral x XOR - numeral y)\<close> |
|
2732 \<open>- numeral (Num.Bit0 x) XOR - numeral (Num.Bit1 y) = 1 + (2 :: int) * (- numeral x XOR - numeral (y + Num.One))\<close> |
|
2733 \<open>- numeral (Num.Bit1 x) XOR - numeral (Num.Bit0 y) = 1 + (2 :: int) * (- numeral (x + Num.One) XOR - numeral y)\<close> |
|
2734 \<open>- numeral (Num.Bit1 x) XOR - numeral (Num.Bit1 y) = (2 :: int) * (- numeral (x + Num.One) XOR - numeral (y + Num.One))\<close> |
|
2735 \<open>(1::int) XOR numeral (Num.Bit0 y) = numeral (Num.Bit1 y)\<close> |
|
2736 \<open>(1::int) XOR numeral (Num.Bit1 y) = numeral (Num.Bit0 y)\<close> |
|
2737 \<open>(1::int) XOR - numeral (Num.Bit0 y) = - numeral (Num.BitM y)\<close> |
|
2738 \<open>(1::int) XOR - numeral (Num.Bit1 y) = - numeral (Num.Bit0 (y + Num.One))\<close> |
|
2739 \<open>numeral (Num.Bit0 x) XOR (1::int) = numeral (Num.Bit1 x)\<close> |
|
2740 \<open>numeral (Num.Bit1 x) XOR (1::int) = numeral (Num.Bit0 x)\<close> |
|
2741 \<open>- numeral (Num.Bit0 x) XOR (1::int) = - numeral (Num.BitM x)\<close> |
|
2742 \<open>- numeral (Num.Bit1 x) XOR (1::int) = - numeral (Num.Bit0 (x + Num.One))\<close> |
|
2743 by (auto simp add: bit_xor_iff bit_minus_iff even_xor_iff bit_double_iff even_bit_succ_iff add_One sub_inc_One_eq sub_BitM_One_eq intro: eqI) |
|
2744 |
|
2745 end |
|
2746 |
2900 |
2747 |
2901 |
2748 subsection \<open>Bit concatenation\<close> |
2902 subsection \<open>Bit concatenation\<close> |
2749 |
2903 |
2750 definition concat_bit :: \<open>nat \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int\<close> |
2904 definition concat_bit :: \<open>nat \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int\<close> |