a****l
发帖数: 8211 | 1 算法的原理很简单,输入x,输出y.x的范围(0-1000)的整数,y的范围是(0-1500)的整数,
将x线性的按比例关系转换成y,也就是y=1.5x,小数点后的舍入方法随便(就是说y=2.5的
话算2或者3都可以)
现在的关键是,x是一个16位的整数(unsigned int, 16bits),y也是一个16位的整数,要
求是计算过程中不能用到32位的运算,就是说不能把x,y转换成32位算好再转换回来,这
该怎么计算?有谁知道这个怎么办吗?显然,查表的方法也是不允许的(内存的占用必须是
固定的,不能随范围变化而变化)
另外的一个要求是,y的范围是可以变的,所以不能用固定的乘1.5的算法,y应该可以是任
何一个16位整数可表达的范围. | w*******d
发帖数: 3714 | | p*****n
发帖数: 368 | 3 别忘了运算顺序
【在 w*******d 的大作中提到】
: y = x + x>>1 ?
| p***e
发帖数: 472 | 4
将x线性的按比例关系转换成y,也就是y=1.5x,小数点后的舍入方法随便(就是说y=2.5的
话算2或者3都可以)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
要求是计算过程中不能用到32位的运算,就是说不能把x,y转换成32位算好再转换回来,
这该怎么计算?有谁知道这个怎么办吗?显然,查表的方法也是不允许的(内存的占用必须
是固定的,不能随范围变化而变化)
另外的一个要求是,y的范围是可以变的,所以不能用固定的乘1.5的算法,y应该可以是任
何一个16位整数可表达的范围.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
What do you mean? Are those two statements each other in controversy?
【在 a****l 的大作中提到】
: 算法的原理很简单,输入x,输出y.x的范围(0-1000)的整数,y的范围是(0-1500)的整数,
: 将x线性的按比例关系转换成y,也就是y=1.5x,小数点后的舍入方法随便(就是说y=2.5的
: 话算2或者3都可以)
: 现在的关键是,x是一个16位的整数(unsigned int, 16bits),y也是一个16位的整数,要
: 求是计算过程中不能用到32位的运算,就是说不能把x,y转换成32位算好再转换回来,这
: 该怎么计算?有谁知道这个怎么办吗?显然,查表的方法也是不允许的(内存的占用必须是
: 固定的,不能随范围变化而变化)
: 另外的一个要求是,y的范围是可以变的,所以不能用固定的乘1.5的算法,y应该可以是任
: 何一个16位整数可表达的范围.
| l*****x
发帖数: 3431 | 5 问题看起来是用16位存储器实现Y=k*X，k是常数。
把k展开为最接近的二进制数列，然后用willywufd提供的移位累加方法，大数加小数，
如果结果出现msb 1->0，则溢出报错。
请拍砖
【在 a****l 的大作中提到】
: 算法的原理很简单,输入x,输出y.x的范围(0-1000)的整数,y的范围是(0-1500)的整数,
: 将x线性的按比例关系转换成y,也就是y=1.5x,小数点后的舍入方法随便(就是说y=2.5的
: 话算2或者3都可以)
: 现在的关键是,x是一个16位的整数(unsigned int, 16bits),y也是一个16位的整数,要
: 求是计算过程中不能用到32位的运算,就是说不能把x,y转换成32位算好再转换回来,这
: 该怎么计算?有谁知道这个怎么办吗?显然,查表的方法也是不允许的(内存的占用必须是
: 固定的,不能随范围变化而变化)
: 另外的一个要求是,y的范围是可以变的,所以不能用固定的乘1.5的算法,y应该可以是任
: 何一个16位整数可表达的范围.
| z*****n
发帖数: 7639 | 6 y = (x + x<<1)>>1;
【在 a****l 的大作中提到】
: 算法的原理很简单,输入x,输出y.x的范围(0-1000)的整数,y的范围是(0-1500)的整数,
: 将x线性的按比例关系转换成y,也就是y=1.5x,小数点后的舍入方法随便(就是说y=2.5的
: 话算2或者3都可以)
: 现在的关键是,x是一个16位的整数(unsigned int, 16bits),y也是一个16位的整数,要
: 求是计算过程中不能用到32位的运算,就是说不能把x,y转换成32位算好再转换回来,这
: 该怎么计算?有谁知道这个怎么办吗?显然,查表的方法也是不允许的(内存的占用必须是
: 固定的,不能随范围变化而变化)
: 另外的一个要求是,y的范围是可以变的,所以不能用固定的乘1.5的算法,y应该可以是任
: 何一个16位整数可表达的范围.
| p*f
发帖数: 982 | 7 如果我理解得不错的话,应该是:
y=(65535)/[max y- min y]*x.如果你的范围变化不是很频繁的话，查表是可以的，因为
表的大小取决于x的范围，而不是y的范围。 | p*f
发帖数: 982 | 8 还有个办法是：用一个除法器，计算前面的那个系数（得到16位结果），然后用一个16
位乘16位的乘法器，只取结果的高16位。 | u****u
发帖数: 229 | 9 很抱歉,你似乎没有理解原始问题的难点在于哪里.你说的根本就是最原始的做法,能用
这个方法就根本不用问这个问题了.
16
【在 p*f 的大作中提到】
: 还有个办法是：用一个除法器，计算前面的那个系数（得到16位结果），然后用一个16
: 位乘16位的乘法器，只取结果的高16位。
| z*****n
发帖数: 7639 | 10 前面不是有人给出了solution吗？
y = x + (x>>1); 或者 y=(x+x<<1)>>1;
就可以解决问题啊。
我写了个程序输入了10个数验证了下：
32 48
51 76
51 76
92 138
54 81
90 135
13 19
69 103
20 30
6 9
【在 u****u 的大作中提到】
: 很抱歉,你似乎没有理解原始问题的难点在于哪里.你说的根本就是最原始的做法,能用
: 这个方法就根本不用问这个问题了.
:
: 16
| p*f
发帖数: 982 | 11
你们注意到这句话没有:
另外的一个要求是,y的范围是可以变的,所以不能用固定的乘1.5的算法,
你们所用得solution都是固定乘1.5。
【在 z*****n 的大作中提到】
: 前面不是有人给出了solution吗？
: y = x + (x>>1); 或者 y=(x+x<<1)>>1;
: 就可以解决问题啊。
: 我写了个程序输入了10个数验证了下：
: 32 48
: 51 76
: 51 76
: 92 138
: 54 81
: 90 135
| z*****n
发帖数: 7639 | 12 啥叫y的范围是可变的？楼主说了x的范围是在1500以内，
y的范围也在一个integer的最大值以内。
【在 p*f 的大作中提到】
:
: 你们注意到这句话没有:
: 另外的一个要求是,y的范围是可以变的,所以不能用固定的乘1.5的算法,
: 你们所用得solution都是固定乘1.5。
| a****l
发帖数: 8211 | 13 y的范围可变的意思就是说y可能是(0-1500)或者说(0-2512)或者说(0-3507),反正都是
在16位的范围内的数.所以不是固定的乘1.5的算法.不过这个问题已经解决了,就是把1.
5的算法扩展一下用两步就算出来的.计算的速度是原始算法的4倍.
【在 z*****n 的大作中提到】
: 啥叫y的范围是可变的？楼主说了x的范围是在1500以内，
: y的范围也在一个integer的最大值以内。
|
|
