Chương trình C# đếm số bit 1 (set bits) trong số nguyên

Đếm số bit có giá trị 1 trong biểu diễn nhị phân của số nguyên (Hamming weight / Population count). Ví dụ: 11 (thập phân) = 1011 (nhị phân) → 3 bit 1.

Thuật toán Brian Kernighan (hiệu quả)

Lặp: n = n & (n - 1) xóa bit 1 thấp nhất mỗi lần. Số lần lặp = số bit 1.

int count = 0;
while (n != 0) {
    n &= (n - 1); // Xóa bit 1 cuối cùng
    count++;
}

Mã nguồn (cách bitwise cơ bản)

using System;

public class Demo {
    public static void Main() {
        int num = 11; // 1011 nhị phân
        int count = 0;
        
        while (num > 0) {
            count += num & 1; // Kiểm tra bit thấp nhất (LSB)
            num >>= 1;        // Dịch phải 1 bit
        }
        
        Console.WriteLine("Tổng bit 1: " + count);
    }
}

Kết quả

Tổng bit 1: 3

Cách hiện đại (.NET Core 3.0+ / .NET 5+)

// BitOperations.PopCount - tối ưu phần cứng (CPU instruction POPCNT)
using System.Numerics;

int count = BitOperations.PopCount((uint)num);
// Hoặc cho long
long count = BitOperations.PopCount((ulong)num);

So sánh

Lưu ý

• Code gốc dùng num & 1 và num >>= 1 — đúng nhưng lặp cố định 31 lần cho int dương.
• Với số âm (biểu diễn bù 2), dịch phải >>= là arithmetic shift (giữ bit dấu) — có thể lặp vô hạn. Dùng uint hoặc n &= n-1.
• BitOperations.PopCount cần System.Numerics (.NET Core 3.0+).