백준 17419. 비트가 넘쳐흘러

https://www.acmicpc.net/problem/17419

17419번: 비트가 넘쳐흘러

 

이 문제는 직접 연산하는것 외에 방법을 모르겠어서 찾아 봤다.

주어지는 식은 다음과 같은데 

• K = K-(K&((~K)+1))

K = 10110  이라고 해보자 

 

여기서 우선 가장 안쪽 괄호 ((~K) + 1) 은 2의 보수를 취하는것 이다. 

((~K) + 1)  = 01010

 

이제 기존 k와 and 연산을 해주면 00010 이된다.

 

즉 위 식은 K에서 최하위 1인 bit를 빼주는 연산이라는 얘기다.

따라서 연산 횟수는 K의 1의 갯수가 된다.