資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究設定最左邊的未設定位
本文旨在尋找一種方法來設定給定數字的最左邊的未設定位。最左邊的未設定位被認為是在最高有效設定位之後出現的第一個未設定位。
問題陳述
給定一個數字 n，任務是設定該數字的二進位制展開中未設定的最左邊的位。所有其他位應保持不變。如果原始數字的所有位都已設定，則返回該數字。
示例
Input: 46 Output: 62
解釋
46 的二進位制展開 = 101110。
最左邊的未設定位是 101110。
設定下劃線位後，我們得到 111110。這是 62 的二進位制展開。
因此答案是 62。
Input: 11 Output: 15
解釋
11 的二進位制展開 = 1011。
最左邊的未設定位是 1011。
更改下劃線位後，我們得到 1111，它是 15 的二進位制展開。
Input: 30 Output: 31
解釋
30 的二進位制展開 = 11110。
最左邊的未設定位是 11110。
設定最左邊的未設定位後，我們得到 11111，它是 31 的二進位制展開。
Input: 7 Output: 7
解釋
7 的二進位制展開 = 111。
由於所有位都已設定，因此沒有最左邊的未設定位。因此，答案保持與原始數字相同。
解決方案方法
檢查所有位是否都已設定。如果是，則返回原始數字作為答案。
使用按位 AND 運算子查詢最新未設定位的位，並更新計數器。
設定對應於計數器的位。
顯示答案。
查詢所有位是否都已設定
這裡的想法是，透過新增一位，如果輸入數字的所有位都已設定，則該輸入數字將成為 2 的完美平方。因此，以下表達式將確定數字的所有位是否都已設定：n & (n + 1) == 0;
讓我們透過一個例子來理解這一點。
令數字為 5。我們需要檢查 5 的所有位是否都已設定。
| n = 3 | n + 1 = 4 | n & (n + 1) |
| 011 | 100 | 000 |
因此，可以安全地得出結論，n 的所有位都已設定，我們按原樣返回該數字。
查詢最左邊的未設定位
如果 AND 操作的輸出不等於零，我們繼續查詢最左邊的未設定位。首先生成一個數字，其位數等於給定整數的位數。最初，新數字的只有最左邊的位被設定。
然後，我們執行一個迴圈，該迴圈從最左邊的 1 位開始，透過對給定數字和新數字執行按位 AND 來搜尋向右移動的第一個 0。當 AND 操作的結果為 0 時，我們返回第一個未設定的最左邊位的位，pos。
設定最左邊的未設定位
生成一個新數字，其中只有對應於 pos 的位被設定。對這個新數字和原始數字執行按位 OR 運算。
演算法
函式 all_bits_set()
計算 n & (n + 1)。
如果結果 == 0，則返回 true。
否則返回 false。
函式 find_leftmost_unset_bit()
初始化 m = 1，pos = 0。
while (n > m)
將 m 左移 1 位
將 m 右移 1 位，使其對應於 n 的最高有效位。
while ((n & m) != 0)
將 m 右移 1 位
pos++
一旦迴圈中斷，我們就從 MSB 獲得了最左邊的未設定位的位。
返回 log2(n) - pos，它是從 LSB 開始的位位置。
函式 set_leftmost_unset_bit()
初始化 k = 1
函式呼叫 find_leftmost_unset_bit()。
k = k << pos
計算 n | k。
更新 n。
函式 main()
初始化 n
函式呼叫 all_bits_set()
函式呼叫 find_leftmost_unset_bit()
函式呼叫 set_leftmost_unset_bit()
顯示 n
示例：程式
這些程式透過將其二進位制展開的最左邊的未設定位修改為 1 來修改輸入數字 n。它使用按位運算子 OR 以及左移和右移運算子以及按位 AND 運算子來實現其目標。
#include <stdio.h>
#include <math.h>
// 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.
int all_bits_set(int n) {
if ((n & (n + 1)) == 0) {
return 1;
}
return 0;
}
// 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;
while ((n & m) != 0) {
m = m >> 1;
pos++;
}
return (int)(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;
*n = *n | k;
}
// main function
int main() {
int n = 46;
printf("Input Number: %d\n", n);
if (all_bits_set(n)) {
printf("%d\n", n);
return 0;
}
set_leftmost_unset_bit(&n);
printf("Number after setting the Leftmost Unset Bit: %d\n", n);
return 0;
}
輸出
Input Number: 46 Number after setting the Leftmost Unset Bit: 62
// 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
public class Main {
// 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.
static boolean allBitsSet(int n) {
return (n & (n + 1)) == 0;
}
// function to find the position of the leftmost unset bit from the LSB.
static int findLeftmostUnsetBit(int n) {
int m = 1, pos = 0;
while (n > m) {
m = m << 1;
}
m = m >> 1;
while ((n & m) != 0) {
m = m >> 1;
pos++;
}
return (int) (Math.log(n) / Math.log(2) - pos);
}
// function to set the leftmost unset bit from the LSB.
static int setLeftmostUnsetBit(int n) {
int k = 1;
int pos = findLeftmostUnsetBit(n);
k = k << pos;
n = n | k;
return n;
}
// main function
public static void main(String[] args) {
int n = 46;
System.out.println("Input Number: " + n);
if (allBitsSet(n)) {
System.out.println(n);
} else {
n = setLeftmostUnsetBit(n);
System.out.println("Number after setting the Leftmost Unset Bit: " + n);
}
}
}
輸出
Input Number: 46 Number after setting the Leftmost Unset Bit: 62
import math
# 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.
def all_bits_set(n):
if (n & (n + 1)) == 0:
return True
return False
# function to find the position of the leftmost unset bit from the LSB.
def find_leftmost_unset_bit(n):
m = 1
pos = 0
while n > m:
m = m << 1
m = m >> 1
while (n & m) != 0:
m = m >> 1
pos += 1
return int(math.log2(n) - pos)
# function to set the leftmost unset bit from the LSB.
def set_leftmost_unset_bit(n):
k = 1
pos = find_leftmost_unset_bit(n)
k = k << pos
n = n | k
return n
# main function
if __name__ == "__main__":
n = 46
print("Input Number:", n)
if all_bits_set(n):
print(n)
else:
n = set_leftmost_unset_bit(n)
print("Number after setting the Leftmost Unset Bit:", n)
輸出
Input Number: 46 Number after setting the Leftmost Unset Bit: 62
時間和空間分析
時間複雜度 - O(log2(n))，因為在函式 find_leftmost_unset_bit() 中，我們可能必須遍歷二進位制展開的所有 log2(n) 位才能找到最左邊的未設定位。
空間複雜度 - O(1)，因為在實現中始終使用常量空間。
結論
本文討論了一種查詢和設定給定數字的最左邊的未設定位的方法。如果數字的所有位都已設定，我們按原樣返回該數字。否則，要設定該位，我們使用按位左移和右移運算子生成新的位模式，以及按位 OR 運算子計算結果。為了更深入地理解，我們詳細解釋瞭解決方案方法的概念、多個示例、使用的演算法、C++ 程式解決方案以及時間和空間複雜度分析。
405 次檢視
