이진수의 마지막 n개의 비트가 모두 켜져있는지 확인하는 방법

SW Expert Academy

SW Expert Academy

 

 

정수 m의 마지막 n개의 비트가 모두 1인지 확인하는 문제

 

m이 $10^{8}$이고 테스트 케이스는 10000개이고 제한시간 2초라 단순하게 확인하면 시간초과날 것 같다

 

가장 쉬운 방법은 0부터 n-1까지 순회해서 각 비트가 1인지 검사하는 것

 

(1 << i) & m == 1이면 m의 i번째 비트가 1인 것이고 0이면 i번째 비트가 0인 것이다.

 

T = int(input())

for test_case in range(1, T + 1):
    
    n,m = map(int,input().split())
    
    no = False
    
    for i in range(n):
        
        if (1 << i) & m == 0:
            
            no = True
            break
    
    if no:
        
        print(f'#{test_case} OFF')
    
    else:
        
        print(f'#{test_case} ON')

 

 

다른 방법으로 정수 m을 $2^{n}$으로 나눈 나머지가, $2^{n}-1$인지 검사하면 된다.

 

정수 m은 켜져 있는 비트에 대해 2의 거듭제곱의 합으로 나타낼 수 있다.

 

예를 들어 10 = 1010(2) 이므로, $10 = 2^{3} + 2$

 

따라서, 어떤 정수 m이 마지막 n개의 비트가 모두 1이고, 그 상위 비트는 1이든 0이든 상관 없이...

 

$$m = A + 2^{n-1} + 2^{n-2} + ... + 2^{2} + 2^{1} + 2^{0}$$

 

우변을 $2^{n}$으로 나눈다면, $2^{n}$ 이상의 합 A부분은 $2^{n} * B$로 나타낼 수 있다.

 

즉 A는 $2^{n}$으로 나눈 나머지가 0이므로 m을 $2^{n}$으로 나눈 나머지는,

 

$$2^{n-1} + 2^{n-2} + ... + 2 + 1 = 2^{n} - 1$$

 

T = int(input())

for test_case in range(1, T + 1):
    
    n,m = map(int,input().split())

    if  m % (2**n)== 2**n-1:
        
        print(f'#{test_case} ON')
    
    else:
        
        print(f'#{test_case} OFF')