Блог пользователя duckladydinh

Автор duckladydinh, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      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.