Replacing characters takes a very long time in a string
I am trying to replace one character (bit) in a string that is a binary number. For bit replacement, I developed a method that simply splits the string using the method string.substring()
corresponding to the given index, then concatenates everything. Following is the method -
/*
*Method will replace the index-th bit with bitToInsert in the given str
*/
String str = "11000110100110011111";
int index = 5;
int bitToInsert = 0;
if (index == 0) {
str = str.substring(0, str.length() - 1) + bitToInsert;
} else {
str = str.substring(0, str.length() - index - 1) + bitToInsert + str.substring(str.length() - index);
}
This works great, however it takes a very long time to swap bits if the given str is very large. Is there any other way so that replacing any bit can be done in less time compared to the above method?
source to share
The performance issues you are seeing are because Java strings are immutable. In other words, the string cannot be changed after it has been created. So, to change one character in a String, the JVM has to make a copy of the entire string, which will take some time if it's a large string.
In the above code, it is actually even worse than copying the first part of the string and the second part of the string separately from one character, and then copying those copies into the final result, you can improve performance if the above code usingStringBuilder
to create the target string so you only need to make a copy once.
If you are really dealing with a long binary number, you should useBitSet
. How well this works for you will depend on what you do with the data, once you've flipped some bits.
String str = "11000110100110011111";
BitSet bitSet = new BitSet(str.length());
//All bits are unset at first so set any that correspond to a '1' in the String
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '1') {
bitSet.set(i);
}
}
int index = 5;
boolean bitToInsert = false; //i.e. 0
bitSet.set(index, bitToInsert);
source to share
Using BitSet and StringBuffer is a good idea. However, I have another suggestion optimized for low memory and high speed .
Use int or long depending on how long your binary number is. If it can't fit into the ints / long array that best suits your needs.
I'll demonstrate here how you use a byte type array to store 11000110100110011111:
byte [] bits = new byte[1000];
String str = "11000110100110011111";
int arrayIndex=0; //position in array
int bitIndex=0; //which bit at bits[arrayIndex] is it
//put your bits into a byte array
for (int i=0; i<str.length(); i++){
arrayIndex = i / 8;
bitIndex = i % 8; //you can have max 8 bits in a byte
bits[arrayIndex]= (byte) (bits[arrayIndex] | ((Byte.parseByte(""+str.charAt(i)) << bitIndex)));
}
This is how you change a specific bit:
//for replacing bit bitNumber with bitValue (where bitValue is 0 or 1)
void changeBit(int bitNumber, byte bitValue){
int arrayIndex= bitNumber / 8;
int bitIndex= bitNumber % 8;
//clear bit first
byte crtBit = (byte)(1 << bitIndex);
crtBit = (byte) ~crtBit;
bits[arrayIndex]= (byte) (bits[arrayIndex] & crtBit);
//set bit to new value
bits[arrayIndex]= (byte) (bits[arrayIndex] | (bitValue << bitIndex));
}
source to share