프로그래머스 다음 큰 숫자

처음에는 2진수에서 1의 개수를 세며 1씩 더해 맞을때까지 while문을 돌리는거는 비효율적이라고 생각해 패턴을 찾았음.

패턴: 0111 > 1000, 오른쪽부터 봤을 때 1 다음에 나오는 첫 0을 1로 바꾸고 비트를 오른쪽으로 밀어버리는것.

string으로 코드를 만들었는데 통과하지만 효율 테스트에서 걸러짐.

 

뭔가 비트연산으로 나오면 비직관적이라서 생각이 안드는듯 하다

 

정답:

n=0111,0000 이라고 가정

 

bit연산으로

n & -n = 최하위 비트 찾기

0111,0000 & 1001,0000 = 0001,0000

 

n + (n & -n) = 아까 말했던 첫번째 패턴

0111,0000  + 0001,0000 = 1000,0000

 

n ^ (n + (n & -n)) = 원본과 첫번째 패턴과 다른 비트 수

0111,0000  ^ 1000,0000 = 1111,0000

 

n ^ (n + (n & -n))  / (n & -n)여기서 비트를 오른쪽으로 밀어야 하니까, 최하위 비트로 나누어 주면

1111,0000 / 0001,0000 = 0000,1111

 

여기서 첫번째 패턴을 만들때 0이 1이 되었기 때문에 최하위 비트 1, 원래부터 연속되었던 1 3개로 1이 4개가 됨

하지만 연속된 3개중에서 사용해야 할것은 2개이니까  비트 2개를 밀어줘야함

n ^ (n + (n & -n))  / (n & -n) >> 2

0000,1111 >> 2 = 0000,0011

 

이거를 첫번째 패턴이랑 더하면

1000,0000 + 0000,0011 = 1000,0011

 

using System;

class Solution 
{
    public int solution(int n) 
   {
        int answer = 0;
        int upBit = n & -n;
        int mid = n + upBit;
        
        int post = ((n ^ mid) / upBit) >> 2;
        answer = post | mid;
            
        return answer;
    }
}