# C++/help plz

Question
hi
what should i do for solving this problem?

#include<stdio.h>
int hanoi(int n);
void main(){
int n;
scanf("%d",&n);
hanoi(n);
printf("%d\n",hanoi(n));
}
int hanoi(int n){
if(n!=1)
return (1+2*hanoi(n-1));
return 1;
}

thanx
bita

You have not appreciated the fact that numbers - either integer or floating point - held by computers are _not_ infinite. Yes you can use big number libraries, but in this case you are using a plain int to hold values which you multiply by 2.

The int built in type is of a bit-length that is natural for the processor the compiled code is targeted to run on. In this case I would guess that it is a 32-bit value. As int is signed the useful range of positive values is one less than 2 to the 31st power (or 31 one bits). Hence I think your program will not work with n > 31 (or n < 1 for that matter - you might try passing 0 for n to your hanio function - I'd start by doing it in your head using paper and pen or pencil to keep track of the values at first if I were you).

Each time you multiply a value by two you add one to the number of binary digits required to hold it. Thus 1 requires 1 bit to represent, 1*2 (==2) requires 2 bits, 2*2 (==4) requires 3 bits and so on. Hence by the time you have done this 31 times you are running out of bits in your int. In fact you run out when n=32. But for a twos complement signed values of 32 bits in length when the top (32nd) bit is set the value is negative, with -1 represented by all 1 bits. If you are unfamiliar with twos complement representation and arithmetic then you might like to read up on it (e.g. see http://en.wikipedia.org/wiki/Two%27s_complement). I suggested signed integers are held in twos complement as this is the norm for most (if not all) popular modern desktop computer systems, as is 32-bits for the size of C and C++ int types.

[Note:

C and C++ do not mandate the bit length of the supported built in integer types, only that sizeof(char)==1 - which does not mean char is 8-bits long necessarily - and that sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) and the bit length of the unsigned equivalent for each integer type is the same as its signed counterpart.

However, most compilers for 32-bit code for byte addressed machines, which covers a majority of current desktop and server platforms have the following sizes for the integer types:

sizeof(char ) == 1 (by definition) and is 8-bits in length
sizeof(short) == 2 and is 16-bits in length
sizeof(int  ) == 4 and is 32-bits in length
sizeof(long ) == 4 and is 32-bits in length

For the newer 64-bit architectures there are various schemes. The one used by Microsoft, called LLP64, keeps all C89/C++98 standard integer types the same as the 32-bit model above, but allows an int64 or long long type and pointers to be 64 bits in size (hence LLP64 - Long Long and Pointers 64 bits). Un*x like systems however tend to use the LP64 (long and pointers 64 bits). See for example http://www.unix.org/whitepapers/64bit.html for more in this issue. The long long int type was added to the ISO C99 standard and will probably also be part of the next version of the ISO C++ standard.

-- end note]

Your code returns a value having n one bits set. When this reaches 32 you have the 2s complement -1 value. When you try 33 or greater the additional bits "fall off" the end when multiplied by 2, you then add 1 to restore the lower bit thus keeping the returned value at 32 1 bits - or -1. To test this I wrapped your hanio function up in some code to see what value it returned for various values of n using MS VC++ 2008 - which has 32-bit twos complement signed ints. Here are the results:

For n=29 the hanio function returns: 536870911
For n=30 the hanio function returns: 1073741823
For n=31 the hanio function returns: 2147483647
For n=32 the hanio function returns: -1
For n=33 the hanio function returns: -1
For n=34 the hanio function returns: -1

You can get 1 more bit (i.e. n=32 should return the correct result) by using unsigned int rather than int as then all 32-bits are for positive values. Doing this in my test program returned the following results:

For n=29 the hanio function returns: 536870911
For n=30 the hanio function returns: 1073741823
For n=31 the hanio function returns: 2147483647
For n=32 the hanio function returns: 4294967295
For n=33 the hanio function returns: 4294967295
For n=34 the hanio function returns: 4294967295

To make use of even greater values you would need to use a larger integer - e.g. a 64-bit integer if supported by your compiler (this may be long long, int64, __int64, or for some compilers for 64-bit processors long or even int, and their unsigned counter parts - you will have to check out your compiler's specification to see what it supports). For even greater precision you could use an arbitrary precision arithmetic library that supported large integer types - see http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic for some information on arbitrary precision arithmetic and examples of libraries.

Of course if you continue to use C you will have to use custom I/O procedures to use these values (I think some libraries may allow values to be converted to and from string values however) as printf / scanf etc. will not know about these types. If using C++ some such C++ libraries provide custom IOStream insertion and extraction operators (operator<< and operator>>).

Of course if using an integer is only a convenience and you do not need to do arithmetic on the result you could re-write your function to work with strings. In this case each time you call hanio you would append '1' (the character one, not the value 1) to a string. Remember, if using C that C style strings are just arrays and _you_ are responsible for making sure you do not cause your code to exceed the limits of the available space - and remember that C strings are arrays of char with a terminating zero character and storage space is required for this terminator.

In C++ I would also consider using a std::vector<bool> or a std::bitset or even a boost::dynamic_bitset (see http://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html, one of the Boost libraries for C++, see http://www.boost.org/).

Hope this helps.

Questioner's Rating
 Rating(1-10) Knowledgeability = 10 Clarity of Response = 10 Politeness = 10 Comment thanx,really thanx for your complete answer

C++

Volunteer

#### Ralph McArdell

##### Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

##### Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials