Làm cách nào để sử dụng tính năng dịch chuyển bit để thay thế phân chia số nguyên?

Question

Tôi hiểu làm thế nào để làm điều đó cho quyền hạn của 2 vì vậy đó không phải là câu hỏi của tôi.

Ví dụ: nếu tôi muốn tìm 5% số bằng cách sử dụng thay đổi bit thay vì chia số nguyên, tôi tính toán như thế nào?

Vì vậy, thay vì (x * 20/19), tôi có thể làm (x * 100 >> 11). Bây giờ điều này là không đúng nhưng nó gần gũi và tôi đã đến nó bằng cách sử dụng thử và sai. Làm cách nào để xác định sự thay đổi chính xác nhất có thể sử dụng?

Answer 1

Vâng nói chung:

• có được phân tích nhân tử thủ về số lượng, bạn muốn phân hủy N thành 2^k * nghỉ ngơi, sau đó bạn có thể sử dụng chút thay đổi trên hai quyền lực. Ví dụ: 20 = 2^2 * 5, để nhân với hai mươi, bạn nhân với 5 và sau đó sử dụng dịch chuyển bit << 2
• Để sử dụng tính năng dịch chuyển bit không phải là hai quyền, hãy quan sát phần sau cho số lẻ l: a * l = a * (l - 1) + a, bây giờ l - 1 là thậm chí và do đó phân hủy thành một hai quyền lực, mà bit chuyển 'lừa' áp dụng.

Có thể xây dựng bộ phận tương tự.

Answer 2

Cách tiếp cận tốt nhất là để trình biên dịch làm điều đó cho bạn. Bạn chỉ cần viết

a/b 

bằng ngôn ngữ bạn chọn, và trình biên dịch tạo ra một chút twiddling.

