THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  Dec2Bin().  This useful function takes a denary integer as its argument (a number in base 10 without a decimal part) and converts it into the binary form (base 2).

The returned binary number is in string format for two reasons.  Firstly, binary numbers are physically a lot longer than their denary form, and, since IBasic would believe a number such as 10100100011001 etc is denary, could cause an overflow (too big for an integer type).  Secondly, the function assembles its output in string format anyway, so no conversion is necessary.

This code will only do conversions up to the maximum possible value of its argument. So, when declaring Dec2Bin(), its arguments must be declared as type integer (int). See the table below for the limits.

Type

Exponent of 2
Value

int 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 4611686018427387904


Declaring the function must be done like this:

declare Dec2Bin(d: int) (or whatever type of integer you choose).

Here's the code:


sub Dec2Bin(d)
' Converts argument d from denary
' into binary and returns binary
' value. Input must be of integer
' type.  Output will also be of
' string type.
def bin$, temp$: string
bin$ = "": 'initialise bin$
do
    if d % 2 = 0: 'no remainder
        temp$ = "0"
    else: 'must be a remainder
        temp$ = "1"
    endif
    bin$ = temp$ + bin$: 'concatenate
    d = d /2: 'chop off LSD
until d = 0: 'every digit processed
return bin$   

Here's the code, and, inset, a simple flowchart describing the algorithm it uses:

sub Dec2Bin(d)
' Converts argument d from denary
' into binary and returns binary
' value. Input must be of integer
' type.  Output will also be of
' string type.
def bin$, temp$: string
bin$ = "": 'initialise bin$
do
    if d % 2 = 0: 'no remainder
        temp$ = "0"
    else: 'must be a remainder
        temp$ = "1"
    endif
    bin$ = temp$ + bin$: 'concatenate
    d = d/2: 'chop off LSD
until d = 0: 'every digit processed
return bin$  
FlowChart

Overview:  the algorithm employed, shown above right, is the classic one used for this function. The argument is successively divided by two until it is reduced to zero. Just before each division, it's tested to find out if it's an odd number or even.

If even, a zero is saved, otherwise a one.  Each saved number is concatenated with what has already been saved, right-to-left.  This eventually produces a full binary representation of the argument itself, ready to be returned to the calling routine.

Here's an example of converting 29 to binary.

Argument
Odd/Even
Digit to Save
Saved String
Argument/2
29
odd
1
"1"
14.5
14
even
0
"01"
7.0
7
odd
1
"101"
3.5
3
odd
1
"1101"
1.5
1
odd
1
"11101"
0.75
0


"11101"

You can see how this was derived by following the flowchart. After each division by two, the decimal part is discarded and we have a new, integer argument. Each time a digit is saved to the string, it's tacked onto the left of the existing string. As the argument gets smaller, the string gets larger. This goes on until the argument shrinks to zero, when the process is complete.

Let's take a look now at the variables.

The function's argument is d, an integer in denary or base 10 format. The purpose of the function is to convert d into binary or base 2 format and return the binary value to the calling routine.

bin$ is created to build up the string that will eventually be returned to the calling routine. Not surprisingly, this is an abbreviation for "binary string."  Note that it's set to be empty before the code starts to do anything by the line
bin$ = "".  This ensures that no random data will be accidentally added onto the final result.

temp$ is used to hold the ones and zeroes to be added to
bin$. This value can change every time around the loop.

The next half dozen lines of code do all the work.  I've numbered them to make explanations simpler.

1
2
3
4
5
6
7
8
9
10

do
    if d % 2 = 0: 'no remainder
        temp$ = "0"
    else: 'must be a remainder
        temp$ = "1"
    endif
    bin$ = temp$ + bin$: 'concatenate
    d = d/2: 'chop off LSD
until d = 0: 'every digit processed
return bin$   

Let's look at the above code in detail now.

1

do.  The main DO loop is opened.

2

if d % 2 = 0.  This line is really asking "Is argument d an even number?"  It works this way: the expression d % 2 is integer arithmetic. It means "Divide d by 2 and retain the remainder while discarding the rest of the result."

If d = 7, d % 2 = 1; if d = 3286, d % 2 = 0.  You can see that the answer will always be either 1 or 0, corresponding to d being either odd or even.

So the expression really is asking if d is an even number. Note that it doesn't actually change d's value. It only asks "IF d is an even number ..."

3

temp$ = "0".  The code will only execute this line if it found d was an even number.  In this case, it will remember it by saving a "0" in temp$.

4

else.  This is an alternative.  It instructs the code what to do if d isn't an even number. It means in effect, execute the next line, 5.

5

temp$ = "1".  The code will only execute this line if it found d was an odd number.  In this case, it will be remembered by saving a "1" in temp$.

6

endif.  Housekeeping - closes IF-ENDIF clause.

7

bin$ = temp$ + bin$.  This line is executed regardless of whether d is an even or an odd number, because the appropriate action is recorded in temp$

We want to tack whatever is in temp$ to the left of whatever is currently in bin$. For example, if
temp$ contains, say, "1", and bin$ contains, say, "00011" then this line will change bin$ to contain "100011".

8

d = d/2.  Now we want to divide d by 2 ready for the next assessment of odd- or even-ness.  And we need to discard any decimal part.  How is that accomplished?

When we declared the function, we also declared d as an integer, and integers don't have decimal parts.  Assume d has value 13.  The result of d/2 would normally be 6.5, but, because d is an integer, the result is 6 - another part of integer arithmetic.

9

until d = 0.  The last thing we did to d was to divide it by 2. If we keep doing this, it will eventually be whittled away to zero. Line 9 is effectively saying "if the last division of argument d reduced it to zero, quit the DO loop, otherwise execute it again."

10

return bin$.  Once the DO loop is exited, the process is complete.  All that remains to do is to return whatever has accumulated in bin$ to the calling routine.


MAIN MENU
HOW DOES IT WORK?

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 4th, 2010.