Số lượng bit 1
Bài học 11 trên 17 trong khóa học Thao tác bit của Coddy.
Trước tiên, bit bật là gì?
Trong thuật ngữ máy tính, chữ số '1' trong số nhị phân được gọi là bit bật.
Trong bài học này, chúng ta muốn tính:
Số bit bật có trong biểu diễn nhị phân của số đã cho.
Ví dụ, giả sử ta có số (20)10 ở dạng nhị phân (10100)2 , số bit bật có trong (20)10 là 2.
Hãy thử nghĩ cách giải. Có thể bạn sẽ nghĩ đến việc chuyển số đó sang dạng nhị phân rồi đếm số chữ số 1. Được thôi, nhưng nếu số đó lớn thì sao? Bạn sẽ không thể lưu chúng bằng kiểu dữ liệu số nguyên, vậy làm sao ta biết được số bit bật trong những số lớn? Câu trả lời hiển nhiên là thao tác trên bit!
- Đầu tiên, ta dùng một biến vị trí, gọi là pos, để biết bit nào nằm ở một vị trí cụ thể trong số nhị phân.
- Sau đó, ta dịch trái số pos lần với giá trị '1'.
- Tiếp theo, ta chỉ cần thực hiện phép AND với số đã cho.
Điều này có ích như thế nào? Hãy cùng tìm hiểu với số (20)10:
- Ở vị trí thứ nhất, pos=0.
20 & 1<<pos, 1<<pos=1 và thực hiện phép AND giữa (10100)2 và (00001)2 cho kết quả là không. - Ở vị trí thứ hai, pos=1.
20 & 1<<pos, 1<<pos=(10)2 và thực hiện phép AND giữa (10100)2 và (00010)2 cho kết quả là không. - Ở vị trí thứ ba, pos=2.
20 & 1<<pos, 1<<pos=(100)2 và thực hiện phép AND giữa (10100)2 và (00100)2 cho kết quả là một, tức là bit bật đầu tiên của ta. - Ở vị trí thứ tư, pos=2.
20 & 1<<pos, 1<<pos=(1000)2 và thực hiện phép AND giữa (10100)2 và (01000)2 cho kết quả là không. - Ở vị trí thứ ba, pos=2.
20 & 1<<pos, 1<<pos=(10000)2 và thực hiện phép AND giữa (10100)2 và (10000)2 cho kết quả là một, tức là bit bật thứ hai.
Để đếm số bit bật, ta có thể dùng một biến đếm. Nhưng mình hy vọng ví dụ này giúp bạn hiểu rõ thuật toán.
Bằng cách này, ta có thể dễ dàng tính số bit bật có trong biểu diễn nhị phân của một số mà không cần lo số đó vượt quá phạm vi của kiểu dữ liệu int trong C++.
Thử thách
Trung bìnhHoàn thành hàm SetBits để trả về số bit được đặt trong số đã cho bằng cách sử dụng phương pháp trên.
Tự làm thử
#include <cmath>
int SetBits(int num) {
// Viết code ở đây
}Tất cả bài học trong Thao tác bit
2Thuật toán bit
Lũy thừa của 2Số xuất hiện số lần lẻSố lượng bit 1Xoay bit của một số IXoay bit của một số IITự luyện tập: Trình biên dịch C++ online
Kiểm tra một phép chuyển đổi: Công cụ chuyển đổi hệ cơ số