โปรแกรมหาลำดับ 1 ติดต่อกันที่ยาวที่สุดในรูปแบบไบนารีของตัวเลขใน C++

สมมติว่าเรามีตัวเลข n เราต้องหาความยาวของลำดับ 1 ติดต่อกันที่ยาวที่สุดในตัวแทนแบบไบนารีของมัน

เช่น หากอินพุตคือ n = 312 ผลลัพธ์จะเป็น 3 เนื่องจาก 312 ในไบนารีคือ 100111000 ซึ่งมี 1 ติดต่อกัน 3 ตัว

ขั้นตอนการแก้ปัญหา

• กำหนด ret = 0, len = 0
• วนลูป i จาก 0 ถึง 31 (สำหรับ integer 32-bit):
  • ถ้า bit ที่ i เป็น 1: เพิ่ม len
  • ถ้า bit ที่ i เป็น 0: รีเซ็ต len = 0
  • อัปเดต ret = max(ret, len)
• คืนค่า ret

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(int n) {
        int ret = 0;
        int len = 0;
        for (int i = 0; i < 32; i++) {
            if ((n >> i) & 1) {
                len++;
            } else {
                len = 0;
            }
            ret = max(ret, len);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.solve(312);
}

อินพุต

312

เอาต์พุต

3