ll q;

scanf("%lld", &q);

while (!(q&1)) q>>1;

위와 같은 코드에서 문제가 생깁니다.

while(q%2==0) q/=2;로 수정하면 괜찮습니다.

long long으로 shift 연산을 하면 어떤 일이 일어나는건가요?

저번에도 한번 long long 비트연산때문에 고통받은적이 있었던 것 같은...