My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
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 self-studying 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 "divide-and-conquer" 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.
Atrend is offline  
 
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.
phillip1882 is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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





Copyright © 2019 My Math Forum. All rights reserved.