[Bit Manipulation] 191. Number of 1 Bits - n & (n-1) trick

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

Number of 1 Bits - LeetCode

 

 

32비트 2진수의 입력값에서 1비트의 개수를 구하는 문제

 

제약조건 Constraints:

• The input must be a binary string of length 32. (입력값은 항상 32자리의 이진수이다)

 

- Input: n = 00000000000000000000000000001011
- Output: 3

 

 

 

1. shift + mod 연산

1) 알고리즘

n이 0보다 클 때 까지 2로 나누어준다. 2로 나누었을때 나머지 값이 마지막 bit의 값이다.

mod 결과값을 더해주고 오른쪽으로 1 shift 해준다.

오른쪽으로 1 shift해서 비어진 첫번째 비트는 0으로 채워진다.

 

 

2) 코드구현

    using namespace std;
    class Solution {
    public:
        int hammingWeight(uint32_t n) {
            int result= 0 ;
            while(n){
                result+=n % 2;
                n = n >> 1;
            }
            return result;
        }
    };

 

 

 

2. n & (n -1)

1) 알고리즘

n과 n-1값으로 and 연산을 하고 n의 값이 0보다 클 때 까지의 회차로 1 bit의 개수를 카운트하는 알고리즘이다.

and연산이란 1bit + 1bit 연산했을때만 결과가 1로 나오는 연산이다.

n & (n - 1) 연산을 반복하다보면 n의 값이 0이 되고, n & (n -1) 연산 횟수가 1비트의 개수가 된다.

 

2) 코드구현

    class Solution {
    public:
        int hammingWeight(uint32_t n) {
            int cnt = 0;
            while(n){
                n = n & (n-1); // or n &= (n-1)
                cnt++;
            }
            return cnt;
        }
    };