Why do we always declare constants to be powers of 2?

Question

Most of the constants I see in others code are powers of 2, i.e.

#define SIZE 256

or

public static final int SIZE = 2048;

Is there any particular reason why we do that instead of i.e.

#define SIZE 257

?

Thanks in advance

Answer 1

Because Computer Memory works with 0/1 that is binary system.

Answer 2

One good reason is bitmasking. As an example, if you are using constants to represent attributes of an object (or anything else), you can save many attributes into a single integer through bitmasking, and identify the individual attributes later. Great for saving many "flags" in a database.

Answer 3

Memory is typically allocated in multiples of page sizes from the operating system, and in many cases, it is useful to arrange things to fit pages exactly (in order to not waste memory). It depends on the specific allocation routine whether this really helps; e.g. if there is an implicit header, having the size a power of two may actually hurt.

Answer 4

Powers of 2 are convenient because they map well to underlying constraints in hardware.

Such as:

1. Page size
2. Address space limits
3. Alignment constaints (DWORD or QWORD alignment generally, both powers of 2)

For flags, powers of 2 always have a single bit set. So things like MY_FLAG_1 | MY_FLAG_2 | MY_FLAG_3 | ... only work with powers of two. Likewise for testing for flags with &.

Its also something of a convention to pick the nearest larger power of two for buffer sizes and the like.

Answer 5

Not much reason really. Due to alignment of variables in structured and on the stack an array of three bytes will likely take of 4 or 8 bytes in memory. I think it just feels nice.

Allocating a whole number of pages from the heap may not work as effectively as desired due to the overhead of the heap's internal structure. Allocation 4096 bytes (1 page for a 32 bit windows machine) may likely result in an allocation of 4104 bytes or more.

If the constants are flags, then the story is very different. It is typically more efficient to have bit flags than flags in some base that is not a power of 2.

Answer 6

With binary computers, it's convenient to use standards-based binary multiples like Mebibyte (or Kibi, Gibi, Tebi ...). These power of 2 numbers also look nice in Octal or Hex notations.

Answer 7

Adding more bits to a memory chip is usually done by quadrupling the number of "cells" on the chip. Twice as wide, twice as long, four times the memory (excepting smaller distances between the "cells").

Also it's easier to multiply using a single shift rather than the generic mulplication algorithm of adding successive shifts depending on if a particular bit is set or not. OpenGL was famous for requiring power of two sizes for textures to access particular scan lines.

Answer 8

When it comes to array sizes I suspect there are two reasons why powers of two are favoured. One - as evidenced by several replies here - is that programmers who don't know what is going on "under the hood" seem to have a general sense that it might somehow be more efficient to use a power of two. The other is (mostly historical now) to do with cyclic buffers.

Cyclic buffers that are powers of two can be handled more easily and faster using masks can on the read and write indices (or pointers) rather than using the normally slower modulo operation or using conditions that require branches. This was crucial on older machines but can still be important for transferring large amounts data - e.g. graphics processing

For example, in C, the the number of bytes available to be read in a cyclic buffer can be obtained by:

pending = (SIZE + wr - rd) & (SIZE - 1);

If not using power of two then the equivalent would be:

pending = (SIZE + wr - rd) % (SIZE - 1);

On machines that don't implement a division/modulus instruction that little "%" could take several hundred cycles, so you would need something like:

if (wr >= rd)
    pending = wr - rd;
else
    pending = (SIZE + wr) - rd;

Which clutters the code and causes branching which can stall the instruction pipeline.

Writing to the buffer which was something like

buf[wr++] = x;
if (wr == SIZE)
    rd = 0;

becomes the (generally) more efficient:

buf[wr++] = x;
wr &= SIZE-1;

Of course if you used an unsigned 8 bit variable to index a 256 entry array then you didn't even need to do the masking.