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.
**

## 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.

Subscribe to:
Posts (Atom)