Recursive Complexity

Thoughts and musings of a programmer and wanna be entrepreneur

Archive for January 2015

Modulo operator in C

leave a comment »

If you are programming in C, then you would know that the way to find the remainder when an integer a is divided by n is by using the modulo operator ( % ), like this, r = a % n. This modulo operator or fundamentally the task of finding the remainder when an integer is divided by another integer, can be used to find whether an integer is odd or even. If an integer leaves remainder 1 when divided by 2, it’s odd, else it’s even. Let’s implement a function in C to do the same.

/*
* This function returns true if an integer is odd, else false
*/
bool is_odd(int a)
{
        return a % 2 == 1;
}

This is a pretty simple function and should help us in our quest. Let’s use this function to find whether the integers 1 and -1 are odd or not.


int main(int argc, char **argv)
{
        if (is_odd(1))
               printf("1 is odd");

       if (is_odd(-1))
               printf("-1 is odd");

       return 0;
}

Run this simple program on a Windows and a Linux machine and be startled. Instead of returning true for both values, the function is_odd returns true for 1 and false for -1, though it’s common knowledge that -1 is odd. Why is it so ? This is due to the way the modulo operation is implemented in the C language. In fact, different languages implement the task of finding the remainder differently and a programmer should be careful when using the modulo operator or a function that does the same in any programming language. The implementation in C is known as the truncated division operation to find the remainder. This Wikipedia article describes the different ways the modulo operation can be implemented. It also shows a table specifying the behaviour of the modulo operation in different programming languages.

In C, the truncated division operation gives a remainder whose sign is the same as that of the dividend. Hence, in function is_odd, a % 2, for a = -1 returns a remainder of -1 and the subsequent comparison with 1 returns false. The safe way to find whether an integer is odd or even using the modulo operator in C is to do the below.

bool is_odd(int a)
        return a % 2 != 0;
}

Thanks to this blog from my friend Shreevatsa which helped me look up the different ways of finding the remainder and their choice in a programming language like C or C++.

Advertisements

Written by Vivek S

January 12, 2015 at 5:24 pm

Posted in Tech

Tagged with ,

TED Blog

The TED Blog shares interesting news about TED, TED Talks video, the TED Prize and more.