[leetcode] 바이너리 - 191번 Number of 1 Bits (Java)

문제링크

Number of 1 Bits - LeetCode

 

 

접근한 방법

• 바이너리

 

---

풀이방법

먼저, signed와 unsigned의 개념을 알아보자.

 

signed - C/C++ 프로그램 언어에서 정수형 변수 중 부호를 갖는 변수를 선언한다.
정수형 중 음수는 2의 보수 체계를 사용하므로 이 키워드에 의해 부호를 사용할 수 있도록 변수 선언할 수 있다. 그러나 정수형의 변수에서 unsigned가 없으면 음수를 사용할 수 있는 부호를 갖는 정수형이 된다. 따라서 프로그램에서는 이 키워드는 많이 사용하지 않는다.

unsigned - C/C++언어에서 사용되는 지정자로 정수형과 같이 사용되어 부호 비트를 제거해 저장 가능한 양수 범위를 두배로 늘이는 역할을 한다.

출처

 

java의 int는 4바이트를 갖는다.

따라서 32비트를 나타낼 수 있는데, signed일 경우 맨 앞자리는 부호 비트이므로 나머지 31비트로만 수를 표현가능하다.

범위를 나타내보면, 아래와 같다.

signed일 경우	- $2^{31}$ ~ $2^{31}$	-2,147,483,648‬ ~ 2,147,483,648
unsigned일 경우	0 ~ $2^{32}$	0 ~ 4,294,967,296

 

answer변수와 mask 변수를 선언하여 정수 n과 mask의 and연산은 32번 수행한다.

반복문을 도는 동안 mask는 왼쪽으로 시프트 이동하여 1의 개수를 카운트할 수 있도록한다.

---

소스코드

package leetcode.binary;

public class Q191_NumberOf1Bits {
    public static int hammingWeight(int n) {
        int answer = 0 ;
        int mask = 1;

        for (int i = 0; i < 32; i++) {
            if((n & mask) != 0){
                answer++;
            }
            mask <<= 1; // mask = mask << 1
        }

        return answer;

    }
    public static void main(String[] args) {
        int n = 11;
        System.out.println(hammingWeight(n));
    }
}