[LeetCode] 191. Number of 1 Bits - 문제풀이

Description

주어진 정수의 bit(1)의 개수를 반환하는 문제입니다.

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.

Follow up:

If this function is called many times, how would you optimize it?

Solution 1. bit manipulation

public int hammingWeight(int n) {
    int cnt = 0;
    while(n != 0) {
        cnt = cnt + (n & 1); 
        n = n>>>1;
    }
    return cnt;
}

1(~0000001)과 and연산을 하여 마지막 비트의 1여부를 확인 한 후 오른쪽으로 shift합니다. 모든 비트가 0이될때까지 반복하고 나온 count를 반환해주면 됩니다.

Solution 2. bitCount()

public int hammingWeight2(int n) {
    return Integer.bitCount(n);
}

java Integer클래스의 bitCount API 를 통해 bit수를 반환받을 수 있습니다.

Reference

Number of 1 Bits - LeetCode

LeetCode, Algorithm, String, Hash Table, LinkedList, Depth-First Search, Breadth-First Search, Matrix, TwoPoint, Array, Recusion, 릿코드, 알고리즘, 코딩테스트, 코테, 문제풀이

Binary Tree, Recusion, 전위순회, inorder-traversal

중위순회, inorder-traversal, 후위순회, postorder-traversal,