The Database Managers, Inc.

Contact The Database Managers, Inc.


Use an RSS enabled news reader to read these articles.Use an RSS enabled news reader to read these articles.

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;
}

Listing D: Detect the size of an integer

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>();
}

Q2) Multiply an integer by 8 without using multiplication or addition.

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
Jump to Questions Page:  1  2  3  4  5  6  7  8  9  10  11  12  13 
 
Jump to Answers Page:  1  2  3  4  5  6  7  8  9  10  11  12  13 
Services | Programming | Contact Us | Recent Updates
Send feedback to: