How to negate a positive integer in C without * or - operators?

Question

Hello I am trying to write a function for my lab which requires me to negate a positive number with restricted operators. The operators allowed are: ! ~ & ^ | + << and >>.

My initial approach was to double x using addition: x + x and then subtracting that from x to get the opposite value, but was roadblocked due to the operator restrictions. I am rather new to C and trying to learn, if someone could provide me with the idea behind performing this operation I would greatly appreciate it.

Answer 1

This is probably not what your instructor wants to see, but it works and it does, unlike the ~ operator, not depend on the implementation (sign-magnitude, 1-complement or 2-complement) and does not cause UB. I post this solution since it meets the requirements but is ugly and slow, because i think the task is stupid (the task leads to functions which only work on systems which use 2-complement, i would bet the instructor presents a solution which only works on 2-complement systems).

#include <limits.h>

//Returns the negative value of n,
//n has to be positive. Negative values of n cause UB.
int makeNegative(int n)
{
    int i=INT_MIN;
    while(i+n) //continue till i+n is 0, no need for the < operator
    {
        i++;
    }
    return i;
}

If you want code that does not cause UB when n is negative, you can check for negative values of n:

#include <limits.h>

int isNegative(int n)
{
    int i=INT_MIN;
    while(i)
    {
        i++;
        if(n==INT_MAX) //when n reaches INT_MAX, it was positive
        {              //we need to check for it before increment
          return 0;    //increment a int of value INT_MAX would cause UB 
        }
        n++;
        if(!n) //n is 0 means n was negative before
        {
          return 1;
        }
    }
    return 0;
}

//Returns the negative value of n i n is positive
//returns n in any other case
int makeNegative(int n)
{
    if(isNegative(n))
    {
        return n;
    }
    int i=INT_MIN;
    while(i+n) //continue till i+n is 0, no need for the < operator
    {
        i++;
    }
    return i;
}

2-Complement system

As others already pointed out, this is what your instructor probably wants to see: n=(~n)+1;. This only works when you are using 2-complement and it causes UB for INT_MIN.

Lets say we have the number 1 stored in the variable n. Now we want to negate n. Then we have to invert the variable, means that we flip every bit and then add +1. Here is an example with a int8_t.

Value | Bit pattern |
    1 |  0b00000001 | n is set to 1
   -2 |  0b11111110 | We inverted n
   -1 |  0b11111111 | We added 1 to n

The advantage of a 2-complement system is, that we can use every possible bit pattern for a value and that we can use the same logic for signed and unsigned variables for most operations. The binary value of 0b11111111 is 0xFF==255 for a unsigned variable. The C standard requires that unsigned integers wrap around. If we store 0xFF in a uint8_t variable and add 1, the result can't be stored in a uint8_t and wraps around to 0. Means 0b11111111+1==0. As we saw before we can store the value -1 in a int8_t as the bit pattern 0b11111111. And here we also get 0b11111111+1==0 => -1+1==0.

One feature 2-Complement systems have is that there is one more negative value than positive values. INT8_MIN<-INT8_MAX. INT8_MIN has the bit pattern 0b10000000, if we invert it we get the bit pattern 0b01111111==INT8_MAX. When we now add 1, we get an overflow and a overflow causes UB for signed variables*. So the statement n=(~n)+1; can causes UB when n is signed. The same is true for n=-n, n=n*-1 and n=n/-1, since they all fail when n has the lowest possible value which we can not negate.

*When you tell the compiler to use wrap around for signed variables, (-fwrapv on gcc), it would result in INT8_MIN again.

Answer 2

Here is the classic solution you are probably expected to produce:

int negate_positive_number(int n) {
    return ~n + 1;
}

The problem with this code is it only works on 2's complement systems. This is not a real issue as you are probably not going to encounter other architectures today.

Yet the C Standard supports other representations for signed integers:

• sign/magnitude where negative values have the same value bits set but a sign bit set,
• ones' complement where negative values have all bits reversed from the representation of the positive value.

In both of these historical oddities, there are 2 possible representations for 0, one of which could be a trap value.

Here is an original solution that works for all 3 architectures: 2's complement, sign/magnitude and ones' complement systems: a bit obscure but more portable:

#include <limits.h>

int negate_positive_number(int n) {
    return (n ^ INT_MIN ^ INT_MAX) + (1 & (INT_MIN + INT_MAX));
}

It uses +, ^ and & and the definitions from <limits.h>, which might be off limits. I assume parentheses are allowed too.

Answer 3

2 complement

int minus(int x)
{
    return ~x + 1;
}

test:

https://godbolt.org/z/c89GWT