solution

Trong tối ưu hóa mã máy, phép nhân/chia cho lũy thừa của 2 có thể được thay bằng phép dịch bit (shift) vốn rẻ hơn nhiều so với phép nhân/chia thực sự, vì $a \times 2^k = a \ll k$, và với $a \ge 0$ thì $\lfloor a / 2^k \rfloor = a \gg k$.

Cho $n$ lệnh mã ba địa chỉ dạng x = a op b với $op \in \{+,-,*,/\}$, trong đó $a,b$ mỗi cái là một hằng số nguyên không âm hoặc tên biến. Với mỗi lệnh, hãy áp dụng đúng một quy tắc đầu tiên khớp trong danh sách theo thứ tự ưu tiên sau:

1. Nếu $op$ là * và đúng một trong hai toán hạng là hằng số bằng $2^k$ ($k \ge 1$) còn toán hạng kia là biến (không phải hằng số) → thay bằng x = <biến> << k.
2. Nếu $op$ là / và $b$ là hằng số bằng $2^k$ ($k \ge 1$) còn $a$ là biến (không phải hằng số) → thay bằng x = <biến> >> k (giả thiết biến đó luôn không âm lúc chạy).
3. Nếu không quy tắc nào khớp, giữ nguyên lệnh gốc.

Lưu ý quan trọng: $2^0 = 1$ không được coi là lũy thừa của 2 hợp lệ cho quy tắc này (tức $k$ phải $\ge 1$); nếu cả hai toán hạng đều là hằng số, hoặc toán tử là +/-, lệnh luôn giữ nguyên.

Ví dụ: x = 4 * y → x = y << 2 (vì $4=2^2$); x = y / 4 → x = y >> 2; x = 3 * y giữ nguyên (3 không phải lũy thừa của 2); x = y * 1 giữ nguyên ($2^0=1$ không hợp lệ).