Working with Powers of Two

Using powers of two for estimation and reasoning

[Video Tutorials] (coming soon)

Working with powers of two is fundamental throughout computer science and computer technology, as is working with base two logarithms (the inverse of powers of two). There are lots of examples of this: Data is represented using bits, which is a base two representation in which each bit represents a power of two; data structures often work by splitting data in half, resulting in complexity proportional to a base two logarithm (as in balanced binary search trees, binary space partitions, and more); memory is addressed using binary values, meaning that memory sizes are naturally powers of two; and the “bit” is the most natural measure of information, leading to the importance of powers of two and the related issue of base two logarithms.

Once you learn a few tricks, you can estimate many quantities that arise in computing problems quickly and easily in your head, giving you a powerful skill at rough approximation. How “rough” is “rough approximation”? In this kind of estimation, we’re really only interested in getting things right to within a factor of two or four, not accurate to a fraction of a percent. The distinctions we’re after are seeing the difference between a process that takes a week and a process that takes a year — not the difference between 10 and 15 minutes. Here’s the basic process:

  1. Estimate values, such as data size, using powers of two and some simple conversions described in this tutorial.
  2. Do calculations by combining powers of two, doing simple addition or subtraction of exponents.
  3. If working with time, convert back from powers of two to meaningful measures such as minutes, hours, or years.

For many tasks, this will give a good rough approximation that illuminates the important issues in a way that can guide more precise analysis.

Brief review of math with powers and logarithms

Before we get into the main content for this tutorial, let’s quickly review how multiplication and division of powers works, and the basic definition of a base two logarithm. One of the main points of this tutorial is that when you are working with large powers of two, multiplication or division can be performed by just adding or subtracting the much smaller numbers in the exponent. Specifically:

  • For any a and b, 2^{a}\cdot 2^{b}=2^{a+b}

  • For any a and b, 2^{a}/2^{b}=2^{a-b}

We also will need to take the base two logarithm of a power of two, and this is particularly simple:

  • For any a, \log_2 2^{a}=a

There are a lot of other rules for working with powers and logarithms, which we cover in the Useful Functions Tutorial, but the three basic rules above are all we’ll need for this tutorial.

The Basic Powers of Two

As a first step, there is a nice correspondence between powers of two and numbers we talk about in everyday conversation (thousands, millions, etc.). In particular, as the exponent of a power of two goes through multiples of 10, values go up through our “named” numbers. For example, 2^{10}=1024, which is approximately a thousand. In fact, when talking about memory (RAM) sizes, since RAM capacity in a hardware module is always a power of two, these are the actual sizes when you get 1K or 1M or 1G of RAM. In other words, if you were to buy a memory module with 1K bytes of RAM (if you could even buy something that small these days!), it would actually have a capacity of 1024 bytes. More realistically, when you buy a 4GB RAM module, it is actually 2^{32} or 4,294,967,296 bytes, rather than the 4 billion that a naive interpretation of the “G” prefix would suggest.

NoteAn aside on hardware and size prefixes

The above description of what “1K” or “1G” means is universally applied to RAM sizes, but not to other sizes. For example, hard drives use traditional base-10 notions (“SI units”) in which “G” means exactly a billion and “T” means exactly a trillion. Solid state drives (SSDs) have inherited this terminology, even though the hardware of an SSD is closer to RAM than it is to a hard drive.

To make this more explicit, some people use “GiB” rather than “GB” to represent 2^{30} bytes, where “GiB” is pronounced “gibibyte” – there is similar terminology for other powers of two, using KiB, MiB, TiB, etc. While the MiB and GiB terminology successfully removes ambiguity in size specifications, it is far from universally used. It is far more common for people to refer to a 4,294,967,296 byte RAM module as “four gigibytes” rather than “four gibibytes,” and you are expected to know the difference by context.

Here are the important powers of two to know:

2^{10} “about a thousand”
2^{20} “about a million”
2^{30} “about a billion”
2^{40} “about a trillion”

Next, you can “fill in the gaps” between these powers of two by knowing the small powers of two – those with an exponent less than 10. If you do much computer science at all, you should know, without even really having to think, that 2^4=16 and 2^8=256 (the latter is the number of distinct 8-bit bytes, so is one of the most important values for you to know right off the top of your head). Another value that is good to know, simply because it comes up a lot, is 2^{16}=65,536, which is often referred to as “64K.” This is the number of different values that can be represented by a 16-bit data type, so knowing this you know that the number of different values possible for a 16-bit short in Java. When using a C or C++ compiler with 16-bit short values, the maximum value of an unsigned short is exactly 2^{16}-1 or 65,535.

