[알고리즘] 32비트에서 1인 비트를 세기

32비트 unsigned int에서 1인 비트는 몇개인가?

ex) 0011 1000(56) -> 3개

1010 1010(170) -> 4개

 

 

Solution 1 : Shift 하면서, 한비트씩 확인.

너무나도 쉽게 생각할 수 있는 알고리즘이다. Shift한 값을 &연산을 하여 1이면 Count를 추가시키면 될 것이다.

 

Solution 2 : x와 x-1을 And 함. 0이 될 때까지

 

아래는 x(56)을 x-1과 &연산한 과정이다.

1) 0011 1000 & 0011 0111 = 0011 0000

2) 0011 0000 & 0010 1111 = 0010 0000

3) 0010 0000 & 0001 1111 = 0000 0000

 

총 3번의 과정을 거쳐서, 비트가 1인게 3개 있다고 판단할 수 있다.

 

Solution 3: Shift, Merge를 이용한 이상한 방법

 

이 알고리즘은 여기에 굉장히 잘 나와있다.

blog.naver.com/zords/221476995246

[재밌는 아이디어] 비트가 1인 갯수 세기 방법

 

간단하게 정리하자면, 

1. Shift연산을 이용하여 왼쪽 부분과, 오른쪽 부분을 분리한다.

2. 분리된 각각의 값에 Mask를 & 시킨다.

3. & 시킨 각각의 결과를 합친다.

4. 1비트, 2비트, 4비트, 8비트, 16비트 총 5번에 걸쳐서 반반씩 쪼갠걸 더하면 총 Count의 값이 나온다.