duckladydinh's blog

By duckladydinh, history, 9 years ago, In English

Hi everyone.

I am working on 484A — Bits which should be an easy one. Unfortunately, I am facing a very strange thing that I have never seen before. Hope that someone can help me with it.

Below is my code, and the problem is this code gives WA on test 2, line 12th, when the statement a = 0 is after cin >> l >> r, but when I just put the statement a = 0 before cin >> l >> r, it gives WA on test 2, line 11th. However, in both cases, I test on my computer, both code are correct.

#include <bits/stdc++.h>
using namespace std;
#define len(u) (64 - __builtin_clzll(u))

int n;
int64_t l, r, a, u;

int main(){
    cin >> n;
    while(n--){
        cin >> l >> r;
        a = 0;
        while(len(l) == len(r) && r > 0){
            u = 1 << (len(r) - 1);
            l-= u, r-= u, a+= u;
        }
        u = 1 << (len(r) - 1);
        u <<= (u + u - 1 == r && r > 1);
        cout << a+u-1 << "\n";
    }
    return 0;
}

Thank you.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You should not call __builtin_clzll(0), quoting that page:

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

That is, if r = 0 after the loop, result of your program is undefined.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank u very much for that, I thought it would be 64 in that case :)

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      When you see that your program behaves differently on local machine and some other machine (e.g. online judge), it's most probably that you have undefined behavior somewhere. Array out-out-bound, integer overflow in signed types, incorrect calls of functions, incorrect format specifier for scanf/printf are the most popular.