Lemires Nearly Divisionless Modulo Trick-CodePudding

In https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/, Lemire uses -s % s to compute something which according to the paper is supposed to be 2^L % s. According to https://shufflesharding.com/posts/dissecting-lemire this should be equivalent, but I'm getting different results. A 32-bit example:

#include <iostream>

int main() {
  uint64_t s = 1440000000;
  uint64_t k1 = (1ULL << 32ULL) % s;
  uint64_t k2 = (-s) % s;
  std::cout << k1 << std::endl;
  std::cout << k2 << std::endl;
}

Output:

./main
1414967296
109551616

The results aren't matching. What am I missing?

CodePudding user response：

Unary negation on integers operates on every bit (two's complement and all that).

So if you want to simulate 32 bit operations using uint64_t variables, you need to cast the value to 32 bits for that step:

#include <iostream>

int main() {
  uint64_t s = 1440000000;
  uint64_t k1 = (1ULL << 32ULL) % s;
  uint64_t k2 = (-uint32_t(s)) % s;
  std::cout << k1 << std::endl;
  std::cout << k2 << std::endl;
}

Which leads to the expected result:

Program returned: 0
Program stdout
1414967296
1414967296

See on godbolt