C 中的强制转换是如何进行的？

Question

我正在 leetcode 上解决问题，这是我的代码。

/*
max int 2147483647 (10^10)
max uint 4294967295 (10^10)
ULONG_MAX 18446744073709551615 (10^20)
LONG_MAX 9223372036854775807 (10^20)
USHRT_MAX 65535, SHRT_MAX 32767
*/

#include <stdio.h>
#include <math.h>

int main(void) {
    int t; 
    scanf("%d", &t);
    while (t--) {
        int length;
        scanf("%d", &length);
        char string[length];
        scanf("%s", string);
        long int answer = 0;
        int ones = 0;
        for (int i = 0; i < length; i++) {
            ones = ones + (string[i] == '1') * (i + 1);
            if (ones & 1) {
                answer = (answer + (long int)pow(2, length - (i + 1))) % 998244353;
            }
        }
        printf("%ld\n", answer);
    }
    
    return 0;
}

它对于较小的值（可能是 int 可以保存的值）工作得很好。但是当计算大值时，它给出了意想不到的结果

，然后我认为这可能是由于溢出造成的，所以我将变量 int answer 更改为 long int answer 我认为这会解决这个问题问题，但它没有，而且还破坏了更小的值的代码

，然后我注意到我正在使用 pow 函数，它肯定会超出高长度值的限制，如 pow< /code> 给出双值作为回报，我将其转换为int 与之前的 (int)pow(2, length - (i+1)) ，我将其更改为 (long int)pow(2, length - (i+1))

我传递这些值来测试代码。

4
16
1111010010111101
2
10
6
101101
4
1111

预期的结果是，

49359
3
48
12

但我得到了

49359
65535
49152
49152

当我使用 int answer 和 (int)pow(...) 时，我得到了预期的结果，但如果我投射答案或 pow长久以来，我得到了意想不到的结果。我不确定这是否是由于强制转换或其他原因造成的，但据我所知，只有当我将这些变量强制转换为 long 时才会发生这种情况。

Answer 1

代码中存在多个问题：

• 如果输入的 t 值为负数，

  while (t--) 将导致意外行为。使用while (t-->0)

• char string[length]; 没有足够的空间容纳 length 个字符，并且空终止符。使用char string[length + 1];

• scanf("%s", string); 不提供任何针对缓冲区溢出的保护。没有简单的方法可以告诉 scanf() 为 %s 读取可变数量的字节。由于长度可能大到 100000，因此您可能应该从堆中分配数组并使用 getchar() 读取这些位。

• 循环中的代码似乎没有实现问题的解决方案：

  <块引用>

  给定一个二进制字符串S，她将字符串的美感定义为所有子字符串的十进制表示的按位异或>S.

  这些说明具有误导性，因为结果与任何内容的十进制表示形式无关。但您的代码不会转换所有子字符串，仅应显示对 998244353 取模的结果。对模块应用异或会产生不同的结果。

• 此外，不需要 pow 转换二进制表示：您可以将 res 乘以 2，然后添加循环中下一个数字的值。

要计算生成的位串，请考虑偏移量 i 处的位，从偏移量 0 的字符串开头开始：

• 它将与自身进行异或 i 次仅删除前缀的子字符串。

• 然后，对于每个子字符串，索引 j 小于 i 的每个位将与最后一个 ij< 进行异或 j 次/code> 删除了一些位。

  


• 如果 i 为奇数，则异或 i 次将产生 0，因此与使用最后一位相反的掩码具有相同的效果我。

  您可以为此使用 2 个嵌套循环：

   for (int i = 0; i < length; i++) {
            int 位 = (string[i] - '0') & 〜我；
            for (j = 0; j < i; j++) {
                位 ^= (字符串[j] - '0') & 〜j;
            }
            答案 = (答案 * 2 + 位) % 998244353;
        }
  

这是修改后的版本：

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

int main() {
    int t, i, j, c;
    int string_size = 0;
    unsigned char *string = NULL;   /* array for the bits */

    /* read the number of test cases */
    if (scanf("%d", &t) != 1)
        return 1;
    while (t-- > 0) {
        int length;
        /* read the length */
        if (scanf("%d", &length) != 1)
            return 1;
        /* discard the rest of the input line */
        while ((c = getchar()) != EOF && c != '\n')
            continue;
        /* reallocate the string if required */
        if (length > string_size) {
            string_size = length;
            string = realloc(string, string_size);
            if (string == NULL)
                return 1;
        }
        /* read the bits */
        i = 0;
        while (i < length && ((c = getchar()) == '0' || c == '1')) {
            string[i++] = (unsigned char)(c - '0');
        }
        /* discard the rest of the input line */
        while (c != EOF && c != '\n') {
            c = getchar();
        }
        /* compute the answer one bit at a time */
        long int answer = 0;
        for (i = 0; i < length; i++) {
            /* compute the next bit of the result string */
            int bit = string[i] & ~i;
            for (j = 0; j < i; j++) {
                bit ^= string[j] & ~j;
            }
            /* compute the answer one bit at a time, reducing modulo 998244353 */
            answer = (answer * 2 + bit) % 998244353;
        }
        printf("%ld\n", answer);
    }
    free(string);
    return 0;
}