一道考察模拟乘法的题目

今天hl和我讨论一道题目：

写道

整形数组如a={1,4,5}代表二进制数字1出现的位置（下标从右边开 始，0为第一个），即110010，也即十进制 x=2^1+2^4+2^5=50. 求 3*x=150的二进制表示里边，1的个数。如本题输出4.输入为整形数组如 a。
注意算法性能的优化。

 我感觉这道题目考察的就是模拟乘法，相对于acm常做的大数乘法的模拟算法要简单一些：

int three_x(int a[],int n){
	int bin_len = a[n-1] + 1;
	int res_len = a[n-1] + 3;
	int *bin_a = (int *)malloc( sizeof(int) * bin_len ) ;
	int *res = (int *)malloc( sizeof(int) * res_len );
	memeset(res,0,sizeof(int) * res_len);

	int i,j=0;
	for(i = 0; i <= a[n-1]; i++){//初始化二进制数组
		if(i == a[j]){
                        bin_a[i] = 1;
                        j++
		}else	
			bin_a[i] = 0;
	}
	
	for(int i = 0; i < bin_len; i++){//二进制数组和3做乘法
		res[i] += bin_a[i] * 3 % 2;
		res[i+1] += bin_a[i] / 2; 	     
	} 
	res[res_len-1] += res[res_len-2] / 2;//处理一下高位：
	res[res_len-2] += res[res_len-2] % 2; 

	int num = 0;
	for(i = 0; i < res_len; i++){//求1的个数
		if(res[i] == 1)
			num++;
	}

	return num;
}

 不知道有什么更高级的接法。

评论

2 楼 fuliang 2009-11-18  

flying_bird84 写道

//连长看看我的代码

int three_x(int *a,int len){
int data=0,count=0;
for (int i=0;i<len;i++)
data += 1<<a[i];
data *= 3;
cout<<data<<endl;
while(data){
data &= (data-1);
count ++;
}
return count;
}

你的这个是把数转化成整数，然后做乘法，最后求得到的数1的个数。对数大小有限制。

1 楼 flying_bird84 2009-11-17  

//连长看看我的代码

int three_x(int *a,int len){
int data=0,count=0;
for (int i=0;i<len;i++)
data += 1<<a[i];
data *= 3;
cout<<data<<endl;
while(data){
data &= (data-1);
count ++;
}
return count;
}