一道笔试题的思考(二)

题目：给定一数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法： 要求O（1）空间复杂度和O（n）的时间复杂度； 除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）； 请用程序（主流编程语言任选）实现并简单描述。在考试的时候我是没想出来，回来查了一下资料，自己实现了一下，原来就是一个想法，把这个数组的前半部分乘积保存在b，即b[i]=a[0]*a[1]*...a[i]，后半部分乘积保存a，a[i]=a[i]*a[i+1]*.....a[n-1],然后求最终数组时，把b[i]=b[i-1]*a[i+1];明白这个思想，代码就比较好写了，注意一下边界就行了：

	public static void main(String[] args) {  
		int[] a = {3,4,2,5,7,6,1};
		int[] b = {1,1,1,1,1,1,1};
		//b是前半截数组
		for(int i=0;i<a.length;i++){
			if(i!=0)b[i]=b[i-1];
			b[i]*=a[i];
		}
		//a是后半截数组
		for(int i=a.length-1;i>=0;i--){
			if(i==a.length-1)a[i]=a[i];
			else
				a[i]*=a[i+1];
		}
		//前半截×后半截=最终的数组
		for(int i=0;i<a.length;i++){
			if(i==0)a[i]=a[i+1];
			else if(i==a.length-1) 
					a[i]=b[a.length-2];
			else
				a[i]=b[i-1]*a[i+1];
		}
		print(a);//输出1680 1260 2520 1008 720 840 5040
		
    }  

考完这个题目后我一直在想的一个问题不是这个题目怎么做，而是让我联想到除法比乘法慢的问题，移位操作是所有操作中最慢的，很容易理解，计算机是以0和1表示数据的，移位操作花费的时钟周期是最短的。引用的第二篇文章讲的很好，可以一看。文章中提醒了我一点：i=2<<3的字节码会是什么？以前以为会是先把２放入栈顶，然后再移位什么的，但是错了，编译乘字节码之后是：bipush 16。也就是说在编译期间就已经把2<<3算出来了。因此i=2<<3和i=2×8的效率在执行期间是一样的，如果是下面的代码：

int i = 2;

int j = i * 8;

编译后字节码是：

但是如果是下面的代码：

int i = 2;

int j = i <<3;

编译后：

这也是我们知道的，常量计算会在编译器就算出来，即不管是i=2<<3还是i=2*8,右边的常量都是在编译期间已经算出来，但是如果是j=i*8和j=i<<3这种情况，j=i<<3可能会更快一点，毕竟是位运算，至于快多少，我不确定。下面是文中给出的各指令所需的时钟周期：

这样看来除法比乘法也慢不了多少.....纠结～

参考：

http://lotusroots.bokee.com/5886635.html

拾谈“用最有效率的方法算出2乘以8等於几?：http://blog.csdn.net/kypfos/article/details/810151