Bài toán về bit

[Nam_Cao]

Em có bài toán về bit mà nghĩ mãi không ra, mọi người xem cách giải quyết như nào ạ? Em cám ơn

[SITUVN.gcd]

Bạn đã biết:

• Dùng các phép toán về bit.

chưa?

Có bao nhiêu bit 0 thì thực hiện bấy nhiêu lần lật và xét độ dài thôi.

[thanhtrung2314 (Trung Nguyen)]

muốn lật mà dài nhất thì số bit 1 liên tiếp bên trái + bên phải số 0 cũng phải dài nhất
đi từ phải sang trái (hoặc trái sang phải tuỳ)
nếu là bit1 thì trái++
nếu gặp bit 0 thì: nếu bit tiếp theo là bit 1 vậy trái thay = phải, nếu bit tiếp theo là bit 0 thì phải = 0
cả 2 trường hợp trên đều update lại trái = 0
mỗi lần lặp thì so max = (trái + phải, max)
kết quả là trái + phải + 1 (vì ta chỉ mới tính trái phải, chưa tính bit 0 ta lật, độ dài sẽ + 1)
làm như trên thì sẽ hố nếu gặp trường hợp gặp toàn 1 khi ta ko có số 0 để làm trái phải
khi đó thì ta cứ check nếu ~n (lấy not toàn bộ bit của n) = 0 thì tức là toàn bit 1, trả về số bit cần để biểu diễn số đó, dùng hàm của ngôn ngữ cũng được hoặc làm tròn xuống log2(n) + 1

[Nam_Cao]

Cảm ơn mọi người giúp đỡ. Nhân tiện cho em hỏi cách tư duy để khi biết giải thuật mình có thể code nhanh nhất ạ?

[rogp10]

Bài này cho bằng số nên bt là n & (n+1) == 0.

[nitro2 (Nhím)]

Câu này giống như câu: “Anh ơi cho em hỏi làm sao đỗ đại học ạ?”