Shulou(Shulou.com)06/03 Report--

This article introduces the knowledge of "how to skillfully use binary to improve performance by 100 times and reduce storage space by 100 times". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations! I hope you can read it carefully and be able to achieve something!

Suppose there is a requirement like this: find out if a number exists among 20 billion random integers? It requires high efficiency and memory saving.

We know that in Java, int occupies 4 bytes, 1 byte = 8 byte,1 byte = 8 bit (bits)

If you use int storage, that is 20 billion int, so the space occupied is about

(200000000004 ≈ 1024) 74.5G.

Memory consumption is so large that ordinary home computers can not meet the needs, so it is not appropriate to store data in memory.

If bit-by-bit storage is different, 20 billion is 20 billion bits, and the occupied space is about

≈ 2.33G, saving 30 times the space.

In fact, this is Bitmap's idea. The basic idea of Bitmap is to mark the Value corresponding to an element with a bit bit, and Key is the element itself. Using bit to store data can greatly save storage space.

What is Bitmap? How do you represent a number in bitmap?

We know that the underlying computer stores binary data, and the binary numbers are only 0 and 1. The value of each bit of bitmap can only be 0 or 1. 0 indicates that it does not exist, and 1 indicates that it exists.

In this way, we can easily express the numbers {1: 1, 2, 4, 6}:

The smallest unit of computer memory allocation is bytes, that is, 8 bits, so what if you want to represent {1214 13 15}?

Of course, it means on another 8-bit:

In that case, it seems to be a two-dimensional array.

1 int occupies 32 bits, so we only need to apply for an int array with a length of int tmp [1+N/32] to store, where N represents the maximum of these numbers to be stored, so:

Tmp [0]: can denote 0x31

Tmp [1]: can represent 32'63

Tmp [2]: can represent 640095

. . .

Therefore, for any integer M _ 32, you can get the subscript, and M% 32 can get where it is in this subscript.

So, how do you put a number into Bitmap? For example, if you want to put the number 5 in it.

Insert a number

First of all, it should be in the fifth position of b [0], which means that it should be in the fifth position. We can move 1 to the left by 5 bits, and then bit by bit with b [0].

Binary is:

This is equivalent to 86 | 32 = 118, that is, 86 | (1

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.