Efficient way to manipulate large powers of two

Question

The most efficient way to code powers of two is by bit shifting of integers.

1 << n gives me 2^n

However, if I have a number that is larger than the largest value allowed in an int or a long, what can I use to efficiently manipulate powers of 2?

(I need to be able to perform addition, multiplication, division and modulus operations on the number)

Answer 1

Is this what you need?

BigInteger hugeNumber = BigInteger.ONE.shiftLeft(n);

This is the result when n=1000,

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Answer 2

What operations do you need to perform on your "powers of two"? If it's only division and multiplication, for example, you can just keep the log2 of the powers of two in question, and use subtraction and addition on them instead. Without knowing what kinds of "manipulate" you want, it's impossible to give good suggestions on how to efficiently "manipulate";-).

Answer 3

Easy: long :-)

If you don't mind floating-point, double can exactly represent all powers of 2 up to 2^1023.

Otherwise, it depends on what kind of "manipulation" you're doing.

Answer 4

Looks like java.math.BigInteger is what you need.

It has mod, shiftLeft, shiftRight, and of course add, multiply, subtract and divide. It's an immutable type (ala String), so perhaps it's not the ultimate most efficient way of doing things, but unless you've provably identified it as a performance problem, I wouldn't worry about it.

Answer 5

Does it need to be accurate?

Otherwise you can represent is as a long multiplied by an two to the power of an int.

Example:

x = 15 * 2^123