[CODE]//Number of bits to the right of leading ones bit.
leading_zeros = leadz(n);
nbits = 8*sizeof(n)-leading_zeros;

// Left-justify n and shift leftmost bit off.
n <<= (leading_zeros + 1);
[/CODE]So if I don't have a function leadz(), will this work instead?
[CODE]if(n == 0)
return 1;

[B]while (n>0) n << 1;
n << 1;
[/B]
r = a;

// Assumes the loop will not get executed if nbits < 1:
for(i = 1; i < nbits; i++)
{
r = (r*r)%p;
// If current (i.e. leftmost) bit = 1, multiply by a:
if(n < 0)
r = (a*r)%p;
// left-shift the exponent:
n <<= 1;
}
return r;[/CODE]

Here is a version of "left-to-right modular binary exponentiation" that has been kicking around the forum for quite a while.[CODE]powmod(a, b, m) {

if (b == 0) return 1;

mask = 1<<31; // can be adjusted for integer size: 1<<63
while ((b & mask) == 0) mask >>= 1;
mask >>= 1;

r = a;

while (mask) {
r = (r * r) % m;
if (b & mask) {
r = (r * a) % m;
}
mask >>= 1;
}
return r;
}
[/CODE]