AishwaryaR's blog

Why does my code read junk bits?
By AishwaryaR, history, 5 years ago, In English

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.

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

Comments Comments (8)
| Write comment?
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

" 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)

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

    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
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        I don't know, lol

        UP: Did you run the same code as mine?

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

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +16 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +16 Vote: I do not like it

              Thanks a lot. I can sleep peacefully now.

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

                Thank you all for the useful inputs :)

                → Reply