EDIT (Tôi hy vọng bạn không nhớ, tôi đang bổ sung tăng cường cho câu trả lời của bạn:.

#include <stdio.h> 

int main(int argc, char **argv) { 
    printf("%d\n", argc/4); 
} 

Rõ ràng, điều nhanh nhất để làm là argc>>2 Hãy xem những gì sẽ xảy ra:

 .file "so3.c" 
     .section  .rodata 
.LC0: 
     .string "%d\n" 
     .text 
.globl main 
     .type main, @function 
main: 
     pushl %ebp 
     movl %esp, %ebp 
     andl $-16, %esp 
     subl $16, %esp 
     movl 8(%ebp), %eax 
     movl %eax, %edx 
     sarl $31, %edx 
     shrl $30, %edx 
     leal (%edx,%eax), %eax 
     sarl $2, %eax 
     movl %eax, %edx 
     movl $.LC0, %eax 
     movl %edx, 4(%esp) 
     movl %eax, (%esp) 
     call printf 
     leave 
     ret 
     .size main, .-main 
     .ident "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3" 
     .section  .note.GNU-stack,"",@progbits 

yup, có nó là, sarl $2, %eax

EDIT 2 (Xin lỗi vì đã chồng chất trên, nhưng 20/19 là phức tạp hơn một chút ...)

Tôi chỉ thay argc*20/19 cho argc/4 và đây là toán học mà đi ra:

0000000100000f07  shll $0x02,%edi 
0000000100000f0a  movl $0x6bca1af3,%edx 
0000000100000f0f  movl %edi,%eax 
0000000100000f11  imull %edx 
0000000100000f13  sarl $0x03,%edx 
0000000100000f16  sarl $0x1f,%edi 
0000000100000f19  subl %edi,%edx 

Vì vậy, quá trình này là

• Nhân đầu vào theo 4 (shll)
• Tải (movl 0x ...) và nhân (imull) một phần điểm cố định thu được kết quả 64 bit (đây là mã 32 bit)
• Divide cao theo đơn đặt hàng 32 bit của kết quả bằng 8 (sarl), lưu ý cách này xử lý số âm
• Divide thấp thứ tự 32 bit của kết quả bởi INT_MAX (sarl) để có được hoặc là 0 hoặc -1
• đúng làm tròn kết quả bậc cao bằng cách cộng 1 (trừ -1) nếu cần.

Answer 3

Giả sử bạn muốn xấp xỉ 5% x bằng cách nhân với y và dịch chuyển bằng n. Kể từ 5% là 1/20, và một >> n = a/2 ⁿ, bạn muốn giải quyết

x/20 ≈ x * y/2 ⁿ (biểu tượng "≈" có nghĩa là "xấp xỉ bình đẳng ")

mà đơn giản hoá để

y ≈ 2 ⁿ/20

Vì vậy, nếu n = 11, sau đó

y ≈ 2 ⁿ/20 = 2048/20 = 102 + 8/20

Vì vậy, chúng tôi có thể đặt y = 102, thực sự tốt hơn 100 bạn tìm thấy bằng thử và sai.

Nói chung, chúng tôi có thể chơi với n để xem liệu chúng tôi có thể nhận được câu trả lời hay hơn không.

Tôi đã làm việc này cho phần 1/20, nhưng bạn sẽ có thể làm việc này cho bất kỳ phân số p/q nào bằng cách thực hiện theo cùng phương pháp.

Answer 4

Giả sử bạn có biểu thức a = b/c. Như hroptatyr đã đề cập, phép nhân khá nhanh (và nó nhanh hơn nhiều so với phân chia). Vì vậy, ý tưởng cơ bản là biến đổi phân chia thành phép nhân như: a = b * (1/c).

Bây giờ, chúng tôi vẫn cần phân chia để tính toán đối ứng 1/c, do đó, điều này sẽ chỉ hoạt động nếu c được biết đến là apriori. Trong khi tính toán dấu phẩy động đủ, đối với intereges chúng ta phải sử dụng một thủ thuật khác: chúng ta có thể sử dụng cho nghịch đảo giá trị c giá trị some_big_number/c, để cuối cùng chúng ta sẽ tính a2 = b * (some_big_number/c), bằng some_big_number * b/c. Vì chúng tôi quan tâm đến giá trị của b/c, chúng tôi phải chia kết quả cuối cùng theo some_big_number. Nếu nó được chọn là một sức mạnh của 2, thì phân chia cuối cùng sẽ nhanh.

ví dụ:

// we'll compute 1/20 of the input 
unsigned divide_by_20(unsigned n){ 
    unsigned reciprocal = (0x10000 + 20 - 1)/20; //computed at compile time, but you can precompute it manually, just to be sure 
    return (n * reciprocal) >> 16; 
} 

EDIT: một phần tốt của phương pháp này là bạn có thể chọn bất kỳ phương pháp làm tròn cho KHỐI bằng cách chọn chỉnh (trong trường hợp này đó là 20 - 1 để làm tròn về phía zero).

Answer 5

Bạn không thể làm mọi thứ với ca làm việc, thay vào đó bạn sẽ cần phải sử dụng ước mơ 'ma thuật' (xem tin tặc thỏa thích). Phép chia ma thuật hoạt động bằng cách nhân một số với một số lớn phù hợp khác, lăn nó theo cách như vậy để mang lại câu trả lời của phép chia (mul/imul nhanh hơn div/idiv). Có hằng số ma thuật chỉ là duy nhất cho mỗi số nguyên, bội số yêu cầu thay đổi, ví dụ: phân số không dấu bằng 3 có thể được biểu diễn (trên 32 bit) là , chia cho 6 sẽ là (x * 0xAAAAAAAB) >> 1 chia cho 12 sẽ thay đổi theo 2, 24 x 3 (của nó là hàng loạt hình học 3 * (2^x), trong đó 0 < = x < 32)

Answer 6

Nó không có ý nghĩa bởi vì những gì bạn đang cố gắng làm không tối ưu hóa quá trình kết quả !!!

Xin chào, tôi không đọc bất kỳ đâu trong câu hỏi của bạn mà bạn có ý định tối ưu hóa.

Điện Người không bao giờ ngừng tò mò bất kể "tính hữu ích". Chúng tôi giống như những người tích cực ám ảnh về những thứ mà bạn đọc trong tin tức nơi họ xếp gác gác, hầm, phòng ngủ và phòng khách với rác mà họ tin sẽ có ích trong một ngày. Ít nhất đó là trường hợp khi tôi ở trường Engg cách đây chưa đầy 30 năm. Tôi khuyến khích bạn tiếp tục tìm kiếm để tích trữ kiến ​​thức "vô dụng" dường như có ít khả năng tối ưu hóa cuộc sống hoặc phong cách sống của bạn. Tại sao phụ thuộc vào trình biên dịch khi bạn có thể làm điều đó bằng thuật toán mã hóa bằng tay? Yah? Có một chút mạo hiểm, bạn biết đấy. Ok enuf giải tán những người bày tỏ thái độ khinh thị khi bạn theo đuổi kiến ​​thức.

Hãy nhớ lại trường trung học của bạn, cách bạn được dạy làm bộ phận của bạn? 437/24, ví dụ:

_____ 
24|437 


    018 
    ----- 
24|437 
    24 
    ----- 
    197 
    24 
    ----- 
    5 

Số thuộc phân chia, 437, được gọi là cổ tức. 24 là số chia, kết quả 18 là thương, và 5 là số dư. Giống như khi bạn nộp thuế, bạn cần phải điền vào lợi nhuận bạn đã nhận được từ cổ tức "cổ tức", vốn là một từ sai. Những gì bạn điền vào biểu mẫu thuế là một bội số của thương lượng của một phần lớn cổ tức. Bạn không nhận được cổ tức, nhưng phần cổ tức - nếu không, điều đó có nghĩa là bạn sở hữu 100% cổ phần.

 ___________ 
11000|110110101 



     000010010 
    ----------- 
11000|110110101 
     11000 
    ---------- 
     000110101 remainder=subtract divisor from dividend 
     11000000 shift divisor right and append 0 to quotient until 
     1100000 divisor is not greater than remainder. 
     110000 Yihaa! 
    ---------- 
     000101 remainder=subtract shifted divisor from remainder 
      11000 shift divisor right and append 0 to quotient until 
      1100 divisor is not greater than remainder. 
    ---------- 
       oops, cannot shift anymore. 

Ở trên, như bạn đã biết, là phân chia TRUE. Điều này đạt được bằng cách trừ đi bằng ước số đã dịch chuyển.

Điều bạn muốn là đạt được điều tương tự bằng cách đơn giản là chuyển cổ tức. Điều đó, thật không may không thể được thực hiện trừ khi số chia là một lũy thừa lũy thừa của 2 (2,4,8,16). Đó là một thực tế rõ ràng về số học nhị phân. Hoặc, ít nhất tôi không nhận thức được bất kỳ phương pháp nào có thể làm điều đó mà không có các kỹ thuật xấp xỉ và intrapolative.

Vì vậy, bạn phải sử dụng kết hợp giữa thay đổi cổ tức và phân chia thực sự. ví dụ:

24 = 2 x 2 x 2 x 3 

Thứ nhất, chia 437 8 sử dụng thay đổi nhị phân để có được 010.010 và sau đó sử dụng phân chia đúng chia cho 3:

010010 
    -------- 
11|110110 
    11 
    ------- 
    011 
     11 
    ----- 
     0 

mà hoạt động ra vào 010010 = 18.

Voila.

Làm thế nào để bạn xác định 24 = 2^8 x 3?

Bằng cách chuyển 11000 sang phải cho đến khi bạn đạt mức 1.

Điều đó có nghĩa, bạn có thể thay đổi cổ tức cùng một số lần như bạn sẽ chuyển số chia cho đến khi số chia chạm một 1.

Do đó, rõ ràng, phương pháp này sẽ không hoạt động nếu số chia là lẻ. ví dụ, nó sẽ không hoạt động cho ước số 25, nhưng nó sẽ làm việc một chút cho ước số 50.

Có thể, có các phương pháp tiên đoán có thể nội suy số chia như 13 đến giữa 2^3 = 8 và 2^4 = 16. Nếu có, tôi không quen thuộc với họ.

Điều bạn cần khám phá là sử dụng chuỗi số.Ví dụ chia cho 25:

1 1 1  1  1 
__ = __ - ___ - ___ + ___ - ... until the precision you require. 
25 16 64 128 256 

nơi dạng tổng quát của bộ truyện là

1 1  b1    bn 
_ = ___ + _______ + ... + ______ 
D 2^k 2^(k+1)   2^(k+n) 

nơi tỷ là một trong hai -1, 0 hoặc +1.

Tôi hy vọng thao tác nhị phân của tôi ở trên sẽ không có lỗi hoặc lỗi chính tả. Nếu vậy, hàng ngàn lời xin lỗi.

Answer 7

Nếu bạn quan tâm đến toán học đằng sau nó, hãy đọc Delight Delight bởi Henry S. Warren.

Nếu bạn quan tâm đến mã được tối ưu hóa, chỉ cần viết những gì dễ đọc nhất của con người. Ví dụ:

int five_percent(int x) { 
    return x/20; 
} 

Khi bạn biên dịch chức năng này sử dụng g++ -O2, nó sẽ không làm một bộ phận thực tế nhưng một số nhân kỳ diệu, bit-chuyển và sửa chữa thay thế.