[Leetcode/C++] 461_Hamming Distance

먼저 문제는 다음과 같습니다.

먼저 저는 두 가지 풀이로 풀어봤습니다.

첫 번째 풀이는 c++의 비트연산자를 이용한 풀이입니다.
풀이 과정은 다음과 같습니다.

입력받은 두 수 x, y의 각각의 비트에서 다른 부분을 찾아야 하므로 ^연산자(XOR)를 이용하여 이 값을 변수 res에 담습니다.

그리고 변수 res를 비트로 나타내었을 때, 1이 나타난 횟수를 변수 cnt에 담았습니다.

전체 코드는 다음과 같습니다.

class Solution {
public:
    int hammingDistance(int x, int y) {
        int res = x ^ y; // res의 비트에는 x y 에서 다른 경우만 1로 되어 있음
        
        int tmp=1, cnt=0;
        // res의 비트 중 1이 몇개 인지 계산하기
        for(int i=1; i<=32; i++){
            if(res & tmp) cnt++;
            if(i==32) break;
            tmp = tmp<<1; // tmp*=2; 와 동일
        }
        return cnt;
    }
};

tmp를 갱신해나가는 마지막에서는 int의 범위를 넘어가게 되므로, if(i==32) break; 문을 이용하여 처리했습니다.


두 번째 풀이는, c++ 의 stl bitset을 이용한 풀이입니다.

놀랐습니다.. 이런 비트 연산에 대한 stl이 있다니

stl을 이용하였어서 문제 풀이 과정에 대한 설명은 따로 없이 바로 코드를 보여드리겠습니다.

class Solution {
public:
    int hammingDistance(int x, int y) {
        bitset<32> bit1(x);
        bitset<32> bit2(y);
        int res=0;
        
        for(int i=0; i<32; i++){
            if(bit1[i]!=bit2[i]) res++;
        }
        return res;
    }
};

bitset이용법은 다음 블로그를 참고해서 이용했습니다.

bitset이용법

좋은 웹페이지 즐겨찾기