Bitshifts để nhận số còn lại

Question

Tôi muốn biết cách lấy phần còn lại bằng cách chia một số nguyên với một số nguyên khác (cả hai số nguyên) chỉ sử dụng bithift hoặc bitwise operator. Nhà điều hành / hoặc nhà điều hành % không được sử dụng.

Ví dụ: để nhận phần còn lại khi số chia có dạng 2^k, hoạt động sau sẽ sinh phần còn lại.

m = Remainder

n = The number

d = The divisor

m = n & (d - 1)

Tuy nhiên phương pháp này chỉ hoạt động khi d có dạng 2^k. Tôi muốn biết một phương pháp tương tự cho quyền hạn không thuộc số 2. Tôi hiện đang giải quyết sự cố từ programming challenges và muốn sử dụng phương pháp như vậy để giảm thời gian thực hiện chương trình

Answer 1

Bất kỳ câu trả lời nào không sử dụng toán tử % sẽ là câu trả lời kém hiệu quả hơn, nhưng nếu bạn hoàn toàn không thể sử dụng nhà điều hành, sau đó, một trong những giải pháp là sử dụng một vòng lặp để trừ d từ n lặp đi lặp lại:

m = n; 
while (m >= d) 
{ 
    m -= d; 
} 

Giả sử số nguyên của bạn là 32-bit, sau đó bạn có thể xem xét một phiên bản tối ưu hóa nơi chúng tôi xóa bội số của d từ n:

m = n; 
for (i = 31; i >= 0; i--) 
{ 
    di = d << i; 
    if (di > 0 && m >= di) m -= di; 
} 

Ví dụ này, giả sử các số nguyên được ký và đồng hồ cho tràn, tức là thử nghiệm cho di > 0.