Tìm dãy 1 liên tiếp dài nhất trong biểu diễn nhị phân (C#)

Sử dụng toán tử bitwise Left Shift (<<) kết hợp AND (&) để đếm độ dài dãy bit 1 liên tiếp dài nhất trong biểu diễn nhị phân của số nguyên.

Thuật toán (Brian Kernighan's Algorithm biến thể)

int count = 0;
while (n != 0)
{
    n = n & (n << 1);  // Giữ lại chỉ các bit 1 liên tiếp
    count++;
}
// count = độ dài dãy 1 liên tiếp dài nhất

Giải thích

Ví dụ n = 150 (nhị phân: 10010110):

Lần 1: n = 10010110 & 00101100 = 00000100 (4)   count=1
Lần 2: n = 00000100 & 00001000 = 00000000 (0)   count=2
Kết thúc: count = 2 (dãy "11" tại vị trí bit 2-3)

Mã nguồn (có sửa lỗi logic gốc)

using System;

class Demo
{
    // Tìm độ dài dãy 1 liên tiếp dài nhất
    private static int FindLongestConsecutiveOnes(int n)
    {
        int count = 0;
        while (n != 0)
        {
            n = n & (n << 1);  // Sửa: n << 1 (không phải n < 1)
            count++;
        }
        return count;
    }
    
    public static void Main()
    {
        // 150 = 10010110₂ → dãy 1 liên tiếp dài nhất = 2 ("11")
        Console.WriteLine(FindLongestConsecutiveOnes(150));  // 2
        
        // Test thêm
        Console.WriteLine(FindLongestConsecutiveOnes(15));   // 4 (1111)
        Console.WriteLine(FindLongestConsecutiveOnes(7));    // 3 (111)
        Console.WriteLine(FindLongestConsecutiveOnes(0));    // 0
    }
}

Kết quả

2
4
3
0

Lưu ý về code gốc

Code gốc có lỗi: i < 1 (so sánh) thay vì i << 1 (left shift). Đã sửa trong ví dụ trên.

Ứng dụng

• Phân tích pattern bit
• Nén dữ liệu (run-length encoding)
• Kiểm tra tính liên tục của flag bits
• Thuật toán đồ thị (bitmask)

Mở rộng: Vị trí dãy 1 dài nhất

// Trả về (length, startBitPosition)
public static (int Length, int Position) FindLongestOnesWithPosition(int n)
{
    int maxLen = 0, maxPos = -1;
    int curLen = 0, curPos = 0;
    
    for (int i = 0; i < 32; i++)
    {
        if ((n & (1 << i)) != 0)
        {
            if (curLen == 0) curPos = i;
            curLen++;
            if (curLen > maxLen) { maxLen = curLen; maxPos = curPos; }
        }
        else curLen = 0;
    }
    return (maxLen, maxPos);
}