## Saturday, January 30, 2010

### Rounding An Integer To The Next Maximal Mutliple Of A Given Radix Power

Let be the modulo- representation of an integer , where each is a symbol/digit corresponding to values . Often we are encountered with problems where we need to find smallest integer such that (i.e. divides without any reminder), where . Some of the very common applications include rounding the number of bits required to represent a data structure to the nearest byte (i.e. power of ). Before we see how to address this problem its worth while to understand the following interesting property of modulo representation. Given a modulo- representation of we can get corresponding modulo- representation of by replacing every group of digits (in modulo- representation), by the corresponding digit (i.e. ) in modulo-. For instance if we would like to convert an integer in binary (i.e. ) representation to hexa-decimal representation (). We start from left to right and replace every bits with the corresponding digit in hexa-decimal system. For example if we see we will replace it with digit , by and so on. So the hexa-decimal system is providing us with a one-one function for every bit string, in fact we can use any one-one function here when we move for modulo representation to modulo . However the one-one function has become a standard for module system.

So coming back to our original problem given the modulo- representation , we would like to round to , where is the smallest multiple of such that . To accomplish this task we need to examine the first (from right) digits in the modulo- representation of . In fact the value of in those bits is the reminder we get when we divide by , so if is the value in those bits then . When we can elegantly use the bit-wise operators to accomplish this. So if some one gives an integer and ask to find a smallest which is a multiple of then we use the following C-statement to accomplish this . Where are the standard bit-wise operators in C.