how to calculate 2^32 without multiplying numbers directly?

Question

the simplest way to calculate 2^32 is 2*2*2*2*2......= 4294967296 , I want to know that is there any other way to get 4294967296? (2^16 * 2^16 is treated as the same method as 2*2*2.... )

and How many ways to calculate it?
Is there any function to calculate it?

I can't come up with any methods to calculate it without 2*2*2...

possible duplicate of [Calculating powers (e.g. 2^11) quickly](http://stackoverflow.com/questions/2198138/calculating-powers-e-g-211-quickly) — RGG, Jul 12 '13 at 16:48
Why are you calculating at all? Here's a function that calculates 4294967296: `f() = 4294967296`. — harold, Jul 12 '13 at 16:55
Without Fancy(tm) computer operations, doubling a number is as simple as adding it to itself. So, doubling '1' 32 times -- 1 + 1 is 2, 2 + 2 is 4, etc -- suffices. — Kaganar, Jul 12 '13 at 16:56

score 9 · Answer 1 · answered Jul 12 '13 at 16:47

9

2 << 31

is a bit shift. It effectively raises 2 to the 32nd power.

answered Jul 12 '13 at 16:47

Robert Harvey

178,213
47
333
501

1

I didn't downvote, but so what it uses two? Shifting one by 32 isn't any less correct. – harold Jul 12 '13 at 16:51
Meh. The operand being raised by a power is 2, not 1. – Robert Harvey Jul 12 '13 at 16:52
I did downvote it, but for a second I was 100% sure that there was `2 << 32`. Nevermind it though – Grzegorz Piwowarek Jul 12 '13 at 16:52
1

@pivovarit It was. SO does not show edits that occurred in the first instants. – Pascal Cuoq Jul 12 '13 at 16:53
3

I like to think of `x << y` as `x * 2^y`. – Mysticial Jul 12 '13 at 16:54
@harold The only use case I can think of is in C, where left-shifting an int by 31 is well-defined, while left-shifting by 32 is not. That being said, I could have misremembered, plus that use case is pointless here since 2^32 overflows. – Dennis Meng Jul 12 '13 at 19:51
@DennisMeng right so it had better be an int64_t or some such and then shifting by 32 would be fine – harold Jul 12 '13 at 20:30

Vilhelm Gray · Answer 2 · 2013-07-15T12:40:13.480

1

If you are on a common computer you can left bitshift 2 by 31 (i.e. 2<<31) to obtain 2^32.

In standard C:

unsigned long long x = 2ULL << 31;

unsigned long long is needed since a simple unsigned long is not guaranteed to be large enough to store the value of 2<<31.

In section 5.2.4.2.1 paragraph 1 of the C99 standard:

... the following shall be replaced by expressions that have the same type as would an expression that is an object of the corresponding type converted according to the integer promotions. Their implementation-defined values shall be equal or greater in magnitude (absolute value) to those shown, with the same sign.

— maximum value for an object of type unsigned long int

ULONG_MAX 4294967295 // 2^32 - 1

— maximum value for an object of type unsigned long long int

ULLONG_MAX 18446744073709551615 // 2^64 - 1

edited Jul 15 '13 at 12:40

answered Jul 12 '13 at 16:47

Vilhelm Gray

11,516
10
61
114

In what you have written, `unsigned long long x = 2<<32;`, if it is C, the shift is on an `int`. This is undefined behavior most everywhere (shifting by more than the width of the type is). – Pascal Cuoq Jul 12 '13 at 16:49
3

And it is either 1 << 32 or 2 << 31. – Pascal Cuoq Jul 12 '13 at 16:50
@PascalCuoq Would an explicit cast as such prevent the UB? – Vilhelm Gray Jul 12 '13 at 16:51
1

Yes, `((unsigned long long)2)<<32` is defined. I edited my first comment to include the original code for future readers. – Pascal Cuoq Jul 12 '13 at 16:52
1

Instead of the clumsy `(unsigned long long)2` you could also simply write `2ULL` – celtschk Jul 15 '13 at 01:17
@celtschk Wow, I feel silly now for forgetting about literals. :) – Vilhelm Gray Jul 15 '13 at 12:40

score 1 · Answer 3 · answered Jul 12 '13 at 16:48

1

Options:

1 << 32
2^32 = (2^32 - 1) + 1 = (((2^32 - 1) + 1) - 1) + 1 = ...
Arrange 32 items on a table. Count the ways you can choose subsets of them.

answered Jul 12 '13 at 16:48

Timothy Shields

75,459
18
120
173

score 1 · Answer 4 · answered Jul 12 '13 at 16:59

If you are not much of a fan of binary magic, then I would suggest quickpower.This function computes xⁿ in O(logn) time.

 int qpower(int x,int n)
 {
   if(n==0)return 1;
   if(n==1)return x;
   int mid=qpower(x,n/2);
   if(n%2==0)return mid*mid;
   return x*mid*mid;
 }

King King · Answer 5 · 2013-07-12T17:04:05.110

0

Why not using Math.Pow() (in .NET). I think most language (or environment) would support the similar function for you:

Math.Pow(2,32);

edited Jul 12 '13 at 17:04

answered Jul 12 '13 at 16:53

King King

61,710
16
105
130

1

The OP didn't specify a programming platform. – Robert Harvey Jul 12 '13 at 17:01
@RobertHarvey I guess most languages would support the similar function `Pow()`, he asked this `Is there any function to calculate it?` So I think it's a choice. Thank you anyway. – King King Jul 12 '13 at 17:03

score 0 · Answer 6 · answered Jul 15 '13 at 00:49

0

In Groovy/Java you can do something like following with long number (signed integer can be max 2^31 in Java)

long twoPOW32 = 1L << 32;

answered Jul 15 '13 at 00:49

Hemant

4,537
8
41
43

how to calculate 2^32 without multiplying numbers directly?

6 Answers6