如何处理C中的整数溢出

I'm trying to create anagrams from words where answers are supposed to be for example:

我试图用答案应该是的例子来创建字谜:

The word "at" should have two anagrams. ordeals should have 5040 anagrams. abcdABCDabcd shoud have 29937600 anagrams. abcdefghijklmnopqrstuvwxyz should have 403291461126605635584000000 anagrams. abcdefghijklmabcdefghijklm should have 49229914688306352000000.

“at”这个词应该有两个字谜。考验应该有5040个字谜。 abcdABCDabcd shoud有29937600个anagrams。 abcdefghijklmnopqrstuvwxyz应该有403291461126605635584000000 anagrams。 abcdefghijklmabcdefghijklm应该有49229914688306352000000。

My program seems to work for the first three examples but not for the last two. How can I change the program to make it work?

我的程序似乎适用于前三个示例,但不适用于最后两个示例。如何更改程序以使其正常工作?

#include <stdio.h>
#include <memory.h>

int contains(char haystack[], char needle) {
    size_t len = strlen(haystack);
    int i;
    for (i = 0; i < len; i++) {
        if (haystack[i] == needle) {
            return 1;
        }
    }
    return 0;
}

unsigned long long int factorial(unsigned long long int f) {
    if (f == 0)
        return 1;
    return (f * factorial(f - 1));
}

int main(void) {
    char str[1000], ch;
    unsigned long long int i;
    unsigned long long int frequency = 0;
    float answer = 0;
    char visited[1000];
    int indexvisited = 0;
    printf("Enter a string: ");
    scanf("%s", str);
    for (i = 0; str[i] != '\0'; ++i);
    unsigned long long int nominator = 1;
    for (int j = 0; j < i; ++j) {
        ch = str[j];
        frequency = 0;
        if (!contains(visited, ch)) {
            for (int k = 0; str[k] != '\0'; ++k) {
                if (ch == str[k])
                    ++frequency;
            }
            printf("Frequency of %c = %lld\n", ch, frequency);
            visited[indexvisited] = ch;
            visited[++indexvisited] = '\0';
            nominator = nominator * factorial(frequency);
        }
    }
    printf("Number of anagrams = %llu\n", (factorial( i )/nominator ) );
    return 0;

}

3 个解决方案

#1

Even though an unsigned long long is pretty big, it's not completely unbounded. Its maximum value is around 1*10^19. If your source string is 26 characters long, you calculate factorial(26) - which is around 4*10^26, much much bigger than will fit in an unsigned long long.

尽管无符号长长度非常大,但它并非完全*限。它的最大值约为1 * 10 ^ 19。如果源字符串长度为26个字符,则计算阶乘(26) - 大约为4 * 10 ^ 26,比无符号长整数大得多。

#2

Just for the fun, here's the best I could come up with using only built-in datatypes. Instead of calculating factorials over and over (and, btw, avoid recursion for such things!), it has an "intelligent" n over k function. Note that it attempts to detect an overflow, but this is not really reliable.

只是为了好玩,这里我只能使用内置数据类型。它不是一遍又一遍地计算阶乘(而且,顺便说一下,避免这种事情的递归!),它有一个“智能”n over k函数。请注意,它会尝试检测溢出,但这并不可靠。

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef size_t AsciiCountTable[0x80];

static int countAsciiCharacters(const char *input, AsciiCountTable table)
{
    const char *c = input;
    while (*c)
    {
        if ((unsigned char)*c > 0x7f)
        {
            // not an ascii character
            return 0;
        }
        ++table[(int)*c];
        ++c;
    }
    return 1;
}

static unsigned long long nOverK(size_t n, size_t k)
{
    unsigned long long result = 1;
    size_t barrier = n - k;
    if (k > barrier) barrier = k;

    for (size_t i = n; i > barrier; --i)
    {
        result *= i;
    }
    for (size_t i = 2; i <= n - barrier; ++i)
    {
        result /= i;
    }
    return result;
}

int main(int argc, char **argv)
{
    if (argc < 2)
    {
        fprintf(stderr, "Usage: %s <word>\n", argv[0]);
        return EXIT_FAILURE;
    }

    AsciiCountTable countTable = {0};
    if (!countAsciiCharacters(argv[1], countTable))
    {
        fputs("Only ASCII characters allowed.\n", stderr);
        return EXIT_FAILURE;
    }

    size_t positions = strlen(argv[1]);
    unsigned long long permutations = 1;

    for (int i = 0; i < 0x80; ++i)
    {
        size_t n = positions;
        size_t k = countTable[i];
        if (k > 0)
        {
            unsigned long long temp = permutations;
            permutations *= nOverK(n, k);
            if (temp > permutations)
            {
                fputs("Overflow detected.\n", stderr);
                return EXIT_FAILURE;
            }
            positions -= k;
        }
    }

    printf("permutations: %" PRIuMAX "\n", permutations);
    return EXIT_SUCCESS;
}

#3

When you need to work with ridicously large numbers you have to split things, i'd say that using a long double to store the root number and a long unsigned int to store the 10th potence would do the trick.

当你需要处理大量的数字时,你必须拆分东西,我会说使用一个长双来存储根数和一个长的unsigned int来存储第十个潜力就可以了。

4*10^26  == ld 4, lui 26 == ld * 10^lui

this could be usefull for calculations, not sure tho how to represent it, it'll overflow everything but a string

这可能对计算有用,不知道如何表示它,它会溢出除字符串之外的所有内容