คำชี้แจงปัญหา
ให้ตัวเลข n ภารกิจคือการหาค่า 0 สูงสุดระหว่างสองค่า 1 ทันทีในการแทนค่าเลขฐานสองของ n ที่กำหนด คืนค่า -1 หากการแทนค่าไบนารีมี 1 น้อยกว่าสองตัว
ตัวอย่าง
หากตัวเลขที่ป้อนคือ 35 การแทนค่าไบนารีของมันคือ -
00100011
ในการแทนค่าไบนารีด้านบนมี 3 0 ระหว่างสอง 1 ทันที ดังนั้นคำตอบคือ 3.
อัลกอริทึม
เราสามารถใช้ตัวดำเนินการกะระดับบิตเพื่อแก้ปัญหานี้ได้ เราจำเป็นต้องหาตำแหน่งของเลข 1 สองตัวในการแสดงเลขฐานสองของ n และเพิ่มความแตกต่างของตำแหน่งเหล่านี้ให้มากที่สุด
- หากตัวเลขเป็น 0 หรือกำลัง 2 ให้คืนค่า -1
- กำหนดค่าเริ่มต้นของตัวแปรก่อนหน้าด้วยตำแหน่งแรกสุดจากขวาสุด 1 โดยจะเก็บตำแหน่งของ 1 ที่เห็นก่อนหน้านี้
- ใช้ตัวแปรอื่น cur ซึ่งเก็บตำแหน่งของ 1 ทันทีหลังจากก่อนหน้า
- ความแตกต่างของ ITake ของ cur – ก่อนหน้า – 1 มันจะเป็นจำนวน 0 ระหว่างถึง 1 ทันที และเปรียบเทียบกับค่าสูงสุดก่อนหน้าของ 0 และอัปเดตก่อนหน้าเช่น prev=cur สำหรับการทำซ้ำครั้งต่อไป
- IUse ตัวแปร 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
