8
\$\begingroup\$

Is there a better way to code this specific algorithm using successively division through 2 which converts decimal numbers into binary numbers without calling a built-in function?

print "Please enter a decimal number."
prompt = '>> '
dec_number = input(prompt)
dec_new = dec_number 
binstr = ''

'''dec2bin'''
while dec_new != 0:
  binstr += str(dec_new % 2)
  dec_new = dec_new // 2

print binstr[::-1]
\$\endgroup\$
0

1 Answer 1

8
\$\begingroup\$

In general, your idea is not bad.

The best solution, as far as I read, would be the algorithm Divide by 2 that uses a stack to keep track of the digits for the binary result.

As an intro, this algorithm assumes that we start with an integer greater than 0. A simple iteration then continually divides the decimal number by 2 and keeps track of the remainder.

dec-to-bin

The first division by 2 gives information as to whether the value is even or odd. An even value will have a remainder of 0. It will have the digit 0 in the ones place. An odd value will have a remainder of 1 and will have the digit 1 in the ones place. We think about building our binary number as a sequence of digits; the first remainder we compute will actually be the last digit in the sequence.

That said, we have:

from pythonds.basic.stack import Stack

def divideBy2(decNumber):
    remstack = Stack()

    while decNumber > 0:
        rem = decNumber % 2
        remstack.push(rem)
        decNumber = decNumber // 2

    binString = ""
    while not remstack.isEmpty():
        binString = binString + str(remstack.pop())

    return binString

print(divideBy2(42))

Comments regarding your code:

  1. Why did you do this: dec_new = dec_number ? You could've just use dec_number. There's no need of assigning its value to another variable.
  2. This: dec_new = dec_new // 2 could be as well as the above line of your code rewritten as: dec_new //= 2
  3. The indentation should contain 4 spaces, not 2.

A version that better (than your solution) utilizes the memory would be:

def dec_to_bin(n):
    bits = []

    bits.append(str(0 if n%2 == 0 else 1))
    while n > 1:
        n = n // 2
        bits.append(str(0 if n%2 == 0 else 1))

    bits.reverse()
    return ''.join(bits)

What I did:

  • floor divide all the numbers by two repeatedly until we reach 1
  • going in reverse order, create bits of this array of numbers, if it is even, append a 0 and if it is odd append a 1.

Other ways of doing it:

Using recursion:

def dec_to_bin(x):
    return dec_to_bin(x/2) + [x%2] if x > 1 else [x]

The above solution returns the result as a list which you can later on .join() then apply int() to it.

Another idea that came to my mind is as simple as:

u = format(62, "08b")
>> 00111110
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Thanks! This is what I have been looking for. I'll try your samples out and see how far I can get though these codes contain a lot of new things I still need to learn. \$\endgroup\$ Jul 7, 2016 at 13:02
  • \$\begingroup\$ I strongly recommend you to start step by step. There's no hurry. You can start with this which is absolutely great. Good luck. And if you have questions, just ask. But don't forget, this is only for code reviewing. You can read our help section for more information \$\endgroup\$ Jul 7, 2016 at 13:04
  • \$\begingroup\$ Now that you have mentioned it, this line really seems to be redundant. The second comment looks interesting, didn't know that this notation also applied to the division operator. Besides that I'll try to use 4 spaces from now on. And thank you for providing the link. Looks like it covers a lot. \$\endgroup\$ Jul 7, 2016 at 13:13
  • \$\begingroup\$ Both quotient and reminder can be obtained at the same time using q, r = divmod(233,2) \$\endgroup\$
    – Vincent
    Aug 27, 2018 at 16:19
  • \$\begingroup\$ n%2 can be written as n & 1 which should be faster, same with n >> 1 instead of n // 2 \$\endgroup\$
    – Aemyl
    Feb 12, 2019 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.