Introduction
This is a solution to the question in the hard interview questions node. However, you need not go there if you simply read the following. The task is to convert a positive integer from base 2 to base minus 2. In both bases, all digits are either ones or zeros. For base 2, a one for the digit located n places from the right contributes 2n towards the value of a number. In base minus 2, a digit contributes (-2)n.
As this writeup is composed, there is already a solution to this problem posted above. However, the previous solution exhibits some peculiarities. It is terse and uncommented. It is in a slightly oddball language. And it's incomplete.
An interviewer gives hard interview questions to evaluate an interviewee's ability to think logically and her proficiency in some particular areas. Therefore, an ideal interviewee (from the interviewer's point of view) would improve her critical thinking abilities as well as her skills specific to the job. So this desirable interviewee would read these hard interview questions and work them out as a way to do that. The answers would hopefully provide either a confirmation of correctness to those who solve the problems or a thought path for those who could not solve the problem and require guidance. A terse answer as appears above fails to provide the second quality. Although an interviewee could go to the effort of memorizing all known questions and their unexplicated answers to appear competent in an interview, doing so would short change the interviewer and potentially run afoul if the interviewer invented new questions or dug deeper.
From the author's perspective, SML has oddball syntax. Never having seen SML code prior to this node, he can't say much of the language having learned only enough SML to read the solution. That said, the syntax it uses seems far removed from more familiar languages including BASIC, C, Java, Perl, and Lisp. Further, the program itself is bereft of comments or explanation. Its use of elegant polymorphism also impairs comprehension.
Finally, the statement of the problem appears to add a constraint which is unheeded in the previously given solution. That is, it is requested that an integer be converted. This implies an input of a fixed sized variable, likely 32 bits in length, and output of another variable with the same length. As will be shown below, a base minus 2 integer may require one more bit to store the same value as a base 2 integer. Granted, since the sample code gives the solution in a list of boolean values, it is at no risk of overflow. This makes the solution incomplete, but not really incorrect.
Meandering
Anyone interested enough to read this far has likely gone through the first few steps of thought on their own, but this solution intends to be complete. Please ignore any banality. Also, note that the author came to his solution in something of a roundabout manner, taking longer than an interviewer would likely allow. Therefore, view the below as an instruction in a way you might not want to think.
First, it is noted that all even1 powers of -2 are just powers of 2 since (-2)2n = (-1*2)2n = (-1)2n * 22n = ((-1)2)n * 22n = 1n * 22n = 22n. Secondly, all odd powers of -2 will be the negative of the corresponding power of 2 by similar logic.
This means that setting a bit in an odd number of places from the right in base minus 2 will decrease the represented number. For example, if one were to take 0101-2 (22 + 20 = 510) and set the bit one digit from the right, the result would be 0111-2 (22 - 21 + 20 = 310)). Therefore, the largest positive value that could be represented in 32-bit base minus 2 would be:
0101 0101 0101 0101 0101 0101 0101 0101-2 =
(-2)30 + (-2)28 + (-2)26 + (-2)24 + … + (-2)4 + (-2)2 + (-2)0 =
n=0∑1522n =
n=0∑154n = (geometric sequence)
1 - 4n+1
------- =
1 - 4
1,431,655,76510
Meanwhile, the largest positive value available in a signed 32-bit base 2 is 231-1 = 2,147,483,64810, which is 1.5 times the maximum value of base minus 2. Deviating from the question asked (probably not a good idea if actually solving this on an interview), the largest negative value is checked:
1010 1010 1010 1010 1010 1010 1010 1010-2 =
(-2)31 + (-2)29 + (-2)27 + (-2)25 + … + (-2)5 + (-2)3 + (-2)1 =
n=0∑15(-2)2n+1 =
-2*n=0∑1522n =
-2*n=0∑154n =
1 - 4n+1
-2 * ------- =
1 - 4
-2,863,311,53010
This compares with a maximum negative value of -231 = -2,147,483,64810 for a 32-bit integer. Calculating the range for both sets shows that both can represent 4,294,967,29610 distinct numbers, including 0. Therefore, a base minus 2 number is just as efficient for storing a number as a base 2 number, and there is a unique representation for every number in base minus 2. The important lesson learned here is that any proper base-2-to-base-minus-2 conversion routine should do a range check on an the input to insure it can be converted.
Planning
It is apparent that a number which can be represented as the sum of even1 powers of 2 is the same in base minus 2 as it is in base 2. e.g. 101012 = 10101-2. Therefore, a promising strategy would seem to simply convert all even powers of 2 in this fashion, then add any contribution made by odd powers of 2.
To convert odd powers of 2, one clearly needs to set more than one bit. At least one set bit needs to be an even power of 2, adding to the result, and at least one set bit needs to be an odd power of 2, subtracting from the result. We know that even if we set the bits of the even powers of 2 up to the odd power, that it will not sum to the desired result. This is known because in a base 2 number, setting bit n gives 2n while setting all bits from 0 to n-1 gives 2n-1. (And, if we didn't already know this, we could apply the closed form for a geometric sequence displayed above.)
Starting with the simplest case, we guess only two bits need to be set: one even power and one odd power. (If this strategy fails, we can then try 2, 3, and more bits.) The obvious candidate for the former is the bit for the power one greater than we are converting. Given 22n+1, we set the bit for (-2)2n+2 in the base minus 2 number. Next, we try to find what single bit needs to be set to subtract from this, to give us our original number. Let's call the position of that bit x.
22n+2 + (-2)x = 22n+1
(-2)x = 22n+1 - 22n+2
(-2)x = 22n+1(1 - 2)
(-2)x = -22n+1
x = 2n+1
That worked out quite easily! Therefore, to convert a bit representing an odd power of two, we need to set the same bit in the base minus 2 number as well as set the next bit. e.g. 213 = 8,19210 = 0010 0000 0000 00002 = 0110 0000 0000 0000-2 = 214 - 213
Next, we need to deal with circumstances in which the bit which an even numbered power intends to set is already set by the last odd power. e.g. 214 + 213 = 0110 0000 0000 00002 One's first impression might be to introduce a system of carries as would normally be used in addition. So, in the above case:
1
0000 0110 0000 0000 0000-2 = 213
0000 0100 0000 0000 0000-2 = 214
------------------------
0000 1010 0000 0000 0000-2 = -213 - 215
Whoops! That doesn't work, because when we carry a bit forward to an odd power of two, we have the same difficulty as when converting an odd power of two. That is:
(22n+2) + (22n+1) =
(22n+2) + (22n+2 - 22n+1) =
2*22n+2 - 22n+1 =
22n+3 - 22n+1 =
22n+4 - 22n+3 - 22n+1
Therefore, we should treat a carry in this case like its analagous conversion:
1 1
0000 0110 0000 0000 0000-2 = 213
0000 0100 0000 0000 0000-2 = 214
------------------------
0001 1010 0000 0000 0000-2 = 216 - 215 - 213
Finally, there is the occurrence of a cascaded carry, which is seen when we add 22n+1 + 22n+2 + 22n+3.
(22n+3) + (22n+2 + 22n+1) =
(22n+3) + (22n+4 - 22n+3 - 22n+1) = (substitution from above)
22n+4 - 22n+1
In this case, we see that, since the -22n+3 bit is already set, we merely have to clear this bit (which is decreasing the sum) to add the 22n+3 we desire. An example appears below, drawing from the previous conversion.
1
0000 0110 0000 0000 0000-2 = 213
0000 0100 0000 0000 0000-2 = 214
0001 1000 0000 0000 0000-2 = 215
------------------------
0001 0010 0000 0000 0000-2 = 216 - 213
This gives us a general sequence for converting numbers to base minus 2. We start on the rightmost digit with no carry in. For each digit, we set the outgoing digit if exactly one of the carry in or incoming digit is true. For even digits, the outgoing carry is set if both are true. For odd digits, the outgoing carry is set if either or both are true. Pseudo code to implement this appears below.
BASE_MINUS_2_INT_MAX = 1431655765;
if (integerToConvert > BASE_MINUS_2_INT_MAX)
throw OverFlowError(integerToConvert);
extract digitString from integerToConvert
isEven = true;
carry = false;
digitStack = < >;
for each digit in digitString
if (digit XOR carry)
digitStack.push('1')
else
digitStack.push('0')
endif
if (isEven)
carry = carry AND digit;
else
carry = carry OR digit;
endif
isEven = !isEven;
endfor
return digitStack;
Another Method
The observant reader, who may have already considered this solution too long and meandering, may note that each set of bits of 22n+1 and 22n+2 forms a simple counter which follows the sequence of:
base | base | base | Value
2 | minus | minus |
| 2 | 2 carry |
---------------------------------------
00 | 00 | 0 | 0
01 | 11 | 0 | 1 * 22n+1
10 | 10 | 0 | 2 * 22n+1 = 22n+2
11 | 01 | 1 | 3 * 22n+1 = 22n+1 + 22n+2
Therefore, after the first bit of 20, we can view the conversion process as a series of two bit conversions. First, 20 can be copied directly. Then, we process each remaining pair of bits in a loop. We begin with carry in to each step being clear. The carry out from each step becomes the carry in to the next step. The process would proceed by looking up the next set of base 2 digits in the above table. If carry in is set and the base 2 digits are '11', we set the carry out and write '00'. Otherwise, we copy down the base -2 value in the table, advancing one position down if carry in is set. Then, if the copied value is '01', we set carry out.
This is a perfectly feasible method for solving the problem, and should create identical results to the bit-at-a-time method. However, it should be noted that one could just as well build a table of four bit conversions with carry outs. Or eight bit conversions for that matter. And, while one is at it, a full 32-bit conversion table would be completely feasible, though tedious to compile. Therefore, a solution might appear as below:
if (isBase2Convertabile[base2Num])
return base2toBaseMinus2[base2Num];
else
throw overflowError(base2Num);
endif
Such a solution might be suboptimal if one's intention is to display his mathematical knowledge to an interviewer. In that case, write Θ(1) below the above code. That should do it.
SML Code Explained
As said above, the author is familiar with SML only in passing, so terminology may not be correct in this section. Of particular note is that one does not normally modify a variable in SML but creates a new variable which is created by applying a function to existing variables. Therefore, one does not "push a value onto the stack A", but "creates a new list composed of a value and the previous list A". The former terminology will be preferred below for clarity, and the difference is trivial for these purposes. This explanation is intended mostly to draw parallels between it and the C++ code below. As always, feel free to inform the author of any factual mistakes or misrepresentations in the below text.
The given SML code defines three functions named odd, f, and minus2. odd takes an integer and returns true if the number is odd or false otherwise. minus2 makes a call to f, which does most of the work, and then returns f's result.
f is a recursive, polymorphic function which takes four arguments in all of its forms. These four arguments are:
- n, an int, the remaining value to be converted
- evenp, a bool, whether the current digit represents an even1 power of two
- carry, a bool, whether there is a carry for this power of two
- acc, a bool list, a stack of the converted base minus 2 digits
f is composed of five lines whose purposes are displayed below:
- Returns the final built list when n is zero and the carry is zero. This is the base case except when line two is executed.
- Executes when the number to be converted is zero, and its purpose is to make sure an empty list is not returned. It returns a list composed of false and nothing else. (To be precise, it creates a new list which is composed of false followed by the existing list of bools. However, since the only occasion it could be called would be when the list is empty, this is redundant.)
- Finishes conversion when n is zero but carry bits remain to be written. It executes up to twice at the end of conversion, then calls line 1.
- Runs once for every odd power of two to be converted. Sets outgoing carry if the current bit to be converted is set or if incoming carry is already set. Adds true to the list if the current bit is set and there is no incoming carry or if the current bit is not set and there is an incoming carry. Divides n by two. Then calls lines 1, 3, or 5, depending on outgoing carry and n.
- Runs once for every even power of two to be converted. Sets outgoing carry if the current bit to be converted is set and incoming carry is already set. Adds true to the list if the current bit is set and there is no incoming carry or if the current bit is not set and there is an incoming carry. Divides n by two. Then calls lines 1, 3, or 4, depending on outgoing carry and n.
C++ Code Solution
/*
* File: baseminustwo.cpp
* Author: OldMiner
* Created: 2003 Jan 03
* Last Modified: 2003 Jan 04
*
* A simple conversion utility to convert a given
* number in base 2 to base minus 2.
*
* Written largely for a writeup on Everything2.com
*
*/
#include <stdlib.h>
#include <iostream>
#include <stdexcept>
#include <string>
using namespace std;
// 8 sets of the 4 bit sequence: 0101 (base 2 and minus 2)
// == 5 (base 10 and 16)
const unsigned int BASE_MINUS_2_INT_MAX = 0x00005555 + 0x55550000;
string convert(unsigned int convertMe) {
int digitPos = 33;
bool carry = false, evenDigit = true;
bool currentDigit;
char convertedDigits[33];
if (convertMe > BASE_MINUS_2_INT_MAX)
throw overflow_error("Exceeded maximum base minus two value.");
// Null-termine returned string
convertedDigits[--digitPos] = '\0';
do {
// Get current base 2 digit
currentDigit = convertMe % 2;
// Add a '0' or a '1' at the front of the existing string
convertedDigits[--digitPos] = '0' + (currentDigit ^ carry);
if (evenDigit)
carry &= currentDigit;
else
carry |= currentDigit;
// Move to the next base 2 digit
convertMe >>= 1;
evenDigit = !evenDigit;
// Continue till all base 2 digits have been converted
// and all carries written
} while (convertMe || carry);
return string(convertedDigits + digitPos);
}
int main(int argc, const char **argv) {
if (argc < 2) {
cerr << "Usage: " << argv[0] << " n" << endl;
return -2;
}
try {
string result = convert(atoi(argv[1]));
cout << "Amazingly " << argv[1] << " in base minus 2 is " <<
result << "!" << endl;
return 0;
}
catch (const overflow_error &overflew) {
cerr << "What's all this now?\n" << overflew.what() << endl;
return -1;
}
/* Should never get here */
return 0;
}
The above code was tested and found to compile and run fine using g++ 2.96 and g++ 3.2. Please report any difficulties encountered with compilation, comprehension, or style.
Example Usage
< baseminustwo 1431655765
Amazingly 1431655765 in base minus 2 is 1010101010101010101010101010101!
< baseminustwo 5
Amazingly 5 in base minus 2 is 101!
< baseminustwo 6
Amazingly 6 in base minus 2 is 11010!
< baseminustwo 24576
Amazingly 24576 in base minus 2 is 11010000000000000!
< baseminustwo 57344
Amazingly 57344 in base minus 2 is 10010000000000000!
< baseminustwo 150000000
Amazingly 150000000 in base minus 2 is 11001001100011101011010000000!
< baseminustwo 1500000000
What's all this now?
Exceeded maximum base minus two value.
<
C++ Code Explained
One subtlety in the above code is that convert takes an unsigned int. This will cast any negative number to a very large unsigned number, which will then be thrown out by the range check. Since the problem only asks that positive integers be converted, this should be a sufficient solution.
The do...while loop in the C++ code is equivalent to the SML code above it. The base case occurs when the while condition fails; the value to be converted is zero, and no carries remain. At that point, the built string is returned. There is no need for a second base case like line 2 in the SML code. Because the loop is always run at least once, zero is added to the string without any extra logic. Line 3 of the SML code is mirrored in the while condition. For most runs through the do...while loop, the value to be converted will be non-zero, so the carry is not checked. This is the same as the alternating between lines 4 and 5 in the SML code. Once the value to be converted becomes zero, the carry is checked, and the loop continues till the carry is cleared. The innards of the loop constantly add the next digit to the string to be returned, set the carry, and halve the value to be converted, just as in lines 4 and 5 of the SML code. The remainder of the code is ultimately packaging for this procedure.
Footnote(s)
1: In this writeup,
even indicates all numbers evenly divisible by two
as well as zero. This is done to reduce wordiness.