Chương trình C/C++ đếm bit set trong số nguyên

Ở đây chúng ta sẽ xem cách kiểm tra số bit set trong một số nguyên. Các bit set là các 1 trong biểu diễn nhị phân của một số. Ví dụ số 13 có ba bit set 1101. Vậy đếm sẽ là 3.

Để giải quyết bài toán này, chúng ta sẽ dịch số sang phải, và nếu LSB là 1, thì tăng đếm. Cho đến khi số trở thành 0, nó sẽ chạy.

Thuật toán

countSetBit()

begin
  count := 0
  while count is not 0, do
    if LSb of n is set, then
      count := count + 1
    end if
    n := n after shifting 1 bit to right
  done
  return count
end

Ví dụ

#include<iostream>
using namespace std;

int count_set_bit(int n) {
  int count = 0;
  while(n != 0) {
    if(n & 1 == 1) {
      count++;
    }
    n = n >> 1; //right shift 1 bit
  }
  return count;
}

int main() {
  int n;
  cout << "Enter a number: ";
  cin >> n;
  cout << "Number of set bits: " << count_set_bit(n);
}

Kết quả

Enter a number: 29
Number of set bits: 4

Chương trình này sẽ chạy trong C và tạo ra đầu ra, nhưng khi chúng ta muốn biên dịch trong C++, nó sẽ trả về lỗi trong lúc biên dịch. Nó sẽ nói là có quá nhiều đối số được truyền.