Iterate bits from left to right for any number

Question

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.

Define maximal number, like `size_t` is your maximal value you will proceed. Then, to get mask, use `size_t mask = ((size_t)1 << (sizeof(size_t) * 8 - 1))`. Later, to traverse your number, use `size_t mynum = (size_t)input_number` and that's it. I assume you use unsigned numbers only. — unalignedmemoryaccess, Jun 23 '17 at 09:59
@tilz0R this method is actually unsafe. 1.) `CHAR_BIT` can be a bigger value than `8` 2.) even when using `CHAR_BIT`, the calculation could go wrong if your type has padding bits. -- for a correct solution to calculate the number of bits [see this answer](https://stackoverflow.com/a/4589384/2371524). — , Jun 23 '17 at 11:16
@tilz0R `CHAR_BIT` is defined in `limits.h` to the number of bits in a byte (aka `char`). Its very often `8`, but can be bigger. — , Jun 23 '17 at 11:18
@FelixPalmen You really think, that char may be bigger than 8-bits in C? — unalignedmemoryaccess, Jun 23 '17 at 11:20
@tilz0R You really think it can't? Hint: read the standard. And yes, there are actual machines with bytes wider than 8 bits. — , Jun 23 '17 at 11:22
Then multiply by `8` change to `CHAR_BIT` and problem is solved. — unalignedmemoryaccess, Jun 23 '17 at 11:25
@tilz0R no, it isn't, because of possible padding bits. See my answer. — , Jun 23 '17 at 11:28
If you used a right-to-left algorithm, you wouldn't need to worry about initializing the mask to a suitably large value. — Ian Abbott, Jun 23 '17 at 13:19
@IanAbbott Agree, but in my case I need left-to-right algorithm. — TechJ, Jun 23 '17 at 13:57

score 4 · Accepted Answer · 2017-06-23T13:19:43.943

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.

Interesting link, but since the bit-shifting operators work on values, not underlying representations, the padding bits are irrelevant. — ad absurdum, Jun 23 '17 at 12:24
@DavidBowling the operators work on values and this is the reason WHY the padding bits are very relevant. Using `sizeof(unsigned) * CHAR_BIT` would give you the storage size, *including* padding bits, so if there are padding bits, doing `1 << (sizeof(unsigned) * CHAR_BIT - 1)` would trigger undefined behavior, it shifts too far. The macro is for determining the number of actual value bits. — , Jun 23 '17 at 12:27
@DavidBowling still a good comment because now, I see how one could misread my answer. I'll improve the wording. — , Jun 23 '17 at 13:18
Well, I should have read more carefully, but your change does make the issue more clear. Already upvoted. The link is nice, so thanks for that :) — ad absurdum, Jun 23 '17 at 13:52

chqrlie · Answer 2 · 2017-06-23T15:27:25.787

Your algorithm seems unnecessarily complicated: bits from the exponent can be tested from the least significant to the most significant in a way that does not depend on the integer type nor its maximum value. Here is a simple implementation that does not need any special case for any size integers:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
    unsigned long long base     = (argc > 1) ? strtoull(argv[1], NULL, 0) : 23;
    unsigned long long exponent = (argc > 2) ? strtoull(argv[2], NULL, 0) : 297;
    unsigned long long mod      = (argc > 3) ? strtoull(argv[3], NULL, 0) : 327;
    unsigned long long y = exponent;
    unsigned long long x = base;
    unsigned long long result = 1;

    for (;;) {
        if (y & 1) {
            result = result * x % mod;
        }
        if ((y >>= 1) == 0)
            break;
        x = x * x % mod;
    }
    printf("expmod(%llu, %llu, %llu) = %llu\n", base, exponent, mod, result);
    return 0;
}

Without any command line arguments, it produces: expmod(23, 297, 327) = 185. You can try other numbers by passing the base, exponent and modulo as command line arguments.

EDIT:

If you must scan the bits in exponent from most significant to least significant, mask should be defined as the same type as exponent and initialized this way if the type is unsigned:

 unsigned long long exponent = 297;
 unsigned long long mask = 0;
 mask = ~mask - (~mask >> 1);

If the type is signed, for complete portability, you must use the definition for its maximum value from <limits.h>. Note however that it would be more efficient to use the unsigned type.

 long long exponent = 297;
 long long mask = LLONG_MAX - (LLONG_MAX >> 1);

The loop will waste time running through all the most significant 0 bits, so a simpler loop could be used first to skip these bits:

 while (mask > exponent) {
     mask >>= 1;
 }

Thanks for your answer, but this is the `right to left` implementation of the algorithm. In my case the requirement is implementing the algorithm from `left to right`. — TechJ, Jun 23 '17 at 15:12

Iterate bits from left to right for any number

2 Answers2