Tôi cần tính cơ sở nhật ký 2 của một số trong C nhưng tôi không thể sử dụng thư viện toán học. Câu trả lời không cần phải chính xác, chỉ với int gần nhất. Tôi đã nghĩ về nó và tôi biết tôi chỉ có thể sử dụng một vòng lặp while và tiếp tục chia số cho 2 cho đến khi nó là < 2, và giữ số lần lặp lại, nhưng điều này có thể sử dụng toán tử bitwise không?Làm thế nào để đăng nhập máy tính cơ sở 2 bằng cách sử dụng các toán tử bitwise?
Nếu bạn đếm shifting làm toán tử bitwise, điều này thật dễ dàng.
Bạn đã biết làm thế nào để làm điều đó bằng cách phân chia liên tiếp bằng 2.
x >> 1 cũng giống như x/2 cho bất kỳ số nguyên unsigned trong C.
Nếu bạn cần phải thực hiện điều này nhanh hơn, bạn có thể làm một "phân chia và chinh phục" - nhanh, nói, 4 bit tại một thời điểm cho đến khi bạn đạt tới 0, sau đó quay lại và xem 4 bit cuối cùng. Điều đó có nghĩa là tối đa 16 ca và 19 lần so sánh thay vì 63 lần. Cho dù nó thực sự nhanh hơn trên một CPU hiện đại, tôi không thể nói mà không thử nghiệm. Và bạn có thể thực hiện điều này một bước xa hơn, đầu tiên làm các nhóm 16, sau đó 4, sau đó 1. Có thể không hữu ích ở đây, nhưng nếu bạn có một số số nguyên 1024 bit, nó có thể đáng xem xét.
Cảm ơn, tôi đã không nhận ra nó hiển nhiên như thế nào. Tôi đã hiểu rồi. – SKLAK
@SKLAK: Để có thêm niềm vui, hãy thử biên dịch mã '/ 2' và' >> 1' bằng -O2 và xem nó khác như thế nào. Nếu một là nhanh hơn đáng kể so với khác, bạn cũng có thể nhận được chính xác cùng một mã cho cả hai. – abarnert
Chúng sẽ chỉ giống với 'unsigned'. Đối với 'int', có một thao tác bổ sung để thêm bit dấu trước, để đảm bảo rằng kết quả làm tròn về 0 chứ không phải là vô cực âm. –
Đã trả lời bằng cách abamert nhưng chỉ để được cụ thể hơn đây là cách bạn sẽ mã hóa nó:
Log2(x) = result
while (x >>= 1) result++;
Bạn đếm [chuyển] (http://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts) như một toán tử bitwise? Nếu vậy, câu trả lời là khá rõ ràng. Nếu không, nó phức tạp hơn. – abarnert
0_o Tại sao bạn không thể sử dụng thư viện toán học? –
@JackManey: Có lẽ đây là bài tập về nhà hoặc tương đương tự dạy học. Nhưng đó là tốt; anh ta dường như đã nỗ lực vào nó (anh ấy luôn có một giải pháp làm việc), và đang tìm kiếm những gợi ý để xem có cách nào khác để làm điều đó, không yêu cầu chúng tôi làm bài tập về nhà cho anh ấy. – abarnert