Skip to content

Instantly share code, notes, and snippets.

@orlp
Last active Jan 14, 2022
Embed
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,
};
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;
}
}
@woodb
Copy link

woodb commented Nov 17, 2013

That's some really pretty code, nice work.

@holtdoa
Copy link

holtdoa commented Jan 5, 2016

Pretty slick.

@Jabro
Copy link

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
Copy link

prakharsingh95 commented Sep 5, 2016

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

@mmdts
Copy link

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
Copy link

KevinTyrrell commented 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.

@ian-abbott
Copy link

ian-abbott commented 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.

@brdann
Copy link

brdann commented Aug 4, 2018

That's cool! But it computes unsigned int64_t and returns signed int64_t, what I'm missing?

@shengyang998
Copy link

shengyang998 commented Nov 27, 2018

@brdann Yeah, I think it should return signed.
Whatever it is, signed or unsigned, somehow the answer is wrong on my device.

// I got it. The int64_t doesn't work. Change to long long did solve it.

@WarpspeedSCP
Copy link

WarpspeedSCP commented Feb 4, 2019

I feel like I'm missing something. There aren't any loops here. Does the function have to be called recursively?

@XMB5
Copy link

XMB5 commented Feb 13, 2019

The switch cases fall through

@alejandro-colomar
Copy link

alejandro-colomar commented Mar 17, 2019

You should check for overflow, because squaring base without any checks is asking for trouble. ipow(INT64_MAX, 2) invokes Undefined Behavior. ipow(3, 63) also invokes UB.

@alejandro-colomar
Copy link

alejandro-colomar commented Mar 17, 2019

For the code repetition I would make a static inline function, which avoids repetition, but keeps performance

@Clemapfel
Copy link

Clemapfel commented May 30, 2020

this can easily be made constexpr / consteval by moving highest_bit_set into the same namespace as the function and making that constexpr too which I recommend as it would be in the spirit of optimal runtime

@Zorgatone
Copy link

Zorgatone commented Nov 15, 2021

@orlp

Does this work with uint64_t as well?
Do I need to add elements to highest_bit_set past exponent 63?

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