Once you know these values, it is easy to estimate others. For example, what is 2^{25}? Well, the exponent is in the 20’s, so let’s separate that out by writing 2^{25}=2^{20}\cdot 2^5. Knowing the small powers of two and the approximations for multiples of 10 shows that this is “about a million” times 32 — in other words, 2^{25} is approximately 32 million.

Values for Times, Sizes, and More

When analyzing computations, we often work with measurements of time, so there are a few powers of two to know for approximating units of time. Unfortuntately, there’s no clean pattern as there was in the values above, but taking the time to learn these values allows you to relate numbers of seconds (in powers of two) to measures that make sense to humans. While the approximations above are accurate to within 10% in the worst case, the measure for time units aren’t as close – the following table gives the important values, shown below with relative error of each.

Seconds in an hour Approximately 2^{12}    (relative error 13.8%)
Seconds in a day Approximately 2^{16}    (relative error 24.1%)
Seconds in a year Approximately 2^{25}    (relative error 6.3%)

As another notion of time, consider the speed of a modern processor. Speeds are typically in the “low gigahertz” range, ranging from 2 GHz to 4 GHz, with each machine instruction taking a few clock cycles. For simple calculations, it’s not too far off to say that a modern CPU performs around a billion operations per second – or around 2^{30} operations per second. If you want to be more precise for modern systems you could estimate this as 2^{31} (approximately 2 GHz) or 2^{32} (approximately 4 GHz).

Example 1
Consider a program that allocates 40 bits to a counter, where we’ll assume 2^{31} operations per second. How long would it take to increment the counter before it “wraps-around” (i.e., exceeds the value that can be stored in 40 bits)? A 40-bit counter that is initialized at zero wraps around when it has been incremented 2^{40} times, so if we are considering 2^{31} (about 2 billion) increments per second then this will happen in roughly 2^{40}/2^{31}=2^{9}=512 seconds. 10 minutes is 600 seconds, and since this is a little under that we can estimate this time as 9 minutes. On my system, counting to 2^{40} actually took around 6 minutes, so the estimate gives an excellent ball-park figure!

Example 2
The original Unix implementation kept track of time with a simple integer counter, measuring the number of seconds since the beginning of January 1, 1970 (this starting time is known as the “Unix epoch”). The counter was 32 bits, and unfortunately was a signed integer, so can only count up to 2^{31}-1. What is the last time that can be represented with this time representation? We know that a year is approximately 2^{25} seconds, so the counter is good for 2^{31}/2^{25}=2^7=64 years. 64 years after 1970 is 2034, so that’s a reasonable estimate on the time at which this representation fails. (Note that a precise calculation shows that the counter runs out at 3:14:08 on Tuesday, January 19, 2038, so this is known as the “Year 2038 Problem.” But 2034 is a pretty good estimate, and shows that this implementation had a lifetime that was far too short!)

Base Two Logarithms

If f(n)=2^n is the “powers of two function”, then the inverse is the base two logarithm (i.e., f^{-1}(n)=\log_2 n), which is one of the most important functions used in computer science. The function \log_2 n is proportional to the time to store or lookup a value in a balanced binary tree, the time for a binary search, the time to update a binary heap, and more. If you can estimate powers of two quickly, then you can also estimate base two logarithms quickly! Since 2^{10} is approximately 1000, you also know that \log_2 1000 is approximately 10. Similarly, you know that \log_2 1,000,000 is approximately 20. How accurate is this quick approximation? The exact calculation shows that \log_2 1,000,000\approx 19.9316, so this is very close!

By repeatedly doing quick approximations with powers of two, you can narrow down an estimate for the base two logarithm of any number. What is the base 2 logarithm of 100,000? Well, that’s 100 times 1000 — since 100 is a small value, we know a lot of powers of two in this range, so know that this is approximately 2^7 (since 2^7 is exactly 128). So 100,000 is approximately 2^{7}\cdot 2^{10} = 2^{17}, and so the base two logarithm of 100,000 is approximately 17. (Note that the precise value is 16.6096…)

