例如:
1/7 => 146/1023
47/100 => 480/1023
223/230 => 991/1023
234/567 => 422/1023
- 不能使用浮点算术和除法
二进制搜索解决了我的问题,但不够快......
int binary_search(int min_y, int max_y, int min_x, int max_x, int x){
int y = max_y -= min_y;
int current_x = max_x -= min_x;
while(x != current_x){
current_x = current_x >> 1;
y = y >> 1;
if(x > current_x){
x -= current_x;
min_y += y;
}
}
return min_y;
}
这个问题已经困扰了我好几个星期了。我需要帮助!
3条答案
按热度按时间vsnjm48y1#
产出:
6bc51xsx2#
如果你想在不使用任何除法或浮点运算的情况下缩放一个分数使其分母为1024,你应该使用交叉乘法和二进制移位。您可以像这样计算分母的newNumerator; newNumerator = oldNumerator * 1024/oldDenominator。
因为你不能使用除法(/),你可以使用二进制,一个二进制向右移位来除以2的幂。
1024是2的10次幂,因此可以使用如下移位来除它:newNumerator =(oldNumerator <<10)/oldDenominator
同样,你不允许使用除法(/),所以你可以使用按位算法进行整数除法。
C/C ++ Bitwise Operators in C/C++中的左移和右移运算符
dohp0rv53#
**如果新分母在[1...1023]**这样的范围内,请使用查找表。
我相信它会足够快。