숫자의 첫 번째 숫자와 마지막 숫자 전환
- PHPz앞으로
- 2023-08-27 17:57:071066검색
다음 문서에서는 비트 연산자를 사용하여 첫 번째 비트와 마지막 비트를 전환하여 숫자를 수정하는 데 사용되는 방법에 대해 자세히 설명합니다. 비트 연산자는 이진수의 개별 비트를 조작하는 데 사용할 수 있는 연산자입니다. 또는 비트 패턴.
문제 설명
주어진 숫자 n에 대해 새 숫자의 이진 확장의 첫 번째 비트와 마지막 비트가 반전되도록 숫자를 수정합니다. 즉, 원래 비트가 1이면 반전된 비트는 0이어야 하고 그 반대의 경우도 마찬가지입니다. 첫 번째와 마지막 비트는 변경하지 않고 그대로 두어야 합니다.
예
으아악 으아악Explanation
의 중국어 번역은Explanation
입니다.13의 이진 전개는 1101입니다.
첫 번째와 마지막 비트를 전환하면 확장자는 0100이 되며 이는 4와 같습니다.
따라서 출력 결과는 4입니다.
으아악 으아악Explanation
의 중국어 번역은Explanation
입니다.27의 이진 전개는 11011입니다.
첫 번째 비트와 마지막 비트를 전환하면 확장자는 01010이 되며 이는 10과 같습니다.
따라서 출력은 10입니다.
으아악 으아악Explanation
의 중국어 번역은Explanation
입니다.113의 이진 전개는 1110001입니다.
첫 번째 비트와 마지막 비트를 전환하면 확장은 48과 동일한 0110000이 됩니다.
따라서 출력은 48입니다.
솔루션 접근 방식
이 접근 방식은 비트 XOR 및 왼쪽 시프트 연산자를 사용합니다. 두 피연산자의 해당 비트가 다른 경우 비트 XOR 연산자는 1로 평가되고, 그렇지 않으면 0으로 평가됩니다. 비트 XOR 연산자의 토글 기능을 사용합니다. 예를 들어, 숫자의 첫 번째 비트 n이 1이면 n ^ 1은 숫자의 첫 번째 비트를 0으로 만듭니다. 또한 숫자의 첫 번째 비트가 0으로 설정되면 n ^ 연산이 수행됩니다. 1이 1로 변경됩니다.
숫자 n의 첫 번째 숫자를 뒤집으려면 n^1을 계산합니다. XOR 연산을 수행하여 n의 최하위 비트 또는 첫 번째 비트를 1로 반전합니다.
마지막 숫자를 뒤집기 위해 마지막 숫자만 설정된 숫자 k를 생성합니다. 마지막 비트의 위치 r은 log2(n)과 같습니다. 이는 n의 이진 확장에 log2(n) 비트가 사용되기 때문입니다.
이 접근 방식을 구현하기 위해 다음 단계가 수행됩니다 −
n = 1이면 0을 표시하고 반환합니다.
1과 n을 XOR하여 숫자의 첫 번째 비트를 전환합니다.
n을 1번째 숫자입니다.
답변을 표시하세요.
드라이 러닝
먼저 비트 XOR(^) 연산자의 작동 방식을 이해해 보겠습니다.
| 입력 | 플래그 | 입력 ^ 플래그 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
플래그의 값이 1일 경우 입력값이 반전되는 것을 확인할 수 있습니다.
숫자 57을 생각해 보세요. 57의 이진 확장은 111001입니다.
| 1 | 1 | 1 | 0 | 0 | 1 |
새로운 숫자 1을 생각해 보세요.
| 0 | 0 | 0 | 0 | 0 | 1 |
최하위 또는 가장 왼쪽 비트를 전환하려면 57^1을 수행하면 결과는
| 1 | 1 | 1 | 0 | 0 | 0 |
111000이라는 숫자가 생성됩니다.
이제 마지막 숫자를 전환하기 위해 첫 번째 숫자 대신 마지막 숫자가 설정되도록 숫자 1을 수정합니다. 이를 위해서는 1을 log2(n)자리만큼 왼쪽으로 이동해야 하며, 이 경우에는 log2(57), 즉 5를 이동해야 합니다. 이 작업을 수행하면 다음을 얻습니다.
| 1 | 0 | 0 | 0 | 0 | 0 |
이제 XOR 계산이 우리에게 제공됩니다.
| 0 | 1 | 1 | 0 | 0 | 0 |
生成了数字01100，等于24。将其与原始数字57的二进制展开进行比较，可以观察到最终答案中的第一位和最后一位已经被切换。
因此，答案是24。
算法
函数 toggle_first_bit()
Compute n ^ 1
更新 n
函数 toggle_last_bit()
初始化 r = log2(n)
初始化 k = 1
计算 n ^ k
更新 n
Function main()
初始化 n
如果 (n == 1)
return 0;
Function call toggle_first_bit().
调用函数 toggle_last_bit()。
显示 n.
示例：C++程序
This program modifies an input number n by toggling the first and the last bit of its binary expansion. It employs bitwise operator XOR and left shift operator to achieve its goal.
// This C++ program toggles the first and the last bit of a number
#include <iostream>
#include <cmath>
using namespace std;
// this function flips the last bit of the number
// it uses the concept that a log(n) bits are used in the binary expansion of a number n
void toggle_last_bit(int& n){
int r = log2(n); // value of r indicates the count of last bit of n
int k; // generate a number with log(n) where only the last bit is 1 using the left shift operator
k = 1 << r;
n = n ^ k; // toggle the last bit of n by computing n XOR k
}
// this function flips the first bit of the number by computing n XOR 1
void toggle_first_bit(int& n){
n = n ^ 1;
}
int main(){
int n = 113;
cout << "input number = 113" << endl;
if(n == 1){
cout << "0";
return 0;
}
toggle_first_bit(n); // function call to toggle first bit
toggle_last_bit(n); // function call to toggle last bit
cout << "Number after Toggle First and Last Bits of a Number: "<<n;
return 0;
}
输出
input number = 113 Number after Toggle First and Last Bits of a Number: 48
Time and Space Analysis
时间复杂度 - O(1)，因为该算法始终在常数时间内工作，与输入数字无关。
空间复杂度 - O(1)，因为在实现中没有使用辅助空间。
Conclusion
本文讨论了一种切换数字的第一个和最后一个位的方法。为了实现这一点，我们使用了位左移运算符来生成新的位模式，使用位异或运算符来计算结果。为了更深入地理解，详细解释了方法的概念、示例的演示、使用的算法、C++程序解决方案以及时间和空间复杂度分析。
위 내용은 숫자의 첫 번째 숫자와 마지막 숫자 전환의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!