Learning about bitmaps

A few weeks ago Alistair and I were working on the code used to model the labels that a node has attached to it in a Neo4j database.

The way this works is that chunks of 32 nodes ids are represented as a 32 bit bitmap for each label where a 1 for a bit means that a node has the label and a 0 means that it doesn’t.

For example, let’s say we have node ids 0-31 where 0 is the highest bit and 31 is the lowest bit. If only node 0 has the label then that’d be represented as the following value:
 
 

java> int bitmap = 1 << 31;
int bitmap = -2147483648

If we imagine the 32 bits positioned next to each other it would look like this:

2014-01-12_15-45-16

java> 0X80000000;
Integer res16 = -2147483648

The next thing we want to do is work out whether a node has a label applied or not. We can do this by using a bitwise AND.

For example to check whether the highest bit is set we would write the following code:

java> bitmap & (1 << 31);
Integer res10 = -2147483648

That is set as we would imagine. Now let’s check a a few bits that we know aren’t set:

java> bitmap & (1 << 0);
Integer res11 = 0

java> bitmap & (1 << 1);
Integer res12 = 0

java> bitmap & (1 << 30);
Integer res13 = 0

Another operation we might want to do is set another bit on our existing bitmap for which we can use a bitwise inclusive OR.

A bitwise inclusive OR means that a bit will be set if either value has the bit set or if both have it set.

Let’s set the second highest bit. and visualise that calculation:

2014-01-12_15-45-161

If we evaluate that we’d expect the two highest bits to be set:

java> bitmap |= (1 << 30);
Integer res14 = -1073741824

Now if we visualise the bitmap we’ll see that is indeed the case:

2014-01-12_17-16-21

java> 0XC0000000;
Integer res15 = -1073741824

The next operation we want to do is to unset a bit that we’re already set for which we can use a bitwise exclusive OR.

An exclusive OR means that a bit will only remain set if there’s a combination of (0 and 1) or (1 and 0) in the calculation. If there are two 1′s or 2 0′s then it’ll be unset.

Let’s unset the 2nd highest bit so that we’re left with just the top bit being set.

If we visualise that we have the following calculation:

2014-01-12_17-33-21

And if we evaluate that we’re back to our original bitmap:

java> bitmap ^= (1 << 30);
Integer res2 = -2147483648

I used the Java REPL to evaluate the code samples in this post and this article explains bitshift operators very clearly.

The Neo4j version of the bitmap described in this post is in the BitmapFormat class on github.
 

Reference: Learning about bitmaps from our JCG partner Mark Needham at the Mark Needham Blog blog.
Related Whitepaper:

Bulletproof Java Code: A Practical Strategy for Developing Functional, Reliable, and Secure Java Code

Use Java? If you do, you know that Java software can be used to drive application logic of Web services or Web applications. Perhaps you use it for desktop applications? Or, embedded devices? Whatever your use of Java code, functional errors are the enemy!

To combat this enemy, your team might already perform functional testing. Even so, you're taking significant risks if you have not yet implemented a comprehensive team-wide quality management strategy. Such a strategy alleviates reliability, security, and performance problems to ensure that your code is free of functionality errors.Read this article to learn about this simple four-step strategy that is proven to make Java code more reliable, more secure, and easier to maintain.

Get it Now!  

Leave a Reply


five − 2 =



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

15,153 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books
Get tutored by the Geeks! JCG Academy is a fact... Join Now
Hello. Add your message here.