Lũy thừa của 2
Bài học 9 trên 17 trong khóa học Thao tác bit của Coddy.
Nếu bạn đã thực hành đủ với các số nhị phân, hẳn đến giờ bạn đã nhận ra rằng mọi lũy thừa của 2 đều chỉ có 1 bit được bật (bit được bật là bit có giá trị '1'). Ví dụ: (2)10 = (10)2 , (4)10 = (100)2 , (8)10 = (1000)2 và cứ thế.
Trong bài học này, chúng ta sẽ thảo luận về bài toán sau:
Dùng thao tác bit để xác định một số cho trước có phải là lũy thừa của 2 hay không.
Được rồi! Vậy nhận xét trên giúp ích cho chúng ta thế nào? Hãy cùng tìm hiểu.
- Giả sử ta có (8)10 và biết rằng đây là lũy thừa của 2.
- Trừ đi 1, ta được (7)10, tương đương với (0111)2.
- Nếu thực hiện phép AND ( & ) với 7 và 8, ta được 0.
- Thú vị phải không? Hãy thử với một số khác cũng là lũy thừa của 2. Lấy (32)10, tương đương với (100000)2, rồi trừ đi 1, ta được (31)10 = (011111)2. Một lần nữa, kết quả là 0!
- Vậy, khái quát điều này, ta có thể nói rằng nếu một số, gọi là x, là lũy thừa của 2 thì ( x & (x-1) ) luôn bằng '0' không?
Dựa vào nhận xét này, ta có thể dễ dàng giải bài toán mà không cần dùng thư viện toán học hay hàm tính lũy thừa, cũng không cần dùng vòng lặp. Ta vừa giải được bài toán với độ phức tạp thời gian O(1)! Thật tuyệt phải không? Đó là cách thao tác bit giúp chúng ta tối ưu chương trình đáng kể, đồng thời khiến code bớt phức tạp hơn.
Thử thách
DễCho trước một số, hãy xác định số đó có phải là số chẵn hay không bằng cách thao tác trên bit.
Tự làm thử
#include <iostream>
using namespace std;
bool IsPowerOf2(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ố