Tại sao 0x55555556 chia cho 3 công việc hack?

Question

Có một hack (tương đối) nổi tiếng để chia số 32 bit cho ba. Thay vì sử dụng phân chia đắt tiền thực tế, số có thể được nhân với số ma thuật 0x55555556 và 32 bit trên của kết quả là những gì chúng tôi đang tìm kiếm. Ví dụ, đoạn code C sau:

int32_t div3(int32_t x) 
{ 
    return x/3; 
} 

biên soạn với GCC và -O2, kết quả trong việc này:

08048460 <div3>: 
8048460: 8b 4c 24 04    mov ecx,DWORD PTR [esp+0x4] 
8048464: ba 56 55 55 55   mov edx,0x55555556 
8048469: 89 c8     mov eax,ecx 
804846b: c1 f9 1f    sar ecx,0x1f 
804846e: f7 ea     imul edx 
8048470: 89 d0     mov eax,edx 
8048472: 29 c8     sub eax,ecx 
8048474: c3      ret 

Tôi đoán các hướng dẫn sub có trách nhiệm sửa chữa số âm, bởi vì những gì nó làm về cơ bản là thêm 1 nếu đối số là số âm, và đó là một số NOP nếu không.

Nhưng tại sao hoạt động? Tôi đã cố gắng nhân các số nhỏ hơn theo cách thủ công với phiên bản 1 byte của mặt nạ này, nhưng tôi không nhìn thấy mẫu và tôi thực sự không thể tìm thấy bất kỳ giải thích nào ở bất kỳ đâu. Nó có vẻ là một số ma thuật bí ẩn có nguồn gốc không rõ ràng cho bất cứ ai, giống như 0x5f3759df.

Ai đó có thể cung cấp giải thích về số học đằng sau điều này không?

Answer 1

Đó là vì 0x55555556 thực sự là 0x100000000/3, được làm tròn lên.

Làm tròn là quan trọng. Vì 0x100000000 không chia đều cho 3, sẽ có lỗi trong kết quả 64 bit đầy đủ. Nếu lỗi đó là số âm, kết quả sau khi cắt ngắn 32 bit thấp hơn sẽ là quá thấp. Bằng cách làm tròn lên, lỗi là tích cực, và tất cả trong 32 bit thấp hơn để cắt bớt nó ra.