Why is this modular arithmetic incorrect in my rotate string function?

Question

I am writing a rotate string function in C. The intended behavior is that the strings chars will be rotated using a modulus of the string length, and a key. The function seems to work in the forward direction, but if I specify a negative key, I want the string to rotate in the opposite direction, and this is where the bug exists. For completeness/testing purposes, I will supply the entire program, but below that I will highlight the problem area and explain what I've done to try to debug so far:

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

char *rotate_str(char *mutable_str, int key);

int main(void) {
    char str[] = "This is a test.";

    char *output = rotate_str(str, -2);
    printf("%s\n", output);
    return EXIT_SUCCESS;
}

//Bug - negative rotate doesn't work properly - test with -2
char *rotate_str(char *mutable_str, int key) {
    assert(mutable_str);
    size_t len = strlen(mutable_str);
    ssize_t i;
    char *output = malloc(len + 1);
    assert(output);

    ssize_t rotated_index = 0;
    for (i = 0; i < len; ++i) {
        rotated_index = (i + key) % len; // Get the new index position
        output[rotated_index] = mutable_str[i];
    }
    output[len] = '\0';
    return output;
}

The trouble spot is:

    for (i = 0; i < len; ++i) {
        rotated_index = (i + key) % len; // Get the new index position
        output[rotated_index] = mutable_str[i];
    }

On the first iteration, i = 0, key = -2, and len = 15. When I compute -2 + 0 % 15 using a calculator (Google in this case), I get 13. However, my C program is making rotated_index = 14 as per my debugger output. So this itself is already a concern.

When I do a positive 2 as key, I get output: t.This is a tes, which is what I'd expect. But when I do the -2 as key, I get output: is is a test. but the expected output is is is a test.Th

_When I compute -2 + 0 % 15 using a calculator (Google in this case), I get 13_, though `-2 + 0 % 15` --> `-2` — David Ranieri, Mar 25 '20 at 20:17
Does this answer your question? [Modulo operation with negative numbers](https://stackoverflow.com/questions/11720656/modulo-operation-with-negative-numbers) — r3mainer, Mar 25 '20 at 20:18
@DavidRanieri In C, `-2 + 0 % 15` is just `-2 + 0` since `%` binds more tightly than `+`. — Tom Karzes, Mar 25 '20 at 20:21
The `%` in C is a remainder; its behaviour is described in the link r3mainer gave above. You can fix your code by making the the numerator positive: Add `len` to the `key` before the loop or calculate `(i + key + len) % len` — M Oehm, Mar 25 '20 at 20:22
The `%` operator in C is a remainder operator. It does not perform a mod function the way it's normally defined in mathematics (unless the first operand is non-negative and the second is positive). You can add multiples of `len` to `i + key` before appying `%`, forcing it into the non-negative range, or you can check its sign and handle the negative case specially. — Tom Karzes, Mar 25 '20 at 20:23

score 2 · Answer 1 · answered Aug 31 '20 at 20:32

Your issue has to do with using the modulo operator with negative numbers.

To start with, you are using size_t which is an unsigned type, but you are trying to put negative numbers into the unsigned type. There is a better explanation why this is an issue here: https://stackoverflow.com/a/39337256/13341069

Handle the key < (len * -1).

 char* rotate_str(char *mutable_str, int key)
 {
     assert(mutable_str);
     int len = strlen(mutable_str);
     int i;
     char *output = (char *)malloc(len + 1);
     assert(output);

     int remainder;
     int rotated_index = 0;
     for (i = 0; i < len; ++i)
     {
         remainder = (i + key) % len; // Get the new index position. range is (-len to +len)
         rotated_index = (remainder + len) % len; // Add len to shift value range to [0, +len).
         output[rotated_index] = mutable_str[i];
     }
     output[len] = '\0';
     return output;
 }

Why is this modular arithmetic incorrect in my rotate string function?

1 Answers1