Why does my code read junk bits?

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

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

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.

AishwaryaR
7 лет назад
9

Комментарии (8)

Показать архивные | Написать комментарий?

georgerapeanu

7 лет назад, скрыть # |

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

→ Ответить

veschii_nevstrui

7 лет назад, скрыть # ^ |

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

#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);
	cout.setf(ios::fixed);
	cout.precision(10);

	int n;
	cin >> n;
	cout << (1 << n) << endl << (1 << (n % 32)) << endl;
}

→ Ответить

Naseem17

7 лет назад, скрыть # ^ |

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.

→ Ответить

veschii_nevstrui

7 лет назад, скрыть # ^ |

← Rev. 2 →

I don't know, lol

UP: Did you run the same code as mine?

→ Ответить

Naseem17

7 лет назад, скрыть # ^ |

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?

→ Ответить

mohmahkho

7 лет назад, скрыть # ^ |

+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.

→ Ответить