資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告