5.4 다음숫자

문제 

양의 정수가 하나 주어졌다. 이 숫자를 2진수로 표기했을때 1비트의 개수가 같은 숫자중에서 주어진 수보다 크지만 가장 작은 수와, 작지만 가장 큰 수를 구하여라 .

 

해결법

이 문제는 두가지 방식으로 풀 수 있다. 원리는 같지만 비트조작으로 하는지, 수학적으로 해결하는지의 차이이다.

우선 비트조작으로 해결하는 것을 살펴보자 

 

- 비트조작으로 다음수 구하기 

주어진 수보다 크지만 가장 작은수는 1의 갯수가 같은 다음 수를 의미할 것이다. 

그러기 위해서는 0수열로 끝나는 수열이 아닌것 ( 다음에 1수열이 나오는 수열) 중에서 맨 오른쪽 0비트를 1로 뒤집고 , 뒤집은 수 보다 오른쪽에 있는 0과 1을 재정렬해서 0은 전부 왼쪽에 1은 전부 오른쪽에 오도록 하면 가장 작은 수가 될 것이다.

 

11011001111100이라는 수가 있다고 가정했을때 

0수열로 끝나는 수열이 아닌 0수열 중에서 가장 오른쪽 0비트는 7번째 수이다.

1	1	0	1	1	0	0	1	1	1	1	1	0	0
13	12	11	10	9	8	7	6	5	4	3	2	1	0

이 위치를 p라고 하자 

그리고 p를 기준으로 오른쪽에 있는 0과 1의 갯수를 각각 c0와 c1으로 정의 해보자 

그러면, p = 7 , c0 = 2  , c1 = 5 가 될 것이다.

위의 정의에 따라 세가지 단계를 거치면 다음 수를 구할 수 있을 것이다.

1단계  : p위치에 있는 0을 1로 뒤집는다. 

1	1	0	1	1	0	1	1	1	1	1	1	0	0
13	12	11	10	9	8	7	6	5	4	3	2	1	0

2단계 : p의 오른쪽에 있는 비트들을 0으로 만든다.

1	1	0	1	1	0	0	0	0	0	0	0	0	0
13	12	11	10	9	8	7	6	5	4	3	2	1	0

3단계 : c1 -1 개의 1을 오른쪽부터 체워넣는다. 

1	1	0	1	1	0	1	0	0	0	1	1	1	1
13	12	11	10	9	8	7	6	5	4	3	2	1	0

 

1단계는 간단하다 

n |= 1 << p

를 통해  해결할 수있다.

 

2단계는 

하위비트 p개를 제외한 모든 위치가 1로 세팅된 마스크가 필요하고, 그 마스크와 &연산을 통해 하위 비트를 모두 0으로 만들 수 있다.

n &= ~((1 << p ) -1)

 

3단계는 

오른쪽에 c1-1 개의 1을 체워넣기 위해서는 c1 -1 개의 1을 가진 숫자와 | 연산을 통해 해결 할 수 있다.

n |= (1 << (c1 -1) ) -1

 

- 비트조작으로 이전수 구하기 

다음수 구하기를 반대로 하면 해결할 수 있다. 

1	0	0	1	1	1	1	0	0	0	0	0	1	1
13	12	11	10	9	8	7	6	5	4	3	2	1	0

1단계 : 1수열로 끝나지 않으면서 (뒤에 0수열이 있는) 맨 오른쪽에 위치한 1비트를 0으로 바꾼다. 이 위치는 p

1	0	0	1	1	1	0	0	0	0	0	0	1	1
13	12	11	10	9	8	7	6	5	4	3	2	1	0

2단계 : p오른쪽에 있는 모든 비트를 0으로 만든다. 

1	0	0	1	1	1	0	0	0	0	0	0	0	0
13	12	11	10	9	8	7	6	5	4	3	2	1	0

3단계 : p바로 오른쪽에 (c1 +1)개의 1을 체워 넣는다. 

1	0	0	1	1	1	0	1	1	1	0	0	0	0
13	12	11	10	9	8	7	6	5	4	3	2	1	0

 

1단계와 2단계는 동시에 할 수 있다.

