숫자를 변환하기 위한 최소 비트 뒤집기

2220. 변환 숫자에 대한 최소 비트 뒤집기

난이도: 쉬움

주제: 비트 조작

숫자 x의 비트 뒤집기는 x의 이진 표현에서 비트를 선택하고 이를 0에서 1 또는 1에서 0으로 뒤집기는 것입니다.

• 예를 들어 forx = 7인 경우 이진 표현은 111이며 임의의 비트(표시되지 않은 선행 0 포함)를 선택하고 뒤집을 수 있습니다. 오른쪽에서 첫 번째 비트를 뒤집어 110을 얻고, 오른쪽에서 두 번째 비트를 뒤집어 101을 얻고, 오른쪽에서 다섯 번째 비트(선행 0)를 뒤집어 10111을 얻을 수 있습니다.

두 개의 정수 시작과 목표가 주어지면 시작을 목표로 변환하기 위한 비트 플립의 최소 횟수를 반환합니다

.

예 1:

• 입력: 시작 = 10, 목표 = 7
• 출력: 3
• 설명: 10과 7의 이진 표현은 각각 1010과 0111입니다. 3단계를 거쳐 10을 7로 변환할 수 있습니다.
  • 오른쪽에서 첫 번째 비트 뒤집기: 1010 -> 1011.
  • 오른쪽에서 세 번째 비트 뒤집기: 1011 -> 1111.
  • 오른쪽에서 네 번째 비트 뒤집기: 1111 -> 0111.
  • 3단계 이내에 10을 7로 변환할 수 없다는 것을 알 수 있습니다. 따라서 3을 반환합니다.

예 2:

• 입력: 시작 = 3, 목표 = 4
• 출력: 3
• 설명: 3과 4의 이진 표현은 각각 011과 100입니다. 3단계를 거쳐 3을 4로 변환할 수 있습니다:
  • 오른쪽에서 첫 번째 비트 뒤집기: 011 -> 010.
  • 오른쪽에서 두 번째 비트 뒤집기: 010 -> 000.
  • 오른쪽에서 세 번째 비트 뒤집기: 000 -> 100.
  • 3단계 이내에 3을 4로 변환할 수 없다는 것을 알 수 있습니다. 따라서 3을 반환합니다.

제약조건:

• 0 <= 시작, 목표 <= 10⁹

힌트:

1. 시작과 목표의 비트 값이 다른 경우 해당 비트를 뒤집어야 합니다.
2. 비트 뒤집기가 필요한 비트를 결정하려면 XOR 연산을 사용하는 것이 좋습니다.

해결책:

시작과 목표 사이의 비트 위치가 얼마나 다른지 확인해야 합니다. 이는 두 숫자가 다른 각 비트 위치에 대해 1을 반환하는 XOR 연산(^)을 사용하여 쉽게 달성할 수 있습니다.

단계:

1. 시작과 목표 사이에 XOR 연산을 수행합니다. 결과는 시작과 목표가 다른 모든 위치에서 1이 있는 숫자가 됩니다.
2. 결과의 이진 표현(예: 해밍 거리)에 1이 몇 개 있는지 계산합니다.
3. 1의 수는 필요한 최소 비트 플립 횟수를 제공합니다.

이 솔루션을 PHP: 2220으로 구현해 보겠습니다. 변환 숫자에 대한 최소 비트 뒤집기

  
  
  설명:



^(XOR) 연산은 시작과 목표의 각 비트를 비교합니다. 비트가 다른 경우 결과의 해당 비트는 1이 됩니다.
그런 다음 결과에서 1의 개수를 세어 서로 다른 비트 수, 즉 필요한 비트 플립 수를 제공합니다.
&1 연산은 마지막 비트가 1인지 확인하고 >>= 1은 숫자를 오른쪽으로 이동하여 다음 비트를 처리합니다.



  
  
  시간 복잡도:



시간 복잡도는 (O(log N))입니다. 여기서 (N)은 시작 또는 목표 중 더 큰 값입니다. 숫자의 각 비트를 확인하기 때문입니다. 최악의 경우 32비트 정수의 모든 비트를 반복합니다(PHP 5.6은 시스템에 따라 32비트 또는 64비트 정수에서 작동하므로).



  
  
  산출:



시작 = 10, 목표 = 7의 경우 출력은 3입니다.
시작 = 3, 목표 = 4의 경우 출력은 3입니다.


연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
        
위 내용은 숫자를 변환하기 위한 최소 비트 뒤집기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!