Search code examples
crsatraversalexponentiation

Iterate bits from left to right for any number

I am trying to implement Modular Exponentiation (square and multiply left to right) algorithm in c.

In order to iterate the bits from left to right, I can use masking which is explained in this link In this example mask used is 0x80 which can work only for a number with max 8 bits.

In order to make it work for any number of bits, I need to assign mask dynamically but this makes it a bit complicated.

Is there any other solution by which it can be done.

Thanks in advance!

-------------EDIT-----------------------

    long long base = 23;
    long long exponent = 297;
    long long mod = 327;

    long long result = 1;

    unsigned int mask;

    for (mask = 0x80; mask != 0; mask >>= 1) {

         result = (result * result) % mod;  // Square

         if (exponent & mask) {
            result = (base * result) % mod; // Mul
         }
    }

As in this example, it will not work if I will use mask 0x80 but if I use 0x100 then it works fine. Selecting the mask value at run time seems to be an overhead.

Solution

  • If you want to iterate over all bits, you first have to know how many bits there are in your type.

    This is a surprisingly complicated matter:

    • sizeof gives you the number of bytes, but a byte can have more than 8 bits.
    • limits.h gives you CHAR_BIT to know the number of bits in a byte, but even if you multiply this by the sizeof your type, the result could still be wrong because unsigned types are allowed to contain padding bits that are not part of the number representation, while sizeof returns the storage size in bytes, which includes these padding bits.

    Fortunately, this answer has an ingenious macro that can calculate the number of actual value bits based on the maximum value of the respective type:

    #define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
                  + (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

    The maximum value of an unsigned type is surprisingly easy to get: just cast -1 to your unsigned type.

    So, all in all, your code could look like this, including the macro above:

    #define UNSIGNED_BITS IMAX_BITS((unsigned)-1)

// [...]

unsigned int mask;
for (mask = 1 << (UNSIGNED_BITS-1); mask != 0; mask >>= 1) {
    // [...]
}

    Note that applying this complicated macro has no runtime drawback at all, it's a compile-time constant.