z4120's blog

By z4120, 3 years ago, In English

Note: Depends on your coding convention, you may not encounter this bug at all.

I have had a bug in a code similar to this:

void process(long long x) { /* ... */ }
for (auto i = a.size(); i-->0; ) {
    for (auto j = b.size(); j-->0; ) {
        process(i - j);

Can you see the bug?

Both i and j are unsigned, therefore the result will be computed modulo 2^32 or 2^64, depends on the computer architecture. However, because process function takes a long long as input, the input is converted to long long. On 64-bit machines, the result ends up being correct, but on 32-bit machine, if i - j == -1 then the received x value is 2^32-1.

In this particular case, there's no undefined behavior, so turning on -ftrapv -fsanitize=undefined -D_GLIBCXX_DEBUG etc. does not help. But compiling the code as 32-bit, enabling -Wsign-compare, or never using unsigned integer types would work.

How to compile for 32-bit machine with 64-bit compiler?

Add the -m32 compiler flag. (Note that if your compiler fails with some message about link failed, you may need to install 32-bit libraries. The instruction is dependent on your operating system — see 1 2)

Another use of 32-bit compiling: Benchmark with Codeforces speed.

Because Codeforces runs your program in 32-bit, benchmarking in 64-bit mode may not reflect the performance on Codeforces server.

In particular, 64-bit integer multiplication and division on 32-bit machines are much slower on 32-bit machines than on 64-bit machines, so replacing a 64-bit integer division with a 32-bit one may make the program significantly faster on Codeforces, but the performance is almost the same on a 64-bit machine.

  • Vote: I like it
  • +27
  • Vote: I do not like it