[LeetCode] 191. Number of 1 Bits

leet코드 문제를 풀다가 신기한 풀이가 있어서 공유합니다.

🎨 문제

이진수 숫자가 주어지면 1의  개수를 세는 문제이다.

Number of 1 Bits - LeetCode

📘 풀이

풀이 방식은 다양하지만 새롭게 알게된 풀이가 있었다. 바로 비트 연산을 활용하는 것이다. 

 

💡 입력값 n에 n - 1한 값을 AND 연산하면 1이 하나 빠진다.

 

위의 방법을 이용하면 n이 0이 될 때까지 해당 연산을 반복하고 반복 횟수를 리턴하면 1의 개수를 알 수 있다.

📗 코드

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        
        while (n != 0) {
            n &= n - 1;
            count += 1;
        }
        
        return count;
    }
}

📒 예시

입력(n)	n - 1	n & n - 1
1000	0111	0000

입력(n)	n - 1	n & n - 1
1010	1001	1000
1000	0111	0000