整数与二进制
提要：理解与掌握二进制数在计算机的运算方面的应用
文章目录
一、简单乘法
1.递归版
代码如下（示例）：
摘自王立斌老师《具体数论与代数》
2.迭代版
代码如下（示例）：
#include<stdio.h>
int naive_multiply(int a,int b);
void main()
{
printf("输入要计算的整数a和b\n");
int a,b;
scanf("%d",&a);
scanf("%d",&b);
printf("a*b=");
printf("%d",naive_multiply(a,b));
}
int naive_multiply(int a,int b)
{
int result=0,k=1;
while(b!=0)
{
if(b%2==0) ;
else result+=a*k;
b=b/2;
k=k*2;
}
return result;
}
二、证明命题1.1
定理： 2 0 2^{0} 20+ 2 1 2^{1} 21+……+ 2 n 2^{n} 2n= 2 n + 1 − 1 2^{n+1}-1 2n+1−1
证明：
显然这是一个首项为1，公比为2的等比数列求和问题
根据公式有
S n S_{n} Sn= n a 1 a_{1} a1 (q=1)
S n S_{n} Sn= a ₁ ( 1 − q ⁿ ) 1 − q \frac{a₁(1-qⁿ)}{1-q} 1−qa₁(1−qⁿ) (q ≠ \neq = 1)
带入数据得 S n S_{n} Sn= 2 n + 1 2^{n+1} 2n+1-1
故命题1.1的相关二进制算法得证。
三、除法算法的证明
充分性：
构造集合
S={a-bk; k ∈ \in ∈Z 且 a-bk ≥ \geq ≥ 0};
显然，集合S非空。由良序原则，存在一个最小元 r ∈ \in ∈ S，且 r = a - qb
因此，a = qb + r，r ≥ \geq ≥ 0
显然，集合中必定存在一个 k 1 k_{1} k1，使得 r = a-b k 1 ≥ k_{1}\geq k1≥ 0，且 a - b( k 1 k_{1} k1+1) <0
则有 a - b k 1 k_{1} k1 < b
即 r < b
综上所述，0 ≤ \leq ≤ r < b
必要性：
假设 q 和 r 不唯一，则有 a = q 1 q_{1} q1b + r 1 r_{1} r1和 a = q 2 q_{2} q2b + r 2 r_{2} r2 (0 ≤ \leq ≤ r 1 r_{1} r1 < b，0 ≤ \leq ≤ r 2 r_{2} r2 < b)
两式相减得， r 2 r_{2} r2 - r 1 r_{1} r1 = b ( q 1 q_{1} q1 - q 2 q_{2} q2)
∵ \because ∵ q != 0
∴ \therefore ∴ b能整除 r 2 r_{2} r2 - r 1 r_{1} r1
又 ∵ \because ∵ 0 ≤ \leq ≤ r 1 r_{1} r1 < b，0 ≤ \leq ≤ r 2 r_{2} r2 < b
∴ \therefore ∴ -b < r 2 r_{2} r2 - r 1 r_{1} r1 < b
∴ \therefore ∴ r 2 r_{2} r2 - r 1 r_{1} r1 = 0
即 r 2 r_{2} r2 = r 1 r_{1} r1
则由题设 a = q 1 q_{1} q1b + r 1 r_{1} r1 = q 2 q_{2} q2b + r 2 r_{2} r2 可得， q 1 q_{1} q1 = q 2 q_{2} q2
因此原命题不成立
则可认为 q 和 r 是唯一的
综合以上两点，则可证明“除法算法”成立