Python에서 하위 집합의 비트 AND가 2의 거듭제곱인지 확인하십시오.

<시간/>

num이라는 숫자 배열이 있다고 가정합니다. 비트 AND가 2의 거듭제곱인 숫자의 하위 집합이 있는지 확인해야 합니다.

따라서 입력이 nums =[22, 25, 9]와 같으면 출력은 True가 됩니다. 하위 집합 {22, 9}인 이진 형식은 {10110, 1001} 이 두 가지의 AND는 10000 =16입니다. 이는 2의 거듭제곱입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

MAX :=max에 32비트 숫자가 있음을 고려하면 32
solve() 함수를 정의합니다. 시간이 많이 걸립니다
숫자의 크기가 1이면
- nums[0]이 2의 거듭제곱이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
총계:=0
0 ~ MAX - 1 범위의 i에 대해
- 총계 :=총계 OR 2^i
0 ~ MAX - 1 범위의 i에 대해
- ret :=총계
- 0에서 숫자 크기 범위의 j에 대해 다음을 수행합니다.
  - nums[j] AND (2^i)가 0이 아니면
    - ret :=ret AND 숫자[j]
- ret가 2의 거듭제곱이면
  - 참 반환
거짓을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

MAX = 32
def is_2s_pow(v):
   return v and (v & (v - 1)) == 0
def solve(nums):
   if len(nums) == 1:
      return is_2s_pow(nums[0])
      total = 0
   for i in range(0, MAX):
      total = total | (1 << i)
   for i in range(0, MAX):
      ret = total
      for j in range(0, len(nums)):
         if nums[j] & (1 << i):
            ret = ret & nums[j]
      if is_2s_pow(ret):
         return True
   return False
nums = [22, 25, 9]
print(solve(nums))

입력

[22, 25, 9]

출력

True