C语言 如何将任何分数的分母转换为1023而不使用除法,然后分数保持原来的比例

b91juud3  于 2023-06-21  发布在  其他
关注(0)|答案(3)|浏览(121)

例如:
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;
}

这个问题已经困扰了我好几个星期了。我需要帮助!

vsnjm48y

vsnjm48y1#

#include <stdio.h>

struct Fraction {
    int numerator;
    int denominator;
};

void print(Fraction f) {
    printf("%d / %d\n", f.numerator, f.denominator);
}

Fraction convert_frac_to_1024_denominator(Fraction fraction) {

    // scale up by x 1024
    Fraction mult_by_1024 = {
        fraction.numerator << 10,
        1 << 10
    };

    // divide through by original denominator
    int quotient = 0, remainder = 0;
    for(int i = 31 ; i >= 0 ; i--)
    {
        quotient <<= 1;
        remainder <<= 1;
        remainder |= (mult_by_1024.numerator & (1 << i)) >> i;

        if(remainder >= fraction.denominator)
        {
            remainder = (remainder - fraction.denominator);
            quotient |= 1;
        }
    }
    mult_by_1024.numerator = quotient;
    return mult_by_1024;
}

int main() {

    Fraction _1_7 = { 1, 7 };
    print(convert_frac_to_1024_denominator(_1_7));

    Fraction _47_100 = { 47, 100 };
    print(convert_frac_to_1024_denominator(_47_100));

    Fraction _223_230 = { 223, 230 };
    print(convert_frac_to_1024_denominator(_223_230));
    
    Fraction _234_567 = { 234, 567 };
    print(convert_frac_to_1024_denominator(_234_567));

    return 0;
}

产出:

146 / 1024
481 / 1024
992 / 1024
422 / 1024
6bc51xsx

6bc51xsx2#

如果你想在不使用任何除法或浮点运算的情况下缩放一个分数使其分母为1024,你应该使用交叉乘法和二进制移位。您可以像这样计算分母的newNumerator; newNumerator = oldNumerator * 1024/oldDenominator。
因为你不能使用除法(/),你可以使用二进制,一个二进制向右移位来除以2的幂。
1024是2的10次幂,因此可以使用如下移位来除它:newNumerator =(oldNumerator <<10)/oldDenominator
同样,你不允许使用除法(/),所以你可以使用按位算法进行整数除法。
C/C ++ Bitwise Operators in C/C++中的左移和右移运算符

dohp0rv5

dohp0rv53#

**如果新分母在[1...1023]**这样的范围内,请使用查找表。

我相信它会足够快。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

