Bạn có chắc chắn muốn xóa bài viết này không ?
Bạn có chắc chắn muốn xóa bình luận này không ?
Bit twiddling (part 3)
Câu đố:
Các bạn có biết đoạn code sau dùng để làm gì?
n & (n-1) == 0
Hãy thử không nhìn giải đáp ở dưới và suy nghĩ trong vòng vài phút xem sao
Giải đáp
Đoạn code trên check một điều kiện là n & (n-1)
có bằng 0 hay không, tức là lời giải sẽ là kiểu nếu n có một đặc tính gì đó thì sẽ thoả mãn công thức trên đúng không :P.
Hãy thử một vài ví dụ nhé
Input: 111
Output: 111 & 110 == 110
Input: 1001
Output: 1001 & 1000 == 1000
Ủa theo như trên thì n & (n-1) có vẻ sẽ là n-1 đúng không nhở, vậy thì đáp án sẽ là n & (n-1) == 0 tức là n-1 == 0 hay là n = 1!
Kết luận sớm quá vậy :P, từ ví dụ trên chúng ta có thể thấy nếu n có bit cuối cùng là 1 thì suy luận trên sẽ đúng, thử với trường hợp n có bit cuối là 0 xem sao.
Input: 110
Output: 110 & 101 == 100
Input 1100
Ouput: 1100 & 1011 == 1000
Input: 100
Output: 100 & 011 = 0!!!!
Chúng ta observe một điều thú vị là, nếu n và n-1 có cùng số bit, thì kết quả sẽ luôn khác 0 bởi vì 1xxxx & 1yyyy sẽ luôn có kết quả là 1zzzz đúng không. Suy ra 2 đặc tính của n là:
- Bit cuối là 0
- n-1 sẽ giảm số bít đi
Từ 2 đặc tính trên chúng ta có thể "đoán" được là n chỉ có thể là dạng 1000..00
tức là n chính là số mũ của 2! Yay!







