C++ Problem Solving

by Curtis Krauskopf

There are usually many ways to solve any programming problem. The solutions provided here are examples and are not necessarily the best -- but they do work.

When creating your solution for any problem-solving type question, remember to test edge-cases -- such as when there are zero, one or an infinite number of possibilities.

Q1) Find the size of an integer data type without using sizeof() function.

A1) Listing D is an example of one solution. What is not mentioned in the question is if the integer data type is signed or unsigned. Does your solution work for both? For edge-case support, we can assume that the integer data type has at least one bit because a 0-bit integer data type is pretty useless. Does your solution work for 1 or 2 bit integers, or did you assume that integers were a multiple of 8 bits?

#include <stdio.h>

template< typename IntType >
int numberOfBits() {
  IntType newValue = 1;
  IntType oldValue = 0;
  int numBits = 0;
  while(oldValue != newValue) {
    ++numBits;
    oldValue = newValue;
    newValue = (newValue << 1) + 1;
  }
  return numBits;
}

int main(int argc, char* argv[]) {
  printf("sizeof(int)  : %d\n", sizeof(int) * 8);
  printf("size of <int>: %d\n", numberOfBits<int>());
  printf("\n");
  printf("sizeof(unsigned int)  : %d\n", sizeof(unsigned int) * 8);
  printf("size of <unsigned int>: %d\n", numberOfBits<unsigned int>());
  printf("\n");
  printf("sizeof(short)  : %d\n", sizeof(short) * 8);
  printf("size of <short>: %d\n", numberOfBits<short>());
  return 0;
}

Update: March 20, 2011 A decompile.com reader, Ján Staník, has submitted the following alternate solution. The solution in Listing D did not assume there are 8 bits per byte but Ján's solution does assume there are 8 bits per byte. However, Ján's solution provides an O(1) solution whereas the solution in Listing D is an O(n) solution. I think it's useful to examine why his solution works because it makes a clever use of arrays and it calculates the distance between array elements in a template function. The only change I made to his solution was to format it to stay within the minimum page width of this website. #include <iostream> template <typename T> void SizeOf() { T a[2]; std::cout << "sizeof() = " << 8 * sizeof(T) << std::endl; std::cout << "SizeOf<> = "; std::cout << 8 * (((long int)((T*)a+1)) - ((long int)(T*)a)); std::cout << std::endl; } int main( ) { SizeOf<unsigned int>(); }

A2) The key to the answer to this question is knowing about the shift operator and how it relates to the integer's internal representation. The following code snippet answers this question:

int x = 3;
x = x << 3;

Previous Answers

More C++ Answers