LeetCode 명상: 역방향 비트

Reverse Bits에 대한 설명은 매우 간단합니다.

주어진 32비트 부호 없는 정수의 역방향 비트.

참고사항도 있습니다:

• Java와 같은 일부 언어에는 부호 없는 정수 유형이 없습니다. 이 경우 입력과 출력 모두 부호 있는 정수 유형으로 제공됩니다. 정수의 내부 바이너리 표현은 부호가 있든 없든 동일하므로 구현에 영향을 주어서는 안 됩니다.

• Java에서 컴파일러는 2의 보수 표기법을 사용하여 부호 있는 정수를 나타냅니다. 따라서 예제 2에서 입력은 부호 있는 정수 -3을 나타내고 출력은 부호 있는 정수 -1073741825를 나타냅니다.

예:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

또는:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

또한 제약 조건에서 입력은 길이가 32인 바이너리 문자열이어야 한다고 명시되어 있습니다.

---

입력이 32비트 정수라는 것을 알고 있으므로 각 비트의 반전된 위치를 쉽게 계산할 수 있습니다. 예를 들어 0번째는 31번째에 해당하고, 1번째는 30번째에 해당합니다.

하지만 우리는 비트 조작을 하고 있습니다. 즉, 각 비트를 하나씩 처리해야 합니다.
따라서 for 루프를 실행하여 이를 수행할 수 있습니다. 매번 인덱스별로 비트를 가장 오른쪽 위치로 이동할 수 있으며 이는 다음과 같습니다.

n >>> idx

비트(0이든 1이든)를 구하는 것은 1을 사용한 AND 연산으로 쉽게 수행할 수 있습니다.
비트가 0이면 0과 1은 0이 됩니다.
1이면 1과 1이 합쳐지면 1이 됩니다.

참고

Note

We can think of ANDing with 1 as the multiplicative identity (for example, $7\cdot 1=7$7⋅1=7 ).

1과 AND를 곱셈 항등식으로 생각할 수 있습니다(예: $7\cdot 1=77\; cdot\; 1\; =\; 7$7⋅1=7 ).

먼저 다음 내용을 알아볼 수 있습니다.

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

그럼 가지고 있는 비트를 반대 위치에 놓아야 합니다. 이를 위해 비트를 왼쪽으로 이동하여 결과를 추가할 수 있습니다.

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

결과를 32비트 정수로 반환해야 합니다. 이를 위해서는 부호 없는 오른쪽 시프트 연산자를 사용하여 트릭을 수행할 수 있습니다.

n >>> idx

최종 솔루션은 다음과 같습니다.

for (let i = 0; i >> i) & 1;

  /* ... */
}

시간과 공간의 복잡성

우리는 입력과 결과가 항상 32비트 정수라는 것을 알고 있으며(그리고 다른 추가 데이터 구조를 사용할 필요가 없음) 루프도 32번 실행합니다. 이는 고정된 숫자이므로 시간과 공간의 복잡성은 모두 $O(1)$O(1) .

---

다음에는 Missing Number에 대해 살펴보겠습니다. 그때까지 즐거운 코딩하세요.

위 내용은 LeetCode 명상: 역방향 비트의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!