Allocating byte array to get 4 billion bits

I was reading this book entitled, Cracking the Coding Interview by Laakman. There is this part where she (the author p.g. 202) did:

byte[] bitfield = new byte [0xFFFFFFF/8];//there are 7 F's

She was allocating 4 billion bits. However, isn't 0xFFFFFFF = 2^28-1? Thus, she has only allocated a byte array of 2^28-1/8 bytes, which is not remotely close开发者_开发技巧 to 4 billion bits. It is only 2^28-1 bits. My question is- is she wrong or am I doing something wrong? How do we allocate 4 billion bits? I have tried:

byte[] bitfield = new byte[0xfffffff *2];

Although the above causes the jvm to run out of heap space.

While we are at it, what is the best was to express hex values? e.g. 0xffffffff or 0xFFFFFFFF?

It's not clear to me why you're multiplying by 2. It's simplest to just take the hex representation of (4 billion / 8) - where by "4 billion" we really mean 0x100000000.

So use 0x100000000 / 8, i.e. 0x2000000:

byte[] array = new byte[0x20000000];

That should be fine if you've given your JVM enough memory on startup, e.g. with -Xmx900M.

Sample code:

public class Test {
    public static void main(String[] args) {
        byte[] bytes = new byte[0x20000000];
    }
}

Run by default:

c:\Users\Jon\Test>java Test
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at Test.main(Test.java:3)

Run with a bit more space:

c:\Users\Jon\Test>java -Xmx900M Test

Being the pedantic, I would say 4 billion is not exactly 2^32 and I would suggest using BitSet which cannot hold this many bits but 2 BitSets can

BitSet[] bitSets = { new BitSet(2 * 1000 * 1000 * 1000), 
                     new BitSet(2 * 1000 * 1000 * 1000) };

If it has to be 2^32 bits or 4 Gb (lowercase b is bits), this is slightly to much for two bitSets.

BitSet[] bitSets = { new BitSet(1 << 28), 
                     new BitSet(1 << 28),
                     new BitSet(1 << 28),
                     new BitSet(1 << 28) };
// set a bit
long bitToSet = 

bitSets[(int) (bitToSet >>> 28)]
       .set((int) (bitToSet % (1 << 28)), value);

// test is set
long bitToTest = 

boolean test = bitSets[(int) (bitToTest >>> 28)]
                     .get((int) (bitToTest % (1 << 28)));

Obviously what ever approach you use you want to wrap the array in a collection which hides the details of how it is implemented.

The MAX_VALUE of Integer is 0X7fffffff. I believe she missed digit '7' while declaring. As The strategy is to use the bit position to indicate the integer value(i.e. each byte has 8 bits can hold up to 8 integers), she allocated array to hold 4 billion integers.

 byte x[] = new byte[0x7fffffff/8];

My first trot through the numbers came up with 2,147,483,640 bits -- about two billion.

[Oops -- missed that divide by 8. Now I get 268,435,448 bits.]

[The maximum sized object you can allocate in Java will depend both on your stated/defaulted heap size limit and details of the JVM design. Some will not be able to allocate a single object larger than 16MB, for example, while others may have a limit of 64MB or such.]

to get 4 billion bits, you need 500,000,000 (500 million) bytes. This is 488281.25K or ~487 meg. In order to allocate this in memory you will most likely need to adjust the heap size of your JVM upwards.

It seems likely that either the book in question had 8 Fs or there was a typeo.

Based on the information posted, I would say you are right. However (considering billion as a short scale billion, 10ˆ9), the way to "allocate 4 billion bits" I can think of is:

byte[] bitfield = new byte [1000 * 1000 * 1000 / 8 * 4];

And the allocated array length would be 500MB (would probably need an extra -Xmx based on your defaults):

bitfield.length

500000000 (base 10)
0x1DCD6500 (base 16)

BTW: I normally express base 16 in caps

On the other side billion is somewhat ambiguous (see short scale vs long scale): Wikipedia Billion Java Primitive Data Types

This might be a mistake since she wants to represent 4 billion integers. Allocating to 0xFFFFFFFF/8 would hold all 4 billion since each byte holds 8 bits. I added this to her errata 4 years ago but she blew me off. : |

I'm pretty sure she missed F - it should be 0xFFFFFFFF (8Fs) = 2^32 ~ 4 billion bytes = 32 billion bits=> 0xFFFFFFFF/8 = 4 billion bits. where every bit position represents a number from 1 to 4 billion.