[LeetCode] 191. Number of 1 Bits - Java

https://leetcode.com/problems/number-of-1-bits/description/

Number of 1 Bits - LeetCode

---

문제

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Note:

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

 

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

 

Constraints:

• The input must be a binary string of length 32.

---

풀이

풀이 과정

주어진 정수 n에서 1인 비트의 개수를 구해야 한다. 

먼저 주어진 수 n과 1을 AND 연산하여 가장 오른쪽 자리가 1인지를 판별한다.

1은 비트로 나타내면 0000 0000 0000 0000 0000 0000 0000 0001 이므로 n의 가장 오른쪽 자리가 1인 경우에만 AND 연산 결과가 1로 반환된다.

만약 1이 반환된다면 정답 카운트를 증가시키고 n을 오른쪽으로 shift 연산한다.
이 때 n이 음수인 경우도 존재하기 때문에 비트를 오른쪽으로 이동시키고 빈자리를 0으로 채우는 >>> 연산을 사용한다

---

최종 코드

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int answer = 0;

        // n이 0이 될 때까지 반복
        while(n != 0){
            // 1과의 AND 연산이 1인 경우 맨 오른쪽 자리가 1이므로 카운트 증가
            if((n & 1) == 1) answer++;
            // 비트를 오른쪽으로 한 칸 이동 후 왼쪽 자리는 0으로 채움
            n >>>= 1;
        }

        return answer;
    }
}

---