[LeetCode] 191. Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/description/?envType=daily-question&envId=2023-11-29

Number of 1 Bits - LeetCode

leetcode - Number of 1 Bits

문제 유형 : 비트마스킹, 비트연산

문제 난이도 : Easy

 

문제

Write a function that takes the binary representation of 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.

 

부호가 없는 정수의 바이너리 표현상에서의 1의 개수를 부하여라.(해밍 웨이트라고도 알려져있다.)

 

자바와 같은 언어에는 부호가 없는 정수 타입이 없다.

입력은 부호가 있는 정수로 주어질 수 있다. 그러나, 이는 당신의 구현에 영향을 끼치지 않도록 되어있다.

자바에서는 컴파일러가 2의 보수표기를 사용한다. 그러므로 예시 3과 같은 경우, -3으로 입력될 것이다.

 

 

풀이

n & (n-1)연산을 통해서 비트의 가장 오른쪽의 1을 없애는 연산을 할 수 있다. n이 0보다 큰 동안 이를 반복해주면 1의 개수만큼 반복하는 것이다.

이 반복 횟수를 반환하면 된다.

 

 

코드

C++

class Solution {
public:
    int hammingWeight(uint32_t n) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        int cnt = 0;
        while(n != 0) {
            n &= n-1;
            cnt++;
        }
        return cnt;
    }
};