naya543   5년 전

다른 사이트에서 문제를 풀다가

shift 연산으로 풀었을 경우 TLE

곱하기 연산으로 풀었을 경우 AC를 받았습니다..

shift 연산보다 곱하기 연산이 더 빠른건가요?

구글링 해봐도 정확하게 모르겠어서 질문 남깁니다.

bupjae   5년 전

다음과 같은 원인일 수 있습니다.

1) 연산자 우선순위: C++ 에서 shift 연산자는 덧셈 연산자보다 우선순위가 낮습니다

2) 음수의 shift: 이 경우는 2^n 으로 곱하고 나누는 것과 다른 결과가 나올 수 있습니다.

 

naya543   5년 전

bupjae   5년 전

11~14번째 줄 반복문이 끝난 뒤에도 여전히 temp = 0 인 상태일 가능성이 있습니다.

그렇게 되면 15번째 줄은 1 << -1 이 되는데, 매우 높은 확률로 원하는 결과가 아닐 겁니다. 

naya543   5년 전

@bupjae

답변감사합니다.

코드에 대해 설명을 드리자면 else 문인 경우는 '홀수'인 경우입니다.

홀수인 경우의 오른쪽 끝 자리는 항상 1이기에 


if (!(num & (1 << temp))) break;

temp가 0인 경우는 없다고 생각이 되는데.. 제 생각이 틀린건가요?

그렇다면 틀렸다고 나와야 하는데 마지막 TC에서 TLE를 받았네요...

bupjae   5년 전

문제와 코드를 읽다 보니까 다른 문제점을 발견했습니다.

   

12번째 줄에서 (1 << temp) 의 결과값은 int 입니다.

num 이 long long 인 것을 볼때,  shift 연산 또한 (1LL << temp) 라고 써서 long long 형으로 맞춰야 올바르게 동작할 것으로 보입니다.

   

마찬가지로, 15번째 줄 또한 shift 연산 및 temp2 또한 long long 이 되어야 할 겁니다.

naya543   5년 전

@bupjae

말씀하신대로 (1LL << temp) 로 바꾸고, temp2 또한 long long 으로 변경하였는데도 TLE 네요..

그래도 (1LL << temp) 를 처음 알게 되었습니다 답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.