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

Why does my code read junk bits?
Автор AishwaryaR, история, 5 лет назад, По-английски

I've made a submission to problem 1303D. I get a correct answer when I iterate upto 30 bit positions, but, according to the constraints in the question, I've to iterate upto 60 (n: 1e18). I don't understand why the code reads junk bits (and hence increments variable splits) thus giving a WA.

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

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

" if (n & (1<<it)){"

I think that 1<<it is considered an int, so 1<<(something bigger than 31) overflows and is treaded like a 0, so for it > 31 the condition is always false. Try using 1LL<<it or if((n>>it) & 1)

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You're not quite right. 1 << n is equivalent to 1 << (n % 32), at least on my GCC and CF custom test.

    Source to check
    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      On my GCC and CF custom test, (1 << n) = 0 when n >= 32. I tried all C++ versions and it acted the same. Why is there a difference between us?

      Of course when n can be larger than 30 bits I'll use 1LL << n but I'm just curious.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        I don't know, lol

        UP: Did you run the same code as mine?

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

          Ok I just figured out our GCCs are the same because i wrote 1<<34 and got 0.

          But why is this happening? is this real life?

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

            Wow! At first I was confused. But with a little bit of search I found out that the results differ because of optimization flags used by CodeForces. I mean if you compile this code without any optimization the results should be the same. But the fact is, if optimization causes a change in result, it's a symptom that the programmer has done something wrong. The thing here is that by the standard of c++ : "If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.". Actually it's an undefined behavior, and you can't rely on it.

            → Ответить