数据结构
网络
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 次查看
