문제


필요 지식

  1. 가우스 공식
    • 1부터 a까지 합은 (a/2)*(a+1)로 생각할 수 있다.
    • a와 1을 더한 수가 a/2개 만큼 있기 때문이다.
  2. (추가) 비트 연산자
    • 기호를 ()로 감싸서 표현 ( 마이너스를 (-)로 표현)
    • (-) = (~) - 1 : 마이너스 한 수는 본래 수의 비트를 flip한 수보다 1이 적다.
    • ~707 = -708

해결 방법

  1. a가 b보다 더 클 때, 둘을 바꾸어야 한다. 그때 XOR연산자 사용가능하다. 
    • temp = a ^ b  : 거름망 - a^b^b하면 b두개를 0으로 만들어 버리고 a만 살게 하고, b^a^a하면 a두개를 0으로 만들어 버리고(무력화시키고) b만 살게 할 수 있다. 
    • b = b ^ temp : b^b^a와 같다. 즉 a를 살리겠다는 것.
    • a = b ^ temp : a^a^b와 같다. b를 살려 a에 저장할 수 있다.이때 b는 전 줄을 거친 b로 생각(본래 a 의 값이 b에 저장됨)
    • 이 과정에서 temp라는 변수를 따로 만들고 하지 않아도 된다.
    • a ^= b ^= a ^= b 하면 a가 마치 temp의 역할을 하게 되기 때문이다.
  2. a와 b사이의 수의 합을 구하는 것을 1부터 b까지 더한 것에서 1부터 a-1까지 더한 것을 빼는 것으로 생각한다.
    • b(b+1)/2 - a(a-1)/2
    • 합치면, (b+a)(b-a+1)/2


코드

#include <string>
#include <vector>
using namespace std;
long long solution(int a, int b) {
long long answer = 0;
if (a > b) a ^= b ^= a ^= b;
answer = (long long)b * -~b / 2 - (long long)a * ~-a / 2;
return answer;
}
//(b(b+1)/2 - a(a-1)/2) 1부터 b까지 더한 것에서 1부터 a-1까지 더한 것을 뺌
// 합친다면, (b+a)(abs(b-a)+1)/2로 한 줄에 끝낼 수 있음
view raw programmer_lv1_두 정수 사이의 합_bit.cpp hosted with ❤ by GitHub