Example 3
Consider this data structures problem: In 2016 there were a little over 5 million registered voters in North Carolina. Let’s say we wanted to be able to look up voters quickly, so we put all those names in a sorted array so that we can look people up using binary search. A binary search on n values takes at most \lceil \log_2 n\rceil comparisons, so what does this say about finding one voter out of 5 million voter records?

Here’s how we estimate this: We’re talking about something in the millions, so we start off by noting that 2^{20} is about a million. We’re talking about 5 million, and the closest power of two to 5 is 2^2, so we use 2^{2}\cdot 2^{20}=2^{22} to estimate 5 million. The base two logarithm of this is 22, so we can find any voter in around 22 or 23 comparisons.

Note that a more precise calculation gives \log_2(5,000,000)\approx 22.2535, so our estimation is very accurate, without ever having to get out a calculator.

This number of comparisons is over 100,000 times faster than simply looking through all 5 million records, and a modern processor can do this in less than a microsecond. By knowing powers of two estimation, we were able to get a very good and concrete understanding of how much binary search improves over linear search, putting some real numbers to the mathematical notation \log_2 n.

Application: Cryptographic Keys

These approximation techniques are particularly useful when analyzing cryptography. You don’t actually have to understand cryptography for these examples to make sense, so don’t worry if you know absolutely nothing about cryptography.

Example 4
In symmetric cryptography, keys are typically arbitrary k-bit values, where we call k the “key length.” For example, people will talk about AES (a cryptographic algorithm) with 128 bit or 256 bit keys. A “brute force attacker” simply tries keys one after another to find one that works, and there are 2^k different k-bit binary values to try.

Consider a simple encryption scheme that uses a 40-bit key, where you can test a key to see if it is the correct key at a rate of a billion per second. When you search for a random key out of 2^{40} possibilities, you will have to, on average, test half of the possible keys. This means you test 2^{40}/2=2^{39} keys. If you can test 2^{30} keys per second, this will take (on average) 2^{39}/2^{30}=2^9 seconds. If you know your small powers of two, you know this is 512 seconds — or even if you don’t remember that exactly, it’s half of 2^{10} so it’s “about 500.” Since 10 minutes is 600 seconds, such a key can be found, on average, in a little under 10 minutes. Obviously, that’s not very secure!

Historical note: Before the year 2000, when non-US users downloaded the Netscape Navigator browser they got the “International Version,” which most commonly used 40-bit keys for a cipher called RC4.

Example 5
What if we increase the key size to 128 bits, while still being able to test keys at around a billion per second — note that 128 bits is the smallest key size supported by the modern cipher AES. This should be more secure than a 40-bit key, but how much more secure? It’s about 3 times as long, so is it three times as secure, or something else? It turns out that tripling the size of the key increases security far, far more than just 3 times! Let’s do calculations like in Example 4: On average, we will need to check 2^{128}/2=2^{127} keys. At a billion a second, this is 2^{127}/2^{30}=2^{97} seconds.

That’s a lot of seconds, so let’s try to get a better handle on that. Using the estimate that there are 2^{25} seconds in a year, we see that this would take, on average, 2^{97}/2^{25}=2^{72} years. Wow. How much is that? Since 72=32+40 we know that this is about 4 billion trillion years. For context, the best estimate on the age of the universe is just 13.7 billion years.

Even if you could build special-purpose hardware that could test keys a billion times faster, it would still take around 4 trillion years to find the key. That’s still almost a thousand times the age of the universe – that seems pretty safe!

Note that we are assuming that brute force, or trying all possible keys, is the only way to break this encryption. For now, that’s more-or-less the best an attacker can do against the AES algorithm, but if a weakness were found that allowed for attacks that are more efficient than brute force, then all bets are off.

This last pair of examples shows how rough approximations are useful for giving quick and very useful estimates in cryptography. Even if the estimation can be off by a factor of 10, Example 4 would show that a 40-bit key could be broken in something between 50 seconds and 5000 seconds (about an hour and a half) – both very practical timings. And if Example 5 overestimated by a factor of 10, you’re still looking at hundreds of millions of trillions of years – very impractical, no matter how you look at it!

Practice Problems

The following problems can be used to test your understanding of the material above. Try working out each problem before opening the solution. In particular, you are strongly encouraged to actually write down a solution to commit yourself to it, and then open the answer to see if you were correct.

