파이썬에서 정수를 0으로 만드는 최소 1비트 연산을 찾는 프로그램

<시간/>

숫자 n이 있다고 가정하고 다음 작업을 여러 번 사용하여 0으로 변환해야 합니다. -

n의 이진 표현에서 가장 오른쪽 비트를 선택합니다.
(i-1)번째 비트가 1로 설정되고 (i-2)~0번째 비트가 0으로 설정되면 n의 이진 표현에서 i번째 비트를 변경합니다.

따라서 마지막으로 n을 0으로 변환하는 데 필요한 최소 연산 수를 찾아야 합니다.

따라서 입력이 n =6과 같으면 초기에 6 ="110"이므로 출력은 4가되고 두 번째 작업으로 "010"으로 변환 한 다음 첫 번째 작업을 사용하여 "011"로 변환 한 다음 "로 변환하십시오. 001" 두 번째 작업을 사용하여 마지막으로 첫 번째 작업을 사용하여 "000"으로 변환합니다.

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

n :=숫자 n의 이진 비트 목록
m:=새 목록
마지막:=0
n의 각 d에 대해 수행
- 마지막이 1과 같으면
  - d:=1-d
- 마지막:=d
- m의 끝에 d 삽입
m:=m
의 요소를 결합하여 이진수 만들기
m을 10진수로 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

def solve(n):
   n=list(map(int,bin(n)[2:]))
   m=[]
   last=0
   for d in n:
      if last==1:
         d=1-d
      last=d
      m.append(d)
   m=''.join(map(str,m))
   return int(m,2)

n = 6
print(solve(n))

입력

"95643", "45963"