How to code a modulo (%) operator in C/C++/Obj-C that handles negative numbers
First of all I'd like to note that you cannot even rely on the fact that (-1) % 8 == -1
. the only thing you can rely on is that (x / y) * y + ( x % y) == x
. However whether or not the remainder is negative is implementation-defined.
Reference: C++03 paragraph 5.6 clause 4:
The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined.
Here it follows a version that handles both negative operands so that the result of the subtraction of the remainder from the divisor can be subtracted from the dividend so it will be floor of the actual division. mod(-1,8)
results in 7, while mod(13, -8)
is -3.
int mod(int a, int b)
{
if(b < 0) //you can check for b == 0 separately and do what you want
return -mod(-a, -b);
int ret = a % b;
if(ret < 0)
ret+=b;
return ret;
}
How I can solve C++ output negative numbers when using modulo?
From cppreference.com:
double fmod (double numer, double denom);
The floating-point remainder of the division operationx/y
calculated by this function is exactly the valuex - n*y
, wheren
isx/y
with its fractional part truncated.
The returned value has the same sign asx
and is less thany
in magnitude.
In your case it is -10 - (-10)/11 * 11 = -10 - 0 * 11 = -10
, which is correct for that implementation of fmod
. If you need another answer, you should implement your own version, as modulo
is defined in different ways for negative numbers.
real modulo operator in C/C++?
There is no simple way to do it, however it is more efficient if you create a two-line solution, and spare a multiplication plus determining n
.
inline int modulo(int a, int b) {
const int result = a % b;
return result >= 0 ? result : result + b;
}
Also, if you need to work correctly for negative b
numbers as well, add to the beginning:
if(b < 0) return modulo(-a, -b);
Weird Objective-C Mod Behavior for Negative Numbers
result = n % 3;
if( result < 0 ) result += 3;
Don't perform extra mod operations as suggested in the other answers. They are very expensive and unnecessary.
Fastest way to get a positive modulo in C/C++
Most of the time, compilers are very good at optimizing your code, so it is usually best to keep your code readable (for both compilers and other developers to know what you are doing).
Since your array size is always positive, I suggest you to define the quotient as unsigned
. The compiler will optimize small if/else blocks into conditional instructions which have no branches:
unsigned modulo( int value, unsigned m) {
int mod = value % (int)m;
if (mod < 0) {
mod += m;
}
return mod;
}
This creates a very small function without branches:
modulo(int, unsigned int):
mov eax, edi
cdq
idiv esi
add esi, edx
mov eax, edx
test edx, edx
cmovs eax, esi
ret
For example modulo(-5, 7)
returns 2
.
Unfortunately, since the quotient is not known they must perform an integer division, which is a bit slow compared to other integer operations. If you know the sizes of your array are power of two, I recommend keeping these function definitions in a header, so that the compiler can optimize them into a more efficient function. Here is the function unsigned modulo256(int v) { return modulo(v,256); }
:
modulo256(int): # @modulo256(int)
mov edx, edi
sar edx, 31
shr edx, 24
lea eax, [rdi+rdx]
movzx eax, al
sub eax, edx
lea edx, [rax+256]
test eax, eax
cmovs eax, edx
ret
See assembly: https://gcc.godbolt.org/z/DG7jMw
See comparison with most voted answer: http://quick-bench.com/oJbVwLr9G5HJb0oRaYpQOCec4E4
Edit: turns out Clang is able to generate a function without any conditional move instructions (which cost more than regular arithmetic operations). This difference is completely negligible in the general case due to the fact that the integral division takes around 70% of the total time.
Basically, Clang shifts value
right to extend its sign bit to the whole width of m
(that is 0xffffffff
when negative and 0
otherwise) which is used to mask the second operand in mod + m
.
unsigned modulo (int value, unsigned m) {
int mod = value % (int)m;
m &= mod >> std::numeric_limits<int>::digits;
return mod + m;
}
explicit MOD in C?
The best option I can think of is to compute:
((-1 % 4) + 4 ) % 4
Here you may replace -1
with any value and you will get MOD
not REM
.
Why is a modulo operation returning an unexpected value
Because of integer promotions in the C standard. Briefly: any type "smaller" than int
is converted to int
before usage. You cannot avoid this in general.
So what goes on: i
is promoted to int
. The expression is evaluated as int
(the constants you use are int
, too). The modulus is -1
. This is then converted to uint8_t
: 255
by the assignment.
For printf
then i
is integer-promoted to int
(again): (int)255
. However, this does no harm.
Note that in C89, for a < 0
, a % b
is not necessarily negative. It was implementation-defined and could have been 15
. However, since C99, -1 % 16
is guaranteed to be -1
as the division has to yield the algebraic quotient.
If you want to make sure the modulus gives a positive result, you have to evaluate the whole expression unsigned
by casting i
:
i = ((unsigned)i - 1) % 16;
Recommendation: Enable compiler warnings. At least the conversion for the assignment should give a truncation warning.
Related Topics
Pointers, Smart Pointers or Shared Pointers
What Does "Default" Mean After a Class' Function Declaration
What Are the Advantages of Using Nullptr
What's Your Favorite Profiling Tool (For C++)
In C/C++ What's the Simplest Way to Reverse the Order of Bits in a Byte
Calculating Normals in a Triangle Mesh
How to Get the Error Message from the Error Code Returned by Getlasterror()
C++: What Regex Library Should I Use
Error Lnk2005, Already Defined
What Is a Subnormal Floating Point Number
How to Initialize Std::Vector from C-Style Array
What Belongs in an Educational Tool to Demonstrate the Unwarranted Assumptions People Make in C/C++
Const Int' Vs. 'Int Const' as Function Parameters in C++ and C
Creating All Possible K Combinations of N Items in C++
How to Printf Uint64_T? Fails With: "Spurious Trailing '%' in Format"