For unsigned n, the value is: MAX - n + 1 (where max is the maximum representable value in the type of n, e.g., UINT_MAX). The article explains this nicely. (I thought of 2's complement when reasoning through this, but you don't actually need to assume 2's complement to follow the reasoning).
So, `-n % n` computes `(MAX - n + 1) % n` efficiently, without needing to worry about corner cases.
I suspect this is useful when you want to generate random numbers with a limited range, where the range doesn't cleanly divide UINT_MAX. You need to cut a bit off the top from your underlying random number generator.
It's calculating ((-n) mod (2^bits)) mod n, where bits is compiler/platform-dependent.
;; TXR Lisp
1> (defun -n%n (n bits)
(mod (mod (- n) (expt 2 bits)) n))
-n%n
2> (-n%n 7 8)
4
3> (-n%n 7 16)
2
4> (-n%n 7 17)
4
5> (-n%n 7 18)
1
6> (-n%n 7 32)
4
7> (-n%n 7 64)
2
In C a "computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type." (C11 6.2.5p9) In other words, it behaves as-if it were two's complement. So the "problem" of assuming two's complement isn't actually a problem at all. (On machines that use signed-magnitude representation for integer types, for example, such as some only recently retired Unisys mainframes, C compilers actually emulate unsigned arithmetic in the generated code.)
While the number of value and padding bits of integer types (other than the fixed-width types) is implemented-defined, that dilemma is precisely what the construct -n % n is intended to deal with, and to do so in a type-safe manner (i.e. no risk of somebody changing the underlying types without changing UFOO_MAX to UBAR_MAX, presuming the macros even exist).
Your alternative construct just assumes "bits" out of thin air, but because the number of padding bits is implementation-defined in C you can only deduce this from UFOO_MAX[1]. In the next C version there should be new macros that specify the number of value bits, but there's still the type-safety problem of the compiler unable to enforce the constraint that a macro (or any other parameter, for that matter) represents a characteristic of the type your primary expression actually uses. This can be problematic even in languages where you can directly query properties of a type.
-n % n is well suited to its purpose. Elegant, even. And not just in the context of C.
[1] EDIT: Or, alternatively, (unsigned type)-1.
let threshold = (0 &- range) % range
Oh come on, it's basically just one extra character.
#ifdef _MSVC
x = ~x + 1; // "Manual" two's complement to avoid warning.
#else
x = -x; // Regular two's complement any good C coder knows
#endifThat being said I am not sure I've ever programmed a one's complement machine.
No it does not. The behavior of -n where n is an unsigned integer is defined by the standard to be the result of subtracting n from 2^(number of bits in the type), independent of the characteristics of the machine.
This is true of both C and C++; and has been true since at least C99 and C++03
Random C++ standard draft from 2005: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n190... Section 5.3.1
>The operand of the unary - operator shall have arithmetic or enumeration type and the result is the negation of its operand. Integral promotion is performed on integral or enumeration operands. The negative of an unsigned quantity is computed by subtracting its value from 2^n, where n is the number of bits in the promoted operand. The type of the result is the type of the promoted operand.
Random C standard draft from 2007: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf Section 6.2.5
>The range of nonnegative values of a signed integer type is a subrange of the corresponding unsigned integer type, and the representation of the same value in each type is the same. A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.
s/ampersand/percent sign/
I can see why you might think this is a good heuristic---don't trust blog authors who don't know the right names for common typographic symbols---but in this case I think you went wrong. Daniel is an excellent computer scientist, with a talent for writing straightforward papers about difficult topics. He's also a non-native English speaker who is usually very gracious about accepting corrections to his normally excellent prose. In this case, it was probably just a typo. It's already been corrected---likely because of a comment on the post. But if you ignore everything that contains small temporary errors like this, you're probably missing out on a lot of otherwise good articles.
https://lemire.me/en/#publications
There's a lot of high-performance machine code knowledge to be gained there.
> When the variable range is a signed integer, then the expression -range % range is zero. In a programming language with only signed integers, like Java, this expression is always zero.
Not because of your intuition on the quotient. E.g. try -8 % 5, -8 % 6, and -8 % 7 and this feeling of perfect sense compared to the languages with unsigned types should melt away.
this gives 4 :(
If 2^N - n happens to be a number that's "full of 1s where there were zeros", then that's what it's supposed to be. I don't understand why you think it "won't compute the expected modulus". That's exactly what it will do.
If N is 32 and n is 5, then -n is 4294967291 and -n % n is 1. It doesn't matter whether that was calculated on a ones complement or twos complement machine.
An example where unsigned short promotes to unsigned int are platforms where sizeof(short) == sizeof(int). E.g. 16 bit systems where short and int is 16 bits, and long is 32: compilers for 8086 and such.
If the promotion goes to int, the subsequent - is safe; there is no way the resulting value can be that problematic most negative int of two's complement.
On two's complement systems, even if the - is signed, if you convert the value back to unsigned short, you will get the two's complement value, as if the calculation was done in the unsigned type all along.
For instance a 16 bit unsigned short value of 65535 (0xFFFF) will go to 65535 of type int, which will go to -65535, which will then map to 1 if converted to unsigned short.