THE PUZZLET PAGE


How_Does_It_Work


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

Declaring the function must be done like this:

declare Dec2Bin(b$: string).


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

sub Bin2Dec(b$: string)
' Argument b$ must be a binary
' number
in string format. It's
' converted to
denary and returned
' as an integer.

def den, i, L: int
L = len(b$)
den = 0
for i = 1 to L
    if mid$(b$, i, 1) = "1"
        den = den + 2^(L - i)
    endif
next i
return den

FlowChart

Overview:  the algorithm employed, shown above right, is the classic one used for this function. It relies on positional powers. That is, the power to which any digit of an integer needs to be raised is directly related to the position of the digit within the integer.

The argument is in string format, so it's a simple matter to use string-slicing to extract each digit in turn and process it.

Here's an example of converting "1011011" to denary.  Note that digits are dealt with from LSD (least significant, or rightmost, digit) to MSD (most significant, or leftmost, digit).  In the code exegesis which follows, digits are dealt with in the opposite order.

Digit nr
(from right)
Digit
Value
Raise To
Power
New
Value
Running
Total
1
1
0
1 x 20 = 1
1
2
1
1
1 x 21 = 2
3
3
0
2
0 x 22 = 0
3
4
1
3
1 x 23 = 8
11
5
1
4
1 x 24 = 16
27
6
0
5
0 x 25 = 0
27
7
1
6
1 x 26 = 64
91

You can see how this was derived by following the flowchart. Every digit is dealt with in turn from the right.  If its value is zero, it's ignored. If its value is 1, it's raised to the appropriate value and added to the running total already stored.

Let's take a look now at the variables.

The function's argument is b$, short for "binary string." It holds the binary or base 2 format number as a string, which is to be converted into denary or base 10 format. The purpose of the function is to convert b$ into denary or base 10 format and return the denary value to the calling routine.

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

Variable i is used as a pointer, pointing to each character in b$ in turn for conversion to its denary value.

Variable L holds the length of b$. This enables the loop to recognise when it has processed all the characters and stop in a timely manner. It's also used along the way to figure out exactly what power to raise each individual digit to.

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

L = len(b$)
den = 0
for i = 1 to L
    if mid$(b$, i, 1) = "1"
        den = den + 2^(L - i)
    endif
next i
return den
 

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

1

L = len(b$).  The length of b$ is worked out and saved in variable L for use within the FOR-NEXT loop (lines 3 and 5).

2

den = 0.  Initialises variable den to zero, preparatory to its use within the FOR-NEXT loop (lines 5 and 8).

3

for i = 1 to L.  The main FOR-NEXT loop is opened.  Variable i is the iterator, going from 1 to L in value.  L holds the length of b$, that is, the number of characters to be processed, so this automatically ensures that each and every digit is processed.

4

if mid$(b$, i, 1) = "1".  This line is really asking "Is the character being pointed to by the current value of variable i a one?"  For example, if b$ holds "101001" and i holds 4, the fourth character from the left is being pointed at. In these circumstances, the answer to the question is "no."

5






den = den + 2^(L - i).  The code will only ever execute this line if the answer to the question in line 4 is "yes",  that is, the current character is a one.  If it's a zero, the line is skipped over.

When it's a one, action must be taken as it means the character has a value in binary that must be converted to denary and added to the running total.

There's a precise relationship between the value of i (which represents the position from the left of b$ of the character being examined) and the power to which that character must be raised.




The inset graph shows how a simple formula for the i-L-b$ relationship  has been derived.
The power is always L - i.
Graph

6

endif.  Housekeeping - closes IF-ENDIF clause.

7

next i.  Housekeeping - part of the FOR-NEXT loop syntax.

8

return den.  Once the code reaches this line, the process is complete.  All that remains to do is to return whatever has accumulated in den to the calling routine.


MAIN MENU
HOW DOES IT WORK?

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