จำนวน 0 สูงสุดระหว่าง 1 ติดกันใน Binary Representation ใน C++

โจทย์

ได้รับจำนวน n งานคือหาจำนวน 0 สูงสุดระหว่าง 1 ติดกันใน Binary Representation ของ n คืน -1 ถ้า Binary Representation มี 1 น้อยกว่า 2 ตัว

ตัวอย่าง

ถ้าตัวเลขอินพุตคือ 35 Binary Representation คือ

00100011

ใน Binary Representation ข้างต้น มี 3 ตัว 0 ระหว่าง 1 ติดกัน ดังนั้นคำตอบคือ 3

อัลกอริทึม

ใช้ Bitwise Shift Operator เพื่อแก้ปัญหา ต้องหาตำแหน่งของ 1 ติดกันสองตัวใน Binary Representation และหาความต่างสูงสุดของตำแหน่งเหล่านี้

• ถ้าตัวเลขเป็น 0 หรือเป็น Power of 2 ให้คืน -1
• เริ่มต้นตัวแปร prev ด้วยตำแหน่งของ 1 ตัวแรกจากขวา เก็บตำแหน่งของ 1 ที่เห็นล่าสุด
• ใช้ตัวแปร cur เก็บตำแหน่งของ 1 ตัวถัดไปทันทีหลัง prev
• หาความต่าง cur - prev - 1 จะได้จำนวน 0 ระหว่าง 1 ติดกัน เปรียบเทียบกับค่าสูงสุดก่อนหน้า และอัปเดต prev = cur สำหรับรอบถัดไป
• ใช้ตัวแปร 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