How casting works in C?-CodePudding

I was solving a problem on leetcode and this was my code.

/*
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;
}

It is working fine for smaller values (possibly values that int can hold). but when calculating large values it was giving unexpected result

then I thought that might be due to the overflow so I changed variable int answer to long int answer which I thought will resolve the problem, but it didn't and also broke the code for even smaller values

then I noticed I am using pow function which will for sure exceed the limit for high values of length, As pow gives double value in return, I was casting it to an int with (int)pow(2, length - (i 1)) before, which I changed to (long int)pow(2, length - (i 1))

I was passing these values to test the code.

4
16
1111010010111101
2
10
6
101101
4
1111

and expected result was

but i got

I am getting the expected result when I am using int answer and (int)pow(...) but if I cast answer or pow to long, I am getting unexpected result. I am not sure if this is due to cast or something else but as far as I noticed it happens only when I am casting these variables into long.

CodePudding user response：

There are multiple problems in the code:

while (t--) will cause unexpected behavior if the value of t entered is negative. Use while (t-- > 0)
char string[length]; does not have enough space for length characters and the null terminator. Use char string[length 1];
scanf("%s", string); does not provide any protection against buffer overflow. There is no simple way to tell scanf() to read up to a variable number of bytes for %s. Since the length can be as large as 100000, you should probably allocate the array from the heap and read the bits with getchar().
the code in the loop does not seem to implement a solution for the problem:

Given a binary string S, she defines the beauty of the string as the bitwise XOR of decimal representations of all substrings of S.

The instructions are misleading because the result has nothing to do with the decimal representation of anything. But your code does not convert all substrings and only the result should be displayed modulo 998244353. Applying xor to the modules would produce a different result.
furthermore there is no need for pow to convert a binary representation: you can multiply res by 2 and add the value of the next digit in the loop.

To compute the resulting bitstring, consider the bit at offset i, starting at the beginning of the string with offset 0:

it will be XORed with itself i times for substrings with just a prefix removed.
Then each bit with an index j smaller than i will be XORed j times for each substring with the last i-j bits removed.

XORing i times will produce 0 if i is odd, hence has the same effect as masking with the opposite of the last bit of i.

You could use 2 nested loops for this:

      for (int i = 0; i < length; i  ) {
          int bit = (string[i] - '0') & ~i;
          for (j = 0; j < i; j  ) {
              bit ^= (string[j] - '0') & ~j;
          }
          answer = (answer * 2   bit) % 998244353;
      }

Here is a modified version:

#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;
}