Two's complement unexpectedly shows up in infinite series ========================================================= [Published 2022-10-20, Updated 2023-01-25] I recently discovered that you can divide by a number x by calculating an infinite series that divides by x+1. Here is an example: 7/5 = 7/(6) + 7/(6*6) + 7/(6*6*6) + ... This may be well known but I only knew about the special case of: x = x/2 + x/4 + x/8 + ... until recently. On a computer it may be especially interesting to divide by a power of 2 minus 1 since you can then divide by e.g. 8 instead of the more difficult number 7. All you need to do is to bit shift: 500/7 = (500 >> 3) + (500 >> 6) + (500 >> 9) + ... which is equivalent to 500/7 = 500/8 + 500/8/8 + 500/8/8/8 + ... There is just a slight problem; this doesn't give you the whole result when using integers because you miss the fractional parts. Here is a more complete example: // Calculates `dividend / ((1 << divisor_exponent) - 1)` void divide(int dividend, int divisor_exponent, int *res, int *rem) { int divisor = (1 << divisor_exponent) - 1; *res = 0; *rem = 0; while (dividend) { *rem += dividend & divisor; dividend >>= divisor_exponent; *res += dividend; } while (*rem >= divisor) { *res += 1; *rem -= divisor; } } This function really gives you the exact result, integer part in res and remainder in rem. Please try it! - - - After writing this function I got a weird idea: what if I make the exponent negative? Let's see what should happen: 1/7 = 1/8 + 1/64 + 1/512 + ... (exponent = 3) 1/3 = 1/4 + 1/16 + 1/64 + ... (exponent = 2) 1/1 = 1/2 + 1/4 + 1/8 + ... (exponent = 1) So far so good. The next exponent is 0. 2^0-1 = 0. That means we have to divide by 0. 1/0 = 1/1 + 1/1 + 1/1 + ... (exponent = 0) That gives us infinity, which I guess makes sense. Now we're getting into negative numbers. This is where it gets interesting. 1/-0.5 = 1/0.5 + 1/0.25 + 1/0.125 + ... (exponent = -1) But wait, that can't be true! We can't add positive numbers to get a negative number, or more precisely -2. Anyway, let's try it with a computer. Right-shifting -1 steps should mean that we left-shift one step. Here is a function that can do that: int divide_inv(int dividend, int neg_exp) { int res = 0; while (dividend <<= neg_exp) { res += dividend; } return res; } In order to calculate 1/-0.5 we call divide_inv(1, 1) and the function returns -2. It totally works. Wait, no, that must have been just luck. Computers use two's complement but pure math can't know about that! Let's try some other random number like 469/(2^-3 - 1) which equals -536. divide_inv(469, 3) returns -536. It totally works. I don't know why it works. Using pure math doesn't work since we were just adding positive numbers and could never get a negative number but when using a two's complement signed integer, the math just seems to fall into place and these weird impossible results become true. There is just one limitation; it doesn't work when the result would be non-integer. Example: 1 / (2^-2 - 1) = -1.33333333333333333333 but divide_inv(1, 2) returns 1431655764. Spooky.