Thực hiện phép chia số nguyên sử dụng phép nhân

Question

Nhìn vào lắp ráp x86 do trình biên dịch tạo ra, tôi nhận thấy rằng các bộ phận số nguyên (chưa ký) đôi khi được thực hiện dưới dạng số nguyên. Những tối ưu hóa dường như theo các hình thức

value/n => (value * ((0xFFFFFFFF/n) + 1))/0x100000000 

Ví dụ, biểu diễn một bộ phận của 9:

12345678/9 = (12345678 * 0x1C71C71D)/0x100000000 

Một bộ phận của 3 sẽ sử dụng phép nhân với 0x55555555 + 1, và vân vân.

Khai thác thực tế là lệnh mul lưu trữ phần cao của kết quả trong thanh ghi edx, kết quả cuối cùng của bộ phận có thể thu được bằng cách sử dụng phép nhân đơn với giá trị phép thuật. (Mặc dù tối ưu hóa này đôi khi được sử dụng kết hợp với một chút thay đổi khôn ngoan ở cuối.)

Tôi muốn có một số thông tin chi tiết về cách thức này thực sự hoạt động. Cách tiếp cận này hợp lệ khi nào? Tại sao phải 1 được thêm vào "số ma thuật" của chúng tôi?

Answer 1

Phương pháp đó được gọi là "Phân chia theo phép nhân bất biến".

Hằng số mà bạn đang xem thực sự xấp xỉ đối ứng.

Vì vậy, chứ không phải là tính toán:

N/D = Q 

bạn làm điều gì đó giống như thay vì điều này:

N * (1/D) = Q 

nơi 1/D là một đối ứng có thể được precomputed.

Về cơ bản, các số nghịch đảo không chính xác trừ khi D là nguồn cấp hai. Vì vậy, sẽ có một số lỗi liên quan đến vòng lặp. Các +1 mà bạn thấy là có để sửa chữa cho các lỗi vòng-off.

---

Ví dụ phổ biến nhất là phân chia bởi 3:

N/3 = (N * 0xaaaaaaab) >> 33 

đâu 0xaaaaaaab = 2^33/3 + 1.

Cách tiếp cận này sẽ khái quát hóa với các ước tính khác.