数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中二进制表示中两个相邻1之间最大0的个数
问题陈述
给定一个数字n，任务是找到给定n的二进制表示中两个相邻1之间最大的0的个数。如果二进制表示中包含少于两个1，则返回-1。
示例
如果输入数字为35，则其二进制表示为：
00100011
在上面的二进制表示中，两个相邻1之间有3个0。因此答案是3。
算法
我们可以使用按位移位运算符来解决此问题。我们需要找到n的二进制表示中两个相邻1的位置，并最大化这些位置的差值。
- 如果数字为0或2的幂，则返回-1
- 将变量prev初始化为最右边第一个1的位置。它存储先前看到的1的位置。
- 取另一个变量cur，它存储紧随prev之后的1的位置。
- 计算cur – prev – 1的差值，它将是两个相邻1之间的0的个数，并将其与0的先前最大值进行比较，并更新prev，即；对于下一次迭代，prev=cur。
- 使用变量setBit，它扫描n的所有位，并帮助检测当前位是0还是1。使用辅助变量setBit，它扫描n的所有位，并帮助检测当前位是0还是1。
示例
现在让我们看一个例子：
#include <bits/stdc++.h>
using namespace std;
int getMaxZeros(int n) {
if (n == 0 || (n & (n - 1) == 0)) {
return -1;
}
int setBit = 1;
int prev = 0;
int i;
for (i = 1; i < sizeof(int) * 8; ++i) {
++prev;
if ((n & setBit) == setBit) {
setBit = setBit << 1;
break;
}
setBit = setBit << 1;
}
int maxZeros = INT_MIN;
int cur = prev;
for (int j = i + 1; j <= sizeof(int) * 8; ++j) {
++cur;
if ((n & setBit) == setBit) {
if (maxZeros < (cur - prev - 1)) {
maxZeros = cur - prev - 1; prev = cur;
}
}
setBit = setBit << 1;
}
return maxZeros;
}
int main() {
int n = 35;
cout << "Maximum zeros = " << getMaxZeros(n) << endl;
return 0;
}输出
Maximum zeros = 3
更新于：2019-12-31
760 次浏览
广告