가장 왼쪽의 설정되지 않은 비트를 설정합니다.

이 글은 주어진 숫자의 가장 왼쪽에 설정되지 않은 숫자를 설정하는 방법을 찾는 것을 목표로 합니다. 가장 중요한 설정 비트 다음의 첫 번째 설정되지 않은 비트는 가장 왼쪽의 설정되지 않은 비트로 간주됩니다.

문제 설명

숫자 n이 주어지면 작업은 해당 숫자의 이진 확장에서 설정되지 않은 가장 왼쪽 비트를 1로 설정하는 것입니다. 다른 모든 비트는 변경되지 않은 상태로 유지되어야 합니다. 원래 숫자의 모든 비트가 설정된 경우 숫자가 반환됩니다.

예

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

46의 이진 확장 = 101110.

가장 왼쪽의 설정되지 않은 비트는 101110입니다.

밑줄 그어진 비트를 설정하면 111110이 됩니다. 이는 62의 이진 확장입니다.

따라서 답은 62입니다.

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

11의 이진 확장 = 1011.

가장 왼쪽의 설정되지 않은 비트는 1011입니다.

밑줄 친 비트를 변경하면 15의 이진 확장인 1111이 됩니다.

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

30의 이진 확장 = 11110.

가장 왼쪽의 설정되지 않은 비트는 11110입니다.

가장 왼쪽의 설정되지 않은 비트를 설정하면 31의 이진 확장인 11111을 얻습니다.

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

7의 이진 확장 = 111.

모든 비트가 설정되어 있으므로 가장 왼쪽의 설정되지 않은 비트가 없습니다. 따라서 답은 원래 숫자와 동일하게 유지됩니다.

해결 방법

• 모든 비트가 설정되었는지 확인하세요. 그렇다면 원래 번호를 답으로 반환하십시오.

• 비트 AND 연산자를 사용하여 가장 최근에 설정되지 않은 비트의 위치를 ​​찾고 카운터를 업데이트합니다.

• 카운터에 해당하는 비트를 설정하세요.

• 답변을 보여주세요.

모든 비트가 설정되었는지 확인

여기서 아이디어는 1비트를 추가하면 모든 비트가 설정되면 입력 숫자가 2의 완전제곱이 된다는 것입니다. 따라서 다음 표현식은 숫자의 모든 비트가 설정되었는지 여부를 결정합니다. (n + 1) == 0;

예를 통해 이해해 봅시다.

숫자를 5로 둡니다. 5의 비트가 모두 설정되었는지 확인해야 합니다.

의 중국어 번역은 입니다.

n = 3	n + 1 = 4	n & (n + 1)
011
011	100	000

Thus it is safe to conclude that all the bits of n are already set and we return the number as it is.

找到最左边未设置的位

如果AND操作的输出不等于零，则继续查找最左边未设置的位。首先生成一个位数与给定整数相等的数字。新数字的最左边位最初设置为1。

然后，我们运行一个循环，从最左边的1位开始，向右搜索第一个0，通过对给定数字和新数字进行位与运算来实现。当位与运算的结果为0时，我们返回第一个未设置的最左边位的位置pos。

To Set the Leftmost Unset Bit

Generate a new number in which only the bit corresponding to pos is set. Perform bitwise OR operation between this new number and the original number.

Algorithm

的中文翻译为：

算法

Function all_bits_set()

• 计算 n & (n + 1)。

• If result == 0, return true.

• 否则返回 false。

Function find_leftmost_unset_bit()

• Initialize m = 1, pos = 0.

• while (n > m)

• 左移 m 1 位

• 将 m 右移 1 位，以使其对应于 n 的最高有效位。

• while ((n & m) != 0)

• 将 m 右移 1 位

• pos++

• 一旦循环中断，我们就可以得到最高有效位（MSB）中最左边未设置的位的位置。

• 返回 log2(n) - pos，即从最低有效位开始的位位置。

函数 set_leftmost_unset_bit()

• 初始化 k = 1

• Function Call find_leftmost_unset_bit().

• k = k

• Compute n | k.

• Update n.

Function main()

• 初始化 n

• Function Call all_bits_set()

• 函数调用 find_leftmost_unset_bit()

• 调用函数set_leftmost_unset_bit()

• 显示 n

示例：C++程序

这个程序通过将输入数字 n 的二进制展开中最左边未设置的位设置为 1 来修改它。它使用位运算符 OR，左移和右移运算符以及位与运算符来实现其目标。

// A C++ program to set the left most unset bit of a number. If all the bits of the given number are already set, it returns the number as it is.
#include <iostream>
#include <cmath>
using namespace std;
// function to check if all bits of the given number are already set
// if all bits of n are set, n + 1 will be a power of 2.
bool all_bits_set(int n){
   if ((n & (n + 1)) == 0)    {
      return true;
   }
   return false;
}

// function to find the position of the leftmost unset bit from the LSB.
int find_leftmost_unset_bit(int n){
   int m = 1, pos = 0;
   while (n > m){
      m = m << 1;
   }
   m = m >> 1; // to make the number of digits in m equal to number of digits in n
   
   // the following loop executes till the first zero is encountered, starting from the msb
   while ((n & m) != 0){
      m = m >> 1;
      pos++;
   }
   
   // since pos is the position of the unset bit from the MSB we return log2(n) - pos which is the location of the leftmost unset bit from the LSB.
   return log2(n) - pos;
}

// function to set the leftmost unset bit from the LSB.
void set_leftmost_unset_bit(int &n){
   int k = 1;
   int pos = find_leftmost_unset_bit(n);
   k = k << (pos); // left shift k by pos
   n = n | k; // to set the leftmost unset bit
}

// main function
int main(){
   int n = 46;
   cout << "Input Number: "<< n << endl;
   if (all_bits_set(n))    {
      cout << n << endl;
      return 0;
   }
   set_leftmost_unset_bit(n);
   cout << "Number after setting the Leftmost Unset Bit: " << n << endl; // display the updated number
   return 0;
}

输出

Input Number: 46
Number after setting the Leftmost Unset Bit: 62

时间和空间分析

时间复杂度：O(log2(n))，因为在函数find_leftmost_unset_bit()中，我们可能需要遍历二进制展开式的所有log2(n)位数来找到最左边的未设置位。

Space Complexity: O(1), as constant space is always used in the implementation.

Conclusion

本文讨论了一种寻找并设置给定数字最左边未设置位的方法。如果数字的所有位已经设置，我们将返回该数字。否则，为了设置该位，我们使用位左移和右移运算符生成一个新的位模式，并使用位或运算符计算结果。解决方案的概念、多个示例、使用的算法、C++程序解决方案以及时间和空间复杂度分析都被详细解释，以便更深入地理解。

위 내용은 가장 왼쪽의 설정되지 않은 비트를 설정합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!