On all of these problems, use the powers of two estimation techniques that we covered in this tutorial. Do not use a calculator! The whole point is to use quick “back of the envelope” calculations that you can do mostly in your head.

  1. In the tutorial on propositional logic, we talked about the “satisfiability problem”: given a propositional formula with n variables, is there some truth assignment to those variables which makes the formula true? To brute force this problem would require checking all 2^{n} possible truth assignments to the n variables. Consider a program that could check half-a-billion truth assignments per second.

    1. How many truth assignments can be checked per second, written as a power of two?

    2. How long would it take to test all truth assignments when n=30?

    3. How long would it take to test all truth assignments when n=40?

    4. How long would it take to test all truth assignments when n=80?

    1. A billion is approximately 2^{30}, so half a billion is approximately 2^{29}.

    2. When n=30, we have to check 2^{30} truth assignments, which takes 2^{30}/2^{29} seconds, or 2 seconds.

    3. When n=40, we have to check 2^{40} truth assignments, which takes 2^{40}/2^{29}=2^{11} seconds, or about 30 minutes.

    4. When n=80, we have to check 2^{80} truth assignments, which takes 2^{80}/2^{29}=2^{51} seconds. The largest time unit we defined in this tutorial was one year, which is approximately 2^{25} seconds, so this calculation would take 2^{51}/2^{25}=2^{26} years. Since 2^{20} is about a million, and 2^{6}=64, this takes about 64 million years.

  2. “Bitcoin mining” is a computationally-intensive problem that is a central part of Bitcoin cryptocurrency. While the details are more than we’ll describe here, the important part is that as of this writing (September 2026) a successful mining operation requires approximately 2^{79} “hashing operations.” (This simplifies some things, but is “ball-park correct.”)

    1. The fastest general purpose CPUs can perform about 32 million hashing operations per second on a single core. How long would it take for a successful mining operation at that speed?

    2. A fast consumer graphics card has a GPU (Graphics Processing Unit) can be programmed to do bitcoin mining, and the fastest can do about 16 billion hashing operations per second. How long would it take for a successful mining operation at that speed?

    3. Companies build special purpose hardware designed specifically to perform bitcoin mining at high speeds. The “Bitmain Antminer S23 Hyd” can perform roughly 1 quadrillion hashes per second (that’s a million billion). How long would it take for a successful mining operation at that speed?

    4. Most Bitcoin mining is done using “pools,” where people combine the power of their hardware to do mining. If n miners are combined, they can mine roughly n times faster. The “AntPool” is equivalent to a pool of roughly 250,000 miners that work at the speed given in part c. How long would it take for a successful mining operation at that speed?

    1. “32 million” is about 2^{25} (that’s 2^{20} for a million and 2^{5} for 32), so this would take about 2^{79}/2^{25}=2^{54} seconds. Since 2^{25} seconds is about a year, this would take about 2^{29} years, which is about 512 million years (“half a billion years” is also an acceptable way to look at this).

    2. “16 billion” is about 2^{34}, so this would take about 2^{79}/2^{34}=2^{45} seconds. Since 2^{25} seconds is about a year, this would take about 2^{20} years, which is about a million years.

    3. A quadrillion is about 2^{50} (looking at it as a million billion, that’s about 2^{20}\cdot 2^{30}=2^{50}), so this would take about 2^{79}/2^{50}=2^{29} seconds. Since 2^{25} seconds is about a year, this would take about 2^{4} years, or 16 years.

    4. 250,000 is roughly 2^{18}, so the hashrate for this pool is roughly 2^{50}\cdot 2^{18}=2^{68}. Therefore, a mining operation would take about 2^{79}/2^{68}=2^{11} seconds, which is about 2000 seconds. This is roughly 30 minutes (a half an hour).

  3. Sorting data is a fundamental computational task, and provides great examples when studying the design and analysis of algorithms. If you have n data items that you need to put in order, there is a fairly simple and intuitive algorithm known as “insertion sort” that (in the worst case) requires approximately \tfrac{1}{2} n^2 comparisons to find the correct sorted order for the data. A more complex algorithm, which students generally do not find intuitive the first time they see it, is “merge sort”, which requires approximately n\log_2 n comparisons for the same problem.

    1. Using a computer that can make one million comparisons per second, approximately how long would it take for insertion sort to order 64,000 items?

    2. Using a computer that can make one million comparisons per second, approximately how long would it take for merge sort to order 64,000 items?

    3. Repeat both calculations for sorting 8 million items.

    1. We are sorting n=64,000\approx 2^{16} items. Since insertion sort performs \frac{1}{2}n^2=\frac{1}{2}(2^{16})^2=2^{31} comparisons. The computer makes a million or approximately 2^{20} comparisons per second, so the algorithm takes approximately 2^{31}/2^{20}=2^{11} seconds. You can write this out as “2000 seconds”, or using our observation that an hour is approximately 2^{12} seconds you could conclude that this takes about 30 minutes.

      Note that you should not have used a calculator or tried to calculate this exactly – that would miss the entire point of what we’re covering here. But to satisfy your curiosity, if you had done that, the exact amount of time would be 34.133… minutes, so 30 minutes is a good estimate!

    2. We are sorting n=2^{16} items, as in part (a). Since merge sort performs n\log_2 n=2^{16}\cdot\log_2(2^{16})=2^{16}\cdot 16 comparisons, and we can keep everything as a power of two by rewriting 16 as 2^4: in other words, the algorithm makes 2^{16}\cdot 2^4=2^{20} comparisons. Since the computer makes approximately 2^{20} comparisons per second, this algorithm takes just 1 second.

      So while insertion sort takes approximately 30 minutes, merge sort takes only about one second. While merge sort is not an intuitive algorithm at first, this massive improvement in speed is why it is important for computer science students to study merge sort. It will get intuitive after some study and thought – you just need to put in the effort!

    3. Repeating the above calculations with n=2^{23} (8 million), insertion sort will make \frac{1}{2}(2^{23})^2=2^{45} comparisons. At 2^{20} comparisons per second, this will take about 2^{45}/2^{20}=2^{25} seconds, which is approximately one year to sort the data.

      By comparison, merge sort will make 2^{23}\log_2(2^{23})=2^{23}\cdot 23 comparisons, which takes approximately 2^{23}\cdot 23/2^{20}=2^{3}\cdot 23=8\cdot 23 seconds. The numbers here are easy to multiply out, so we see that this takes about 184 seconds, or about 3 minutes.

      So by being smart about algorithms, you can change a program that might take a full year to run into one that finishes in 3 minutes. And the techniques we give here, using powers of two estimation, demonstrate this in a quick and intuitive way.

  4. The “Data Encryption Standard” algorithm (DES) was created in the mid-1970s, and used a 56-bit key.

    1. If you could test a billion keys per second, how long would it take to break DES, on average?

    2. What if you built 1,000 machines that could each test a billion keys per second, so you can test overall a trillion keys per second. How long would it take to break DES on average now?

    3. In 1998, a machine named Deep Crack was built specifically to break DES keys, and the initial version could break a key in roughly two days. By this time, the NSA had proposed a new encryption algorithm named Skipjack that used 80-bit keys. Assuming Deep Crack could test keys against Skipjack at the same rate that it tested against DES, how long would it take to break a Skipjack key?

    This is just like Example 4 above. We would need to test roughly half of the 2^{56} possible keys on average, so we’d need 2^{55} tests.

    1. In this part, the question states that we can test roughly a billion of these per second, which is 2^{30} per second. Therefore, this would take 2^{55}/2^{30}=2^{25} seconds on average. This is roughly one year.

    2. Now we can test 2^{40} keys per second, so it will take 2^{55}/2^{40}=2^{15} seconds on average. Referring to our times above, this is about half a day.

    3. Moving from 56-bit keys to 80-bit keys means there are 2^{80}/2^{56}=2^{24} times as many keys, so it will take 2^{24} times longer to break. Since Deep Crack took 2 days for 56-bit keys, it would take 2^{25} days for an 80-bit key. In other words, this is about 32 million days which is roughly 2^{25}/2^{8}=2^{17} years – or about 128 thousand years.

    Historical note: Skipjack was proposed as part of a cryptographic modernization push by the NSA in the early 1990s, but it also included aspects that were not acceptable and so was never used in practice. We now regularly use AES with 128-bit or even 256-bit keys, which was analyzed above in Example 5.

Up
Miscellaneous Useful Mathematics

Website © Copyright 2025 by Logical Learning