0

我编写了这段代码来计算数字范围之间的设置位数。我的程序编译得很好并给出了正确的输出。大量输入和“超出时间限制”花费了太多时间。

#define forn(i, n) for(long int i = 0; i < (long int)(n); i++)
#define ford(i, n) for(long int i = (long int)(n) - 1; i >= 0; i--)
#define fore(i, a, n) for(long int i = (int)(a); i < (long int)(n); i++)


long int solve(long int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int main() {
    freopen("C:/Projects/CodeChef/SetBits/input.txt", "rt", stdin);
    freopen("C:/Projects/CodeChef/SetBits/output.txt", "wt", stdout);

    int tt;
    long long int num1;
    long long int num2;
    scanf("%d", &tt);
    forn(ii, tt) {
        unsigned long int bits = 0;
        unsigned long long int total_bits = 0;
        scanf("%lld",&num1);
        scanf("%lld",&num2);
        fore(jj, num1, num2+1) {
                bits = solve(jj);
                total_bits += bits;
                }

        printf("%lld\n",total_bits);
    }

    return 0;
}

示例测试用例：-

样本输入：3

-2 0

-3 4

-1 4

样本输出：

63

99

37

对于第一种情况，-2 包含 31 个 1，后跟一个 0，-1 包含 32 个 1，0 包含 0 个 1。因此总数为 63。

对于第二种情况，答案是 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

具有大值的测试用例：-

10

-1548535525 662630637

-1677484556 -399596060

-2111785037 1953091095

643110128 1917824721

-1807916951 491608908

-1536297104 1976838237

-1891897587 -736733635

-2088577104 353890389

-2081420990 819160807

-1585188028 2053582020

关于如何优化代码以减少时间的任何建议。所有有用的建议和答案都将通过投票表示赞赏。:)

4

1 回答 1

1

我真的不知道你在做什么，但我知道你可以大量清理你的代码，你可以内联你的函数。

此外，我冒昧地“改写”您的代码，您正在使用像 C 一样的 C++，而这些定义只是严峻的，将文件映射到 stdio 甚至更糟。我没有测试或编译代码，但它就在那里。

#include <fstream>

inline long int solve(long int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int main() {
    long first, last;
    unsigned count;
    std::ifstream inf("C:/Projects/CodeChef/SetBits/input.txt");
    std::ofstream off("C:/Projects/CodeChef/SetBits/output.txt");
    inf >> count;
    for(unsigned i=0u; i!=count; ++i) {
        inf >> first >> last;
        long total=0;
        ++last;
        for(long t=first; t!=last; ++t) {
            total+=solve(t);
        }
        off << total << '\n';
    }
    return 0;
}

关于如何加快速度的一些想法：

  • 您可以构建计算值的 std::map ，如果它们先前已被处理，则使用它们而不是重新计算。
  • 做同样的事情，但存储范围而不是单个值，但这会很棘手。您可以查看映射中是否存在值并在映射中递增，直到没有更多预处理值，在这种情况下开始处理它们以进行迭代。
  • 检查上一个数字和下一个数字之间是否存在微不足道的序列，您可以计算出第一个值，然后将其递增。
  • 这样的序列可能有一个 O(1) 算法
  • 查看英特尔 TBB 并使用 tbb::parallel 之类的东西将工作分配到每个内核上，因为您正在处理如此小的内存或内存，那么您应该在大块大小的情况下获得非常好的回报。
于 2012-04-11T14:22:56.380 回答