Chuyển đổi phương trình thành hoạt động dịch chuyển bit

Question

Có cách nào tiêu chuẩn để chuyển đổi một phương trình (bất kỳ) thành hoạt động bit-shift không?

Bằng cách này, tôi có nghĩa là chuyển đổi bất cứ điều gì đó không phải là một + hoặc - vào bit thay đổi, vì vậy phương trình cuối chỉ chứa các toán hạng < <, >>, + và -. Điều này là vì lợi ích của việc làm cho các công thức ít xử lý chuyên sâu hơn.

Rõ ràng các phương trình kết quả này sẽ chỉ xấp xỉ, cho độ chính xác tốt hơn với nhiều đơn hàng được xem xét hơn (thứ tự đầu tiên, thứ tự e.t.c).

Tôi đã xóa trang web để tìm thông tin về điều này nhưng không thể tìm thấy bất kỳ thông tin nào, ngoại trừ các nội dung về các công thức cụ thể (sin, cos, inv e.t.c).

Tôi đã hình dung ra một thứ gì đó giống như một quy trình mở rộng đa thức hoặc của Taylor, sau đó chuyển đổi thành các thao tác bit-shift.

Answer 1

Chỉ vì bạn đang giảm thứ gì đó thành hướng dẫn đơn giản hơn, không có nghĩa là chúng sẽ chạy nhanh hơn hoặc ít tốn kém hơn theo một cách nào đó. Mặc dù bạn có thể giảm nhiều thứ xuống một tập hợp con các hoạt động giảm, bạn có thể sẽ cần thêm nhiều thao tác nữa để hoàn thành nhiệm vụ tương tự. Một bộ xử lý chỉ có thể thực thi quá nhiều thao tác trong một giây và bạn sẽ chạy nó trước tiên.

Nói chung khi cố gắng tối ưu hóa nội dung nào đó ở mức thấp, bạn đang cố gắng tận dụng các mã opcodes phức tạp hơn để bạn cần ít người hơn. Ví dụ, bạn có thể thực hiện phép nhân bằng cách thực hiện nhiều lệnh ADD. Nhưng, đối với bất cứ điều gì khác hơn là tầm thường nhất của các ví dụ, nó sẽ mất nhiều hơn đáng kể ADDs hơn so với MUL opcode duy nhất mà nó đã mất, và mất nhiều thời gian để thực thi.

Quay trở lại câu hỏi thực tế của bạn mặc dù ... Hoàn toàn bỏ qua hiệu quả, bạn có thể tính toán bất cứ điều gì miễn là tập lệnh bạn có là Turing Hoàn thành. Bạn thực sự có thể tính toán bất cứ điều gì bằng cách sử dụng a single instruction, nếu bạn cẩn thận cách bạn chọn hướng dẫn đó. Tôi không tin rằng có bất kỳ mục đích chung của câu nói "Chuyển đổi bất kỳ thuật toán tùy ý vào chỉ sử dụng các hướng dẫn", đó thường là công việc của một nhà biên dịch trình biên dịch.

Answer 2

Không nói chung. Trên hầu hết CPU, phép nhân không chậm hơn đáng kể so với các phép tính số học khác, do đó, có ít mục đích cố gắng chuyển đổi phép nhân thành phép dịch chuyển bit, trừ phép nhân bằng lũy ​​thừa không đổi của hai.

Theo phân chia, có một số phương pháp nổi tiếng để chuyển đổi phân chia theo hằng số thành phép nhân theo nghịch đảo và các phương thức này khá hiệu quả. Xem http://www.flounder.com/multiplicative_inverse.htm để biết cách giải thích. Tuy nhiên, phân chia theo các giá trị không liên tục không thể được tối ưu hóa.

Tăng 2 lên một lũy thừa (hoặc chia cho một số bằng lũy ​​thừa 2), tất nhiên, dễ dàng được chuyển đổi sang chuyển bit. Tuy nhiên, các số mũ khác không dễ dàng chuyển đổi.

Hầu hết các chức năng siêu việt không thể được biểu diễn một cách hợp lý ở mức độ bit. Nó không giúp đỡ rằng hầu hết không được xác định trên số nguyên anyway.

Answer 3

Nhân phần mềm với các thao tác bit-khôn ngoan không có khả năng đánh bại phép nhân phần cứng trên các CPU hiện đại.

Thường đi xuống thao tác bit-khôn ngoan có thể mang lại hiệu suất tốt hơn nếu nó cho phép tránh 1) vòng; và 2) phân nhánh.

A good online cookbook để lấy cắp bit. Nếu không, có A Hacker's delight.