在GF(2^8)下可做任意两个数乘法的程序（一）(二)
调错误状态到主函数并询问是否重新输入的循环形式。
在讲解执行a * b之前，先看看xor运算：
[cpp]
/* 对a和b进行异或求和运算 */
void xor(int a[], int b[])
{
for(int i=0; i<8; i++)
{
a[i]=bitxor(a[i], b[i]);
}
}
/* 按位进行异或求和运算 */
int bitxor(int a, int b)
{
if(a==b)
{
return 0;
}
else
{
return 1;
}
}
xor()是对一个字节的a[8]和b[8]进行xor求和，结果保存到a[8]中。
bitxor()是逐位相与。
再看看求和语句：
[cpp]
// -- 执行乘法运算 --
for(i=7; i>=0; i--)
{
if(b[i]==1)
{
xor(c, leftshift(a, 7-i)); // 求和
}
}
看看关键的leftshift函数：
[cpp]
/*
* 计算a[]乘上2的len次幂的结果, len为左移的位数
* 参数temp[]用于保存移位后的数组，用于迭代进行下一次移位
* 参数len为左移的位数，例如10000000的左移位数为7
* state用于保存temp对应的左移位数
* 返回结果为移位后的数组
*/
int *leftshift(int temp[], int len)
{
if(len==0)
{
state=0;
return temp;
}
// 由于temp保存了之前的位移结果，所以只需要左移len-state位
for(state; state
{
shift1(temp); // 乘2，或者说左移1位（包含溢出处理）
}
return temp;
}
为了说明该算法的思想，首先举个例子：对于a * 00001100 = (a * 00001000) xor (a * 00000100)，这时有两种计算方法（假设一次乘法或一次加法为1次计算）：
（1）计算a * 00000100得结果a left shift 2，再计算a * 00001000得结果a leftshift 3，然后得a = (a left shift 2) xor (a left shift 3)。
计算次数为 2 + 3 + 1 + 溢出的加法次数x = 6 + x。
（2）在（1）的基础上，注意到a left shift 3 = (a left shift 2) * 2，所以我们可以先计算a left shift 2，然后使用a left shift 2的结果乘2（只需要1次乘法）得到结果a left shift 3，这样就避免了在计算a left shift 3时又要从a计算起。
计算次数为 2 + 1 + 1 + 溢出的加法次数y = 4 + y。
明显地，y <= x，也就是方法（2）的运算效率高于方法（1）。
在本程序中，对于a[8] * b[8]，我们从b[7]计算到b[0]，也就是a[8] * 2的次数从0一直计算到7，其中每次乘法都运用了之前乘法运算保存的结果，该结果由temp数组保存，state则保存了temp数组对应的移位次数，len为本次乘法原来需要乘2的次数（这里乘2和左移是一致的，在讲述时忽略溢出的处理情况）。其中state为全局静态变量，初始为0：
[cpp]
static state=0; // 用于记录左移的位数
还有左移1位（乘2）的函数shift1：
[cpp]
/* 乘2，左移1位，如果溢出则异或1BH */
void shift1(int a[])
{
int temp=a[0];
for(int i=0; i<7; i++)
{
a[i]=a[i+1];
}
a[7]=0;
if(temp==1) // 溢出处理
{
int mod[8]={0, 0, 0, 1, 1, 0, 1, 1};
xor(a, mod);
}
}
最后输出c，即运算结果，以及计算所用时间（由于要与后面博客中的查表乘法运算的效率相比较）。
还是Run一下吧，写博客的习惯：
好久没写C++，小小回顾一下：
1.若要在主函数中调用其它函数，必须将该函数放在主函数之前，或者提前做好函数声明，例如：
[cpp]
#include
#include // numeric_limits
#include
using namespace std;
int input(int temp[], char name);
void xor(int a[], int b[]);
int bitxor(int a, int b);
int *leftshift(int temp[], int len);
void shift1(int a[]);
2.判断输入是否按了回车换行，可以通过以下方法：
[cpp]
c=cin.get();
while(c!=10)
{
}
其中10（0AH）对应的ACII码为换行。
其中语句cin.get()对应一次输入，而不是上一次的输入。
3.如果要强制退出程序，可以直接使用exit(1)退出，而不需要回调数据到main函数再return。
4.调用函数时数组可以直接作为参数传值：int(a[], b[])。
5.当函数的返回类型是数组时，可以首先在函数中声明一个数组指针：
[cpp]
int *shift=new int[8];
在写程序时没有声明长度，结果一直弹出Debug Assertion Failed!的错误。
在函数结束时返回该指针：
[cpp]
return shift;
注意shift必须new，否则返回的指针所指向的数组可能其值全部为负最大值。
函数声明：
[cpp]
int *leftshift(int a[], int len);
6.如果要清空输入缓冲区中的内容，可以使用以下方法：
[cpp]
cin.ignore(numeric_limits::max(),'\n'); // 清除输入缓冲区中的所有内容
注意必须导入头文件
[cpp]
#include // numeric_limits
关于limits的max()和windows.h冲突的解决方法见numeric_limits::max()和windows.h冲突的解决方法。
7.计算程序运行时间的方法：
（1）使用time.h给出的函数
首先导入头文件：