Last active
April 21, 2024 15:11
-
-
Save orlp/3551590 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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, | |
}; | |
int64_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; | |
} | |
} |
the lookup table for highest bit set can be replaced with __builtin_clz
if it is available (gcc, clang). It will make it faster (especially if the lookup table is not in cache, which is likely in a real-world application doing other things than that) and smaller.
Simply replace highest_bit_set[exp]
with (exp>0) ? 32 - __builtin_clz(exp) : 0
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@MOJNICK If
highest_bit_set
is non-static, the code initializes the array contents every time the function is called, so it is slower than the static version.