Xoay bit của một số II
Bài học 13 trên 17 trong khóa học Thao tác bit của Coddy.
Được rồi! Bạn đã hiểu phép xoay là gì. Tuy nhiên, trong trường hợp này, ta cũng có thể xem phép xoay như việc sử dụng các phép dịch bit. Ta cũng có thể nói rằng xoay một số nhị phân cũng giống như thực hiện phép dịch bit trên số đó, nhưng thay vì loại bỏ các bit, ta đưa chúng trở lại số. Hãy cùng tìm hiểu qua một ví dụ:
Giả sử ta có (33)10 trên một máy tính 8 bit. Số này sẽ được lưu dưới dạng (00100001)2, nếu ta xoay sang trái 3 lần.
- Đầu tiên, ta đã dịch trái (33)10 3 lần.
- Để giữ lại các bit bị dịch ra ngoài, ta đã dịch phải số đó 8-3 lần. (8 là số bit máy tính dùng để lưu số trong bộ nhớ)
- Sau đó, ta thực hiện phép OR trên x và y để thu được số đã xoay.
| x = 33<<3 | 00001000 |
| y = 33>>5 | 00000001 |
x | y | 00001001 |
Tương tự, ta có thể xoay sang phải:
- Đầu tiên, ta sẽ dịch (33)10 sang phải 3 lần và lưu giá trị đó vào một biến.
- Sau đó, ta dịch trái giá trị đó (8-3) lần và lưu vào một biến khác.
- Tiếp theo, ta thực hiện phép OR để thu được số đã xoay.
| x = 33 >> 3 | 00000100 |
| y = 33 << 5 | 00100000 |
x | y | 00100100 |
Vậy là xong! Nhờ các phép thao tác bit, ta có thể xoay các bit của một số nhị phân thật dễ dàng.
Thử thách
Trung bìnhHoàn thiện hàm SumLeftRightRotation() để trả về tổng giá trị của phép xoay trái và xoay phải số đã cho.
Ví dụ, với số 20, phép xoay trái trả về 40 và phép xoay phải trả về 10, nên đầu ra sẽ là 50, tổng của phép xoay trái và xoay phải.
Ở đây, num đại diện cho số đó và r đại diện cho số lần xoay.
Tự làm thử
#define INT_BITS 32
using namespace std;
int SumLeftRightRotation(int num, int r) {
// Viết code tại đâ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ố