In the golden days of C, when memory and disk space were premium resources, we used to squeeze every ‘bit’ of it. One of the use cases we would always run into is to identify if more than one features were set or unset. One easy way was of course to use multiple short values and switch them to indicate changes in flag. However this would actually mean a lot more resources. So, even to this day bitwise operations makes sense. In today’s blog we will discuss two different way to implement in Java.
But before we start, let us define some basic bitwise operations.
Bitwise Operations
So what the heck is a bit? Bit or binary digit is the smallest unit of storage that can be assigned. Eight bits constitute a byte. In computers, we normally have a bit turned On (1) or Off (0) and can do multitude of logical operations on them. People with electronics background may remember the logic gates. In this case we are specifically interested in AND, OR, NOT, NAND and XOR gates. I don’t know if we will need all of them, but let’s see. Let us go through each of these logical operations. We will also put the truth tables along with it. And last but not the least, we will look at bit shifting operations. All of these will come in handy when we start our codes for flag setting.
AND Operation
AND gate has two or more inputs and one output. It is only TRUE when all of them are either TRUE. Let’s look at the truth table.
| A | B | A AND B |
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
OR Operation
OR gate also has two or more inputs and one output. It is TRUE when either of the inputs is TRUE. Again, let’s draw the truth table.
| A | B | A OR B |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
NOT Operation
NOT gate has one input and produces one output.
| A | NOT A |
| 0 | 1 |
| 1 | 0 |
NAND Operation
NOT and AND gate is the reverse of AND gate. The truth table looks as below.
| A | B | A NAND B |
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
XOR Operation
XOR or exclusive OR gate is only TRU when only one value is TRUE. In every other case it will be false. Let’s look at the truth table for this gate.
| A | B | A XOR B |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
Bitwise Shift Operation (<< and >>)
There are two different types of arithmetic shifts, left and right. The are used to shift bytes to the left or right. Left shift between two bit values is done using <<. Conversely, right shift between two bit values is done using >>. Let’s see couple of examples.
1) Left Shift by 1: 0010110 << 1 : 0101100 2) Left Shift by 2: 0010110 << 2 : 1011000 3) Right Shift by 2: 0010110 >> 2 : 0000101
0 value bit (not set) is added either to the left or right to complete the byte pattern. Remember the bits dropped are lost and cannot be recovered.. Also these operations are not circular i.e. removed bytes do not start start appearing from the other side.
Now that out of the way, let’s start writing the programs.
Maintaining Flags – Traditional Method
We will take two different approach here for setting/ unsetting flags. The code is commented so that I do not have to keep on referencing lines. The first method that we look at is traditional where we directly use bitwise operations to manipulate bits. Like I said before, a set state means the feature is active. Let’s see the code now.
public class Traditional {
/*
* Java byte is a 8 bit signed integer. So it can keep value between -128 to +127.
* That means the max value that I can store in Binary is 0b1111111. We will use
* this value for flag (we can of course use a subset, or chain more than one byte
* for keeping the flag value)
*/
private byte b1 = 0b0000000;
public Traditional() {
System.out.println("==== INIT ====");
System.out.println("Size of flag: " + (Byte.SIZE / 8) + " byte(s)");
System.out.println("==== END INIT ====");
}
public void printByte(final String pre) {
final String bint = Integer.toBinaryString(b1);
final String fmt = ("0000000" + bint).substring(bint.length());
System.out.println(pre + ": 0b" + fmt + " (" + b1 + ")");
}
/**
* JAVA ASSUMES ZERO BASED INDEX, WE ARE TAKING ONE BASED FOR EXAMPLE
* Assume a b1 of 0000000. We want to set 5.
* a) First shift bits of 1 by 5
* 0010000
* b) Now OR with this value original
* 0000000
* || 0010000
* -------------
* 0010000
* -------------
*/
public void setBit(final int which) {
b1 |= 1 << which;
printByte("Set Bit [" + which + "]");
}
/**
* JAVA ASSUMES ZERO BASED INDEX, WE ARE TAKING ONE BASED FOR EXAMPLE
* Assume a b1 of 0010000. We want to unset 5.
* a) Shift bits of 1 by 5
* 0010000
* b) Negate (NOT) it
* 1101111
* c) Now do a AND op
* 0010000
* && 1101111
* -------------
* 0000000
* -------------
*/
public void unsetBit(final int which) {
b1 &= ~(1 << which);
printByte("Unset Bit [" + which + "]");
}
/**
* JAVA ASSUMES ZERO BASED INDEX, WE ARE TAKING ONE BASED FOR EXAMPLE
* This is the XOR operation where we only set when one of them is true.
* Consider 0000000 again and switch bit 3
* Shifting by 3 for 1 gives us: 0000100
* Let's do a XOR with original.
* 0000000
* ^ 0000100
* -------------
* 0000100
* -------------
* So the bit is set. Let us try the same operation again.
*
* 0000100
* ^ 0000100
* -------------
* 0000000
* -------------
* That reset the value.
*/
public void switchBit(final int which) {
b1 ^= 1 << which;
printByte("Change Bit [" + which + "]");
}
/**
* JAVA ASSUMES ZERO BASED INDEX, WE ARE TAKING ONE BASED FOR EXAMPLE
* Identify if a bit is set. Move the pos to end and && with 1
* Consider 0000100.
* 1) Is bit 3 set?
* a) v >> 3 = 0000001 = v1
* b) v1 & 1 = 0000001 = v2
* c) v2 > 0: True
* 2) Is bit 4 set?
* a) v >> 3 = 0000000 = v1
* b) v1 & 1 = 0000000 = v2
* c) v2 = 0: False
*/
public boolean isBitSet(final int which) {
return ((b1 >> which) & 1) == 0 ? false : true;
}
/**
* Main class implementation
*/
public static void main(String[] args) throws Exception {
final Traditional app = new Traditional();
app.printByte("Initial String");
System.out.println("--> Setting 5th bit....");
app.setBit(5);
System.out.println("--> Unsetting 5th bit....");
app.unsetBit(5);
System.out.println("--> Changing 4th bit....");
app.switchBit(4);
System.out.println("--> Check if 4th and 5th bits are set....");
System.out.println(app.isBitSet(4));
System.out.println(app.isBitSet(5));
System.out.println("--> Changing 4th bit again....");
app.switchBit(4);
}
}Output for this looks as follows.
==== INIT ==== Size of flag: 1 byte(s) ==== END INIT ==== Initial String: 0b0000000 (0) --> Setting 5th bit.... Set Bit [5]: 0b0100000 (32) --> Unsetting 5th bit.... Unset Bit [5]: 0b0000000 (0) --> Changing 4th bit.... Change Bit [4]: 0b0010000 (16) --> Check if 4th and 5th bits are set.... true false --> Changing 4th bit again.... Change Bit [4]: 0b0000000 (0)
As you can see, we took a 8 bit signed integer and manipulated individual flags. Now this idea can be used to set/ unset 7 different features. Let’s take for example following scenario. We want to keep track of what days we have computer science, mechanics and electronics classes (assume a five day week). The first way that comes to mind of course is to keep them as an array of numbers for each day. Zero indicates we do not have class and One indicates we have class on that day. So, traditionally we can have the following.
private static byte[] comSciDays = {0, 1, 1, 1, 0};
private static byte[] mechanDays = {1, 0, 1, 0, 1};
private static byte[] electrDays = {1, 1, 0, 1, 0};Assuming array definition itself does not take any space, with this we are using 5 * 3 = 15 bytes. However, we can optimize this to just use 3 bytes as follows.
private static byte comSciDays = 0b0001110; private static byte mechanDays = 0b0010101; private static byte electrDays = 0b0011010;
Using flags we could save quite a few bytes here.
Maintaining Flags – Using BitSet
Java provides a BitSet class that also does the same thing. Next we will be implementing the same solution as above using BitSet methods. Remember we can always wrap these in an Enum to get a singleton for our project.
Let’s see the implementation now.
import java.util.BitSet;
public class BitwiseFun {
private BitSet b1 = new BitSet(7);
/**
* Notice that we are using a long in BitSet?
* So we would be using 8 bytes for each BitSet defined
*/
public BitwiseFun() {
System.out.println("==== INIT ====");
System.out.println("Size of flag: " + (b1.size() / 8) + " byte(s)");
System.out.println("8 bytes? Really??? Yes, internally it is represented by a long...");
System.out.println("See https://developer.classpath.org/doc/java/util/BitSet-source.html");
System.out.println("\tprivate long[] bits;");
System.out.println("==== END INIT ====");
}
public void printByte(final String pre) {
System.out.println(pre + ": " + b1.toString());
}
/**
* This will set the bit that we want to set.
* Using built in functions.
*/
public void setBit(final int which) {
b1.set(which);
printByte("Set Bit [" + which + "]");
}
/**
* Unset a bit using built in functions.
*/
public void unsetBit(final int which) {
b1.clear(which);
printByte("Unset Bit [" + which + "]");
}
/**
* Switching a bit again with built in functions.
*/
public void switchBit(final int which) {
b1.flip(which);
printByte("Change Bit [" + which + "]");
}
/**
*
* Test if a bit is set?
*/
public boolean isBitSet(final int which) {
return b1.get(which);
}
public static void main(String[] args) throws Exception {
final BitwiseFun app = new BitwiseFun();
app.printByte("Initial String");
System.out.println("--> Setting 5th bit....");
app.setBit(5);
System.out.println("--> Unsetting 5th bit....");
app.unsetBit(5);
System.out.println("--> Changing 4th bit....");
app.switchBit(4);
System.out.println("--> Check if 4th and 5th bits are set....");
System.out.println(app.isBitSet(4));
System.out.println(app.isBitSet(5));
System.out.println("--> Changing 4th bit again....");
app.switchBit(4);
}
}This makes it much more easier for us to implement the same thing. You do not need to understand how bits and setting them works. Java library takes care of it.
Here is the output.
==== INIT ====
Size of flag: 8 byte(s)
8 bytes? Really??? Yes, internally it is represented by a long...
See https://developer.classpath.org/doc/java/util/BitSet-source.html
private long[] bits;
==== END INIT ====
Initial String: {}
--> Setting 5th bit....
Set Bit [5]: {5}
--> Unsetting 5th bit....
Unset Bit [5]: {}
--> Changing 4th bit....
Change Bit [4]: {4}
--> Check if 4th and 5th bits are set....
true
false
--> Changing 4th bit again....
Change Bit [4]: {}
Conclusion
That was a quick look at setting flags using bits. If you need to save some “bytes”, make use of those “bits”. Ciao for now!