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!