Hi everyone,
I'm trying to figure out if there is any way to do exponents using bit shifting.
I know the following:
x *= 2 --> x << 2
x /= 2 --> x >> 2
pow(2, x) --> 1 << x
i'm looking for the equivalent bitshift, if any, for x = pow(x, 2) where x can be any number
i've seen the following for x = 5
x = 0101 (5)
x << 2 --> 010100 (20)
x + 0101 --> 011001 (25)
but then that is not true for other numbers :(
That X=5 case is based on the idea that 5x5 = 5 x (4 + 1).
Generalization is that X^2 = X * X = X * (a + b) where a is c^2 and b is 1.
Number 9 is similar 9 = 8 + 1 = 2^3 + 1. Or any number of the form 2^n+1 (n=1,2,...).
A better idea may be simple multiplication, shifted adding or, if needed, converting the multiplication into shifts, adds and subtracts.
Shifted add: add X to result if LSB of the multiplier is set
shift both X and multiplier; X to the left and multiplier to the right.
repeat until all multiplier bits are done.
00110011 * 00100100
= 1 * 00100100 (= (1 * 1) * 00100100 = 1 * (1 * 00100100 ) = 00100100 << 0)
+ 1 * 01001000 (= (1 * 2) * 00100100 = 1 * (2 * 00100100 ) = 00100100 << 1)
+ 0 * 10010000 (= (0 * 4) * 00100100 = 0 * (4 * 00100100 ) = 00100100 << 2)
+ ... multiplier bit value * bit place value * multiplicand
(bit place value is the bit's worth: n:th bit has bit place value 2^n)
Why?
Because:
(a + b + c)x = ax + bx + cx
and
00110011 = 02^7 + 02^6 + 12^5 + 12^4 + 02^3 + 02^2 + 12^1 + 12^0
00110011 = 00000001 + 00000010 + 00000000 + 00000000 + 00010000 + 00100000 + 00000000 + 00000000
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.