static unsigned t[1023 + 1] = { 0,
0, 2147483648, 1431655765, 1073741824, 858993459, 715827882, 613566756, 536870912, 477218588, 429496729, 390451572, 357913941, 330382099, 306783378, 286331153, 268435456, 252645135, 238609294, 226050910, 214748364, 204522252, 195225786, 186737708, 178956970, 171798691, 165191049, 159072862, 153391689, 148102320, 143165576, 138547332, 134217728,
130150524, 126322567, 122713351, 119304647, 116080197, 113025455, 110127366, 107374182, 104755299, 102261126, 99882960, 97612893, 95443717, 93368854, 91382282, 89478485, 87652393, 85899345, 84215045, 82595524, 81037118, 79536431, 78090314, 76695844, 75350303, 74051160, 72796055, 71582788, 70409299, 69273666, 68174084, 67108864,
66076419, 65075262, 64103989, 63161283, 62245902, 61356675, 60492497, 59652323, 58835168, 58040098, 57266230, 56512727, 55778796, 55063683, 54366674, 53687091, 53024287, 52377649, 51746593, 51130563, 50529027, 49941480, 49367440, 48806446, 48258059, 47721858, 47197442, 46684427, 46182444, 45691141, 45210182, 44739242,
44278013, 43826196, 43383508, 42949672, 42524428, 42107522, 41698711, 41297762, 40904450, 40518559, 40139881, 39768215, 39403369, 39045157, 38693399, 38347922, 38008560, 37675151, 37347541, 37025580, 36709122, 36398027, 36092162, 35791394, 35495597, 35204649, 34918433, 34636833, 34359738, 34087042, 33818640, 33554432,
33294320, 33038209, 32786009, 32537631, 32292987, 32051994, 31814572, 31580641, 31350126, 31122951, 30899045, 30678337, 30460760, 30246248, 30034736, 29826161, 29620464, 29417584, 29217464, 29020049, 28825283, 28633115, 28443492, 28256363, 28071681, 27889398, 27709466, 27531841, 27356479, 27183337, 27012372, 26843545,
26676815, 26512143, 26349492, 26188824, 26030104, 25873296, 25718367, 25565281, 25414007, 25264513, 25116767, 24970740, 24826400, 24683720, 24542670, 24403223, 24265351, 24129029, 23994230, 23860929, 23729101, 23598721, 23469766, 23342213, 23216039, 23091222, 22967739, 22845570, 22724694, 22605091, 22486739, 22369621,
22253716, 22139006, 22025473, 21913098, 21801864, 21691754, 21582750, 21474836, 21367996, 21262214, 21157474, 21053761, 20951059, 20849355, 20748634, 20648881, 20550082, 20452225, 20355295, 20259279, 20164165, 20069940, 19976592, 19884107, 19792476, 19701684, 19611722, 19522578, 19434241, 19346699, 19259943, 19173961,
19088743, 19004280, 18920560, 18837575, 18755315, 18673770, 18592932, 18512790, 18433336, 18354561, 18276456, 18199013, 18122224, 18046081, 17970574, 17895697, 17821441, 17747798, 17674762, 17602324, 17530478, 17459216, 17388531, 17318416, 17248864, 17179869, 17111423, 17043521, 16976155, 16909320, 16843009, 16777216,
16711935, 16647160, 16582885, 16519104, 16455813, 16393004, 16330674, 16268815, 16207423, 16146493, 16086019, 16025997, 15966421, 15907286, 15848587, 15790320, 15732480, 15675063, 15618062, 15561475, 15505297, 15449522, 15394148, 15339168, 15284581, 15230380, 15176562, 15123124, 15070060, 15017368, 14965042, 14913080,
14861478, 14810232, 14759337, 14708792, 14658591, 14608732, 14559211, 14510024, 14461169, 14412641, 14364439, 14316557, 14268994, 14221746, 14174809, 14128181, 14081859, 14035840, 13990121, 13944699, 13899570, 13854733, 13810184, 13765920, 13721940, 13678239, 13634816, 13591668, 13548792, 13506186, 13463847, 13421772,
13379960, 13338407, 13297112, 13256071, 13215283, 13174746, 13134456, 13094412, 13054611, 13015052, 12975732, 12936648, 12897799, 12859183, 12820797, 12782640, 12744710, 12707003, 12669520, 12632256, 12595212, 12558383, 12521770, 12485370, 12449180, 12413200, 12377427, 12341860, 12306496, 12271335, 12236374, 12201611,
12167046, 12132675, 12098499, 12064514, 12030720, 11997115, 11963697, 11930464, 11897416, 11864550, 11831865, 11799360, 11767033, 11734883, 11702908, 11671106, 11639477, 11608019, 11576731, 11545611, 11514657, 11483869, 11453246, 11422785, 11392486, 11362347, 11332367, 11302545, 11272880, 11243369, 11214013, 11184810,
11155759, 11126858, 11098106, 11069503, 11041047, 11012736, 10984571, 10956549, 10928669, 10900932, 10873334, 10845877, 10818557, 10791375, 10764329, 10737418, 10710641, 10683998, 10657487, 10631107, 10604857, 10578737, 10552745, 10526880, 10501142, 10475529, 10450042, 10424677, 10399436, 10374317, 10349318, 10324440,
10299681, 10275041, 10250518, 10226112, 10201822, 10177647, 10153586, 10129639, 10105805, 10082082, 10058471, 10034970, 10011578, 9988296, 9965121, 9942053, 9919093, 9896238, 9873488, 9850842, 9828300, 9805861, 9783524, 9761289, 9739154, 9717120, 9695185, 9673349, 9651611, 9629971, 9608427, 9586980,
9565628, 9544371, 9523209, 9502140, 9481164, 9460280, 9439488, 9418787, 9398177, 9377657, 9357227, 9336885, 9316631, 9296466, 9276387, 9256395, 9236488, 9216668, 9196932, 9177280, 9157712, 9138228, 9118826, 9099506, 9080269, 9061112, 9042036, 9023040, 9004124, 8985287, 8966528, 8947848,
8929245, 8910720, 8892271, 8873899, 8855602, 8837381, 8819234, 8801162, 8783164, 8765239, 8747387, 8729608, 8711901, 8694265, 8676701, 8659208, 8641785, 8624432, 8607148, 8589934, 8572789, 8555711, 8538702, 8521760, 8504885, 8488077, 8471335, 8454660, 8438049, 8421504, 8405024, 8388608,
8372255, 8355967, 8339742, 8323580, 8307480, 8291442, 8275466, 8259552, 8243699, 8227906, 8212174, 8196502, 8180890, 8165337, 8149843, 8134407, 8119030, 8103711, 8088450, 8073246, 8058099, 8043009, 8027976, 8012998, 7998076, 7983210, 7968399, 7953643, 7938941, 7924293, 7909700, 7895160,
7880673, 7866240, 7851859, 7837531, 7823255, 7809031, 7794858, 7780737, 7766667, 7752648, 7738679, 7724761, 7710892, 7697074, 7683304, 7669584, 7655913, 7642290, 7628716, 7615190, 7601712, 7588281, 7574898, 7561562, 7548272, 7535030, 7521834, 7508684, 7495579, 7482521, 7469508, 7456540,
7443617, 7430739, 7417905, 7405116, 7392370, 7379668, 7367010, 7354396, 7341824, 7329295, 7316809, 7304366, 7291964, 7279605, 7267288, 7255012, 7242777, 7230584, 7218432, 7206320, 7194250, 7182219, 7170229, 7158278, 7146368, 7134497, 7122665, 7110873, 7099119, 7087404, 7075728, 7064090,
7052491, 7040929, 7029406, 7017920, 7006471, 6995060, 6983686, 6972349, 6961049, 6949785, 6938557, 6927366, 6916211, 6905092, 6894008, 6882960, 6871947, 6860970, 6850027, 6839119, 6828246, 6817408, 6806604, 6795834, 6785098, 6774396, 6763728, 6753093, 6742491, 6731923, 6721388, 6710886,
6700416, 6689980, 6679575, 6669203, 6658864, 6648556, 6638280, 6628035, 6617823, 6607641, 6597492, 6587373, 6577285, 6567228, 6557201, 6547206, 6537240, 6527305, 6517401, 6507526, 6497681, 6487866, 6478080, 6468324, 6458597, 6448899, 6439231, 6429591, 6419981, 6410398, 6400845, 6391320,
6381823, 6372355, 6362914, 6353501, 6344117, 6334760, 6325430, 6316128, 6306853, 6297606, 6288385, 6279191, 6270025, 6260885, 6251771, 6242685, 6233624, 6224590, 6215582, 6206600, 6197644, 6188713, 6179809, 6170930, 6162076, 6153248, 6144445, 6135667, 6126914, 6118187, 6109484, 6100805,
6092152, 6083523, 6074918, 6066337, 6057781, 6049249, 6040741, 6032257, 6023797, 6015360, 6006947, 5998557, 5990191, 5981848, 5973528, 5965232, 5956958, 5948708, 5940480, 5932275, 5924092, 5915932, 5907795, 5899680, 5891587, 5883516, 5875468, 5867441, 5859436, 5851454, 5843492, 5835553,
5827635, 5819738, 5811863, 5804009, 5796177, 5788365, 5780575, 5772805, 5765056, 5757328, 5749621, 5741934, 5734268, 5726623, 5718997, 5711392, 5703807, 5696243, 5688698, 5681173, 5673668, 5666183, 5658718, 5651272, 5643846, 5636440, 5629052, 5621684, 5614336, 5607006, 5599696, 5592405,
5585133, 5577879, 5570645, 5563429, 5556231, 5549053, 5541893, 5534751, 5527628, 5520523, 5513436, 5506368, 5499317, 5492285, 5485271, 5478274, 5471295, 5464334, 5457391, 5450466, 5443558, 5436667, 5429794, 5422938, 5416099, 5409278, 5402474, 5395687, 5388917, 5382164, 5375428, 5368709,
5362006, 5355320, 5348651, 5341999, 5335363, 5328743, 5322140, 5315553, 5308983, 5302428, 5295890, 5289368, 5282862, 5276372, 5269898, 5263440, 5256997, 5250571, 5244160, 5237764, 5231385, 5225021, 5218672, 5212338, 5206020, 5199718, 5193430, 5187158, 5180901, 5174659, 5168432, 5162220,
5156023, 5149840, 5143673, 5137520, 5131382, 5125259, 5119150, 5113056, 5106976, 5100911, 5094860, 5088823, 5082801, 5076793, 5070799, 5064819, 5058854, 5052902, 5046965, 5041041, 5035131, 5029235, 5023353, 5017485, 5011630, 5005789, 4999961, 4994148, 4988347, 4982560, 4976787, 4971026,
4965280, 4959546, 4953826, 4948119, 4942424, 4936744, 4931076, 4925421, 4919779, 4914150, 4908534, 4902930, 4897340, 4891762, 4886197, 4880644, 4875104, 4869577, 4864062, 4858560, 4853070, 4847592, 4842127, 4836674, 4831234, 4825805, 4820389, 4814985, 4809593, 4804213, 4798846, 4793490,
4788146, 4782814, 4777494, 4772185, 4766889, 4761604, 4756331, 4751070, 4745820, 4740582, 4735355, 4730140, 4724936, 4719744, 4714563, 4709393, 4704235, 4699088, 4693953, 4688828, 4683715, 4678613, 4673522, 4668442, 4663373, 4658315, 4653269, 4648233, 4643207, 4638193, 4633190, 4628197,
4623215, 4618244, 4613283, 4608334, 4603394, 4598466, 4593547, 4588640, 4583743, 4578856, 4573980, 4569114, 4564258, 4559413, 4554578, 4549753, 4544938, 4540134, 4535340, 4530556, 4525782, 4521018, 4516264, 4511520, 4506786, 4502062, 4497347, 4492643, 4487949, 4483264, 4478589, 4473924,
4469268, 4464622, 4459986, 4455360, 4450743, 4446135, 4441538, 4436949, 4432370, 4427801, 4423241, 4418690, 4414149, 4409617, 4405094, 4400581, 4396077, 4391582, 4387096, 4382619, 4378152, 4373693, 4369244, 4364804, 4360372, 4355950, 4351537, 4347132, 4342737, 4338350, 4333973, 4329604,
4325244, 4320892, 4316550, 4312216, 4307890, 4303574, 4299266, 4294967, 4290676, 4286394, 4282120, 4277855, 4273599, 4269351, 4265111, 4260880, 4256657, 4252442, 4248236, 4244038, 4239849, 4235667, 4231494, 4227330, 4223173, 4219024, 4214884, 4210752, 4206628, 4202512, 4198404, };
int make_fraction1023(int n, int d) {
  assert(n > 0 && n <= 1203);
  if (d > 1) {
    return (int) ((1023ull * (unsigned) n * t[d]) >> 32);
  } else {
    return n * 1023;
  }
}

void test(int n1, int d1, int n2) {
  if (make_fraction1023(n1, d1) != n2) {
    printf("%d/%d --> %d/1023 and not expected %d/1023\n", n1, d1,
        make_fraction1023(n1, d1), n2);
  }
}

int main(void) {
  test(1, 7, 146);
  test(47, 100, 480);
  test(223, 230, 991);
  test(234, 567, 422);
  puts("Done");
}

相关问题