
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
September 6th, 2019, 10:28 AM  #1 
Newbie Joined: Jan 2018 From: Belgium Posts: 8 Thanks: 0  Logarithm binary numbers
Hello everyone, I am currently learning about binary numbers and I have stumbled on this problem: "write a function (log n) that calculates the logarithm (base 2) of number n. Number n is a positive binary number". (only using binary arithmetic operations) I know this is a very basic question on this forum, but I have been thinking about it for a few evenings and have not found anything. As I am selfstudying this subject, I cannot turn to anyone for a hint. Could someone help me on the way here? A hint is to determine the most significant bit first, and to use a "divideandconquer" method for large numbers (64+ bit). My strategy would be to find the most significant 1: its position would give me the integral part of the log. It is the fractional part I am kind of stuck on. I thank you in advance. Last edited by skipjack; October 25th, 2019 at 04:58 PM. 
October 25th, 2019, 04:35 PM  #2 
Member Joined: May 2013 Posts: 57 Thanks: 5 
It's the "only using binary arithmetic operations" that's a stumbling block for me. Without that, it would be simple. Just divide by 2, until the number is 0, and count divisions. But with that restriction, division isn't easily available to you. the only allowable operations are and &, or , xor ^, shift left <<, shift right >> not !, and comparisons (==, >= etc.) Code: N = value count = 0 carry = 0 while N > 0: N = N >> 1 carry = 1 while carry != 0: count, carry = count ^ carry, (count &carry) << 1 print(count) Last edited by skipjack; October 25th, 2019 at 05:00 PM. 

Tags 
binary, logarithm, numbers 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Taking the binary logarithm  error propagation?  Biochemist  Physics  7  September 13th, 2016 06:06 AM 
adding binary numbers  thomas2608  Calculus  2  November 19th, 2014 01:18 PM 
binary numbers  mhhojati  Number Theory  3  November 5th, 2013 11:04 PM 
Binary Multiplication of two 1024bit numbers  prakha  Applied Math  1  April 25th, 2013 10:08 AM 
Binary Numbers  johnny  Computer Science  6  October 18th, 2007 11:29 AM 