Start working on charm

1 files changed, 76 insertions, 0 deletions

diff --git a/ipow.h b/ipow.h
new file mode 100644
index 0000000..62ba416
--- /dev/null
+++ b/ipow.h
@@ -0,0 +1,76 @@
+//SOURCE: https://gist.github.com/orlp/3551590
+int64_t ipow(int32_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;
+    }
+}