모든 비트가 1로 체워진 수에서 왼쪽으로 p+1만큼 쉬프트 하면 p 위치까지 비트는 모두 0이다. 이상태에서 &연산을 함으로써 p부터 0까지의 비트를 모두 0으로 바꿀 수 있다.

n &= ~0 << (p+1) 

 

3단계는 

c1+1 개의 1을 가지는 수를 만들고 그 수를 오른쪽으로 c0-1만큼 쉬프트 한 값을 |연산을 해서 해결할 수있다.

n |= ( (1 << (c1 +1) ) -1 ) << (c0 -1)

 

def getNext(n):
    c = n
    c0, c1 = 0, 0
    while c&1 ==0 and c !=0 :
        c0 +=1
        c >>=1
    while c&1 ==1 :
        c1 +=1
        c >>1
    if c0+c1 ==31 or c0+c1 ==0 :
        return -1
    p = c0+c1
    n |= 1 << p
    n &= ~((1 <<p)-1)
    n |= (1<<(c1-1))-1
    return n

def getPrev(n):
    c = n
    c0, c1 = 0, 0
    while c&1 ==1 :
        c1 +=1
        c >>=1
    if c ==0 :
        return -1
    while c&1 ==0 && c != 0 :
        c0 +=1
        c >>=1
    p = c0+ c1
    n &= ~0 << (p+1)
    mask = (1<<(c1+1)-1)
    n |= mask << (c0-1)
    return n

 

-수학적 해법으로 다음수 구하기

원리는 같다. 

1단계 : p번째 비트를 1로 바꾼다.

2단계 : p번째를 기준을오 오른쪽에 있는 모든 비트를 0으로 만든다.

3단계 : 오른쪽에 c1 -1 개의 비트를 1로 체워 넣는다 

 

1단계와 2단계를 빠르게 할 수 있는 방법이 있다. 

맨 오른쪽에 있는 0을 1로 체워 넣고 +1을 하게되면 연속된 1비트들이 전부 0으로 바뀌면서 마지막에 p번째 비트가 1로 바뀔 것이다.

n += 2^c0 -1 

n += 1

 

3단계를 수학적으로 해결하면 

n += 2^(c1-1) -1 

즉, 이 세단계를 수식으로 보면 n += 2^c0 + (2^(c-1)-1) -1  이다.

이 방법은 비트 조작 연산을 첨가하면 코딩하기가 간편하다는 장점이 있다. 

return n+(1<<c0)  + (1 << (c1-1) ) -1

 

-수학적 해법으로 이전수 구하기 

마찬가지로 원리는 같다. 

1단계 : p번째 비트를 0으로 바꾼다.

2단계 : p번째를 기준으로 오른쪽에 있는 모든 비트를 1로 만든다.

3단계 : (c0-1) 번째 비트부터 0번째까지 모든 비트를 0으로 만든다. 

 

이번에도 1단계와 2단계를 빠르게 할 수 있는 방법이 있다. 

가장 오른쪽에 있는 1을 0으로 바꾸고 -1을 하게되면 p는 0이되고 p보다 오른쪽에 있는 모든 수는 1로 만들어진다. 

n -= 2^c1 -1

n -=1

 

3단계를 수학적으로 해결하면 

n -= 2^(c0-1) -1 

즉, 이 세단계를 수식으로 보면 n = n - 2^c1 -2^(c0-1) -1

비트조작 연산을 첨가하면 return n - (1 << c1) - (1 << (c0-1)) -1 으로 표현 할 수 있다. 

def getNext(n):
    c = n
    c0, c1 = 0, 0
    while c&1 ==0 and c !=0 :
        c0 +=1
        c >>=1
    while c&1 ==1 :
        c1 +=1
        c >>1
    if c0+c1 ==31 or c0+c1 ==0 :
        return -1

    p = c0+c1
    return n + (1 << c0) + (1 << (c1-1)) -1


def getPrev(n):
    c = n
    c0, c1 = 0, 0
    while c&1 ==1 :
        c1 +=1
        c >>=1
    if c ==0 :
        return -1
    while c&1 ==0 && c != 0 :
        c0 +=1
        c >>=1
    
    return n - (1 << c1) - (1 << (c0-1)) -1