Create a gist now

Instantly share code, notes, and snippets.

@orlp /ipow.c
Last active Sep 6, 2016

int64_t ipow(int64_t base, uint8_t exp) {
static const uint8_t highest_bit_set[] = {
0, 1, 2, 2, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 255, // anything past 63 is a guaranteed overflow with base > 1
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255,
};
uint64_t result = 1;
switch (highest_bit_set[exp]) {
case 255: // we use 255 as an overflow marker and return 0 on overflow/underflow
if (base == 1) {
return 1;
}
if (base == -1) {
return 1 - 2 * (exp & 1);
}
return 0;
case 6:
if (exp & 1) result *= base;
exp >>= 1;
base *= base;
case 5:
if (exp & 1) result *= base;
exp >>= 1;
base *= base;
case 4:
if (exp & 1) result *= base;
exp >>= 1;
base *= base;
case 3:
if (exp & 1) result *= base;
exp >>= 1;
base *= base;
case 2:
if (exp & 1) result *= base;
exp >>= 1;
base *= base;
case 1:
if (exp & 1) result *= base;
default:
return result;
}
}
@woodb

That's some really pretty code, nice work.

@holtdoa

Pretty slick.

@Jabro
Jabro commented Aug 11, 2016 edited

Pretty cool!
There is one bug though, if you call it e.g. with base = 16 and exponent = 8, the int32_t base will overflow --> as 16^8 = 2^32 --> function will return 0 instead of 2^32

Either pass as int64_t or use a temporary variable with 64 bits

@prakharsingh95
prakharsingh95 commented Sep 5, 2016 edited

You can calculate highest set bit as i <= 64 ? (int)(log10(i)/log10(2)) : 255.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment