Create a gist now

Instantly share code, notes, and snippets.

@orlp /ipow.c
Last active Apr 17, 2018

What would you like to do?
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

This comment has been minimized.

Show comment Hide comment
@woodb

woodb Nov 17, 2013

That's some really pretty code, nice work.

woodb commented Nov 17, 2013

That's some really pretty code, nice work.

@holtdoa

This comment has been minimized.

Show comment Hide comment
@holtdoa

holtdoa Jan 5, 2016

Pretty slick.

holtdoa commented Jan 5, 2016

Pretty slick.

@Jabro

This comment has been minimized.

Show comment Hide comment
@Jabro

Jabro Aug 11, 2016

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

Jabro commented Aug 11, 2016

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

This comment has been minimized.

Show comment Hide comment
@prakharsingh95

prakharsingh95 Sep 5, 2016

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

prakharsingh95 commented Sep 5, 2016

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

@mmdts

This comment has been minimized.

Show comment Hide comment
@mmdts

mmdts Apr 15, 2017

Prakhasingh95, that would prove pointless. The point of this function is that it is so fast, that would just slow it down.

mmdts commented Apr 15, 2017

Prakhasingh95, that would prove pointless. The point of this function is that it is so fast, that would just slow it down.

@KevinTyrrell

This comment has been minimized.

Show comment Hide comment
@KevinTyrrell

KevinTyrrell Jun 9, 2017

A lot of repetitious code here. if (exp & 1) result *= base; is written six times, only needs to be written once. Also the array will be created and destroyed every function call which has overhead. You can move it outside the function header to prevent it from being continuously re-instantiated.

A lot of repetitious code here. if (exp & 1) result *= base; is written six times, only needs to be written once. Also the array will be created and destroyed every function call which has overhead. You can move it outside the function header to prevent it from being continuously re-instantiated.

@ian-abbott

This comment has been minimized.

Show comment Hide comment
@ian-abbott

ian-abbott Aug 30, 2017

@kevintyrell The code repetition is to optimize for speed. The array is static so will not be created and destroyed at every function call. The placement of the array within the function merely limits its static scope to that function.

@kevintyrell The code repetition is to optimize for speed. The array is static so will not be created and destroyed at every function call. The placement of the array within the function merely limits its static scope to that function.

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