时间戳

首页 > 解决方案 > 如何让这个程序更有效率？

c - 如何让这个程序更有效率？

问题描述

我怎样才能找到有多少 Z 数 (Z < N) 具有属性 (N xor Z)> N 其中 N 是 32 位数字并且程序的复杂性是 O(log N);

这是简单的方法，但我真的不知道如何在 O(log N);

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main()
{

    int n;
    int z;
    int contor = 0;
    FILE* in;
    FILE *out;
    in= fopen("in.txt", "rt");
    if (in == NULL)
    {
        printf("ERROR!");
        return -1;
    }
    else
    {
        fscanf(in, "%d", &n);
        for (z = 0; z < n; z++)
        {
            if ((n ^ z) > n)
            {
                contor++;
            }
        }
    }
    out = fopen("out.txt", "wt");
    if (out == NULL)
    {
        printf("Error!");
        return 0;
    }
    else
    {
        fprintf(out, "%d", contor);
    }
    fclose(out);
    fclose(in);
    return 0;
}

标签： c

解决方案

我会给你一个强有力的提示——不是一个完整的解决方案，但它应该让你沿着正确的轨道思考。

关键是用二进制来思考。二进制中的任何数字都将是 1，后跟 0 和 1 位的某种组合。例如：

100 = 1100100
 55 =  110111
 17 =   10001

XOR 可以被认为是位翻转。N xor Z取所有 1 位Z并翻转N.

如果你有一个N像上面这样的数字，你可以翻转哪些位并最终得到一个更大的数字？好吧，如果您将 1 翻转为 0，它会变小。如果你将 0 翻转为 1，它会变得更大。

拿100。将 0 翻转为 1，它会变得更大：

100 = 1100100
108 = 1101100

将 1 翻转为 0 并缩小：

100 = 1100100
 68 = 1000100

该问题的解决方案将涉及计算N. （答案不仅仅是0 位的计数，而且它肯定会以某种方式使用该计数。）直觉上，这似乎是在正确的轨道上——你正在寻找一个对数解决方案，并且数字有一个对数位。

推荐阅读