It is Sunday February 02, 2020 (02022020) and today’s date is a palindrome. Lunch yesterday was great. All the food my wife and I cooked turned out quite tasty. Today we will make a salad and sandwiches using a brioche bread loaf that we get at Trader Joe’s. We need to consume simpler and hopefully less food.
I decided to work on HackerRank Flipping bits problem. I decided to use Java 8. The problem has to do with bit manipulations. In my humble opinion, C is a much better suited language than Java.
I am using Visual Studio Code as my IDE.
3 2147483647 1 0 2147483648 4294967294 4294967295 2 4 123456 4294967291 4294843839 3 0 802743475 35601423 4294967295 3492223820 4259365872
The test scaffolding follows:
// **** scanner ****
private static final Scanner scanner = new Scanner(System.in);
/**
* Test scaffolding.
*/
public static void main(String[] args) throws IOException {
// **** ****
// BufferedWriter bufferedWriter = new BufferedWriter(new
// FileWriter(System.getenv("OUTPUT_PATH")));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// **** ****
int q = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// // ???? ????
// System.out.println("main <<< q: " + q);
// **** ****
for (int qItr = 0; qItr < q; qItr++) {
// **** ****
long n = scanner.nextLong();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// // ???? ????
// System.out.println("main <<< n: " + n);
// **** ****
long result = flippingBits(n);
// long result = flippingBits1(n);
// long result = flippingBits2(n);
// **** ****
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
// **** close buffered writer ****
bufferedWriter.close();
// **** close scanner ****
scanner.close();
}
Not much to see here. We are given the number of values to process. For each value we read a long value, flips its bits and return the long number. All processing is done in the flippingBits() function.
/**
* Complete the flippingBits function below.
*/
static long flippingBits(long n) {
// **** instantiate a big integer with the specified value ****
BigInteger bn = new BigInteger(Long.toString(n));
// **** traverse the big integer flipping bits ****
for (int i = 0; i < Integer.SIZE; i++) {
bn = bn.flipBit(i);
}
// **** return the long representation of the big integer ****
return bn.longValue();
}
We start by instantiating a big integer with the specified value. We then traverse the big integer flipping one bit at a time. We then return the long 
representation of the big integer. It looks simple, clean and perhaps somewhat elegant. I have spent a few years developing code in assembly language, C and C++. When you deal with binary data it is simple and you can easily understand what you and the CPU are doing, not to mention the better performance of the software. This function does not seem to embrace such accolades.
That said; I experimented with other versions of the code.
/**
* Complete the flippingBits function below.
*/
static long flippingBits1(long n) {
// ???? ????
String s = Long.toBinaryString(n);
System.out.println("flippingBits <<< ORIGINAL s ==>" + s + "<==");
// **** prepend '0' ****
while (s.length() < Integer.SIZE) {
s = "0" + s;
}
// ???? ????
System.out.println("flippingBits <<< BEFORE s ==>" + s + "<== len: " + s.length());
// **** flip bits ****
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '0') {
sb.append("1");
} else {
sb.append("0");
}
}
s = sb.toString();
// ???? ????
System.out.println("flippingBits <<< AFTER s ==>" + s + "<== len: " + s.length());
// **** ****
n = Integer.parseUnsignedInt(s, 2);
// **** ****
return (long) Integer.toUnsignedLong((int) n);
}
I tried to experiment with the actual bits. The issue is that integers seem to contain 32 bits and long contain 64 bits. How Java displays values seems somewhat interesting. In C / C++ when you have a long integer you can define it as being an integer or an unsigned integer. When you display the values the sign is handled by the compiler. The result is what you expect. In this case it does not seem to intuitive.
3 2147483647 1 0 flippingBits <<< ORIGINAL s ==>1111111111111111111111111111111<== flippingBits <<< BEFORE s ==>01111111111111111111111111111111<== len: 32 flippingBits <<< AFTER s ==>10000000000000000000000000000000<== len: 32 flippingBits <<< ORIGINAL s ==>1<== flippingBits <<< BEFORE s ==>00000000000000000000000000000001<== len: 32 flippingBits <<< AFTER s ==>11111111111111111111111111111110<== len: 32 flippingBits <<< ORIGINAL s ==>0<== flippingBits <<< BEFORE s ==>00000000000000000000000000000000<== len: 32 flippingBits <<< AFTER s ==>11111111111111111111111111111111<== len: 32 2147483648 4294967294 4294967295 2 4 123456 4294967291 4294843839 flippingBits <<< ORIGINAL s ==>100<== flippingBits <<< BEFORE s ==>00000000000000000000000000000100<== len: 32 flippingBits <<< AFTER s ==>11111111111111111111111111111011<== len: 32 flippingBits <<< ORIGINAL s ==>11110001001000000<== flippingBits <<< BEFORE s ==>00000000000000011110001001000000<== len: 32 flippingBits <<< AFTER s ==>11111111111111100001110110111111<== len: 32 4294967291 4294843839 3 0 802743475 35601423 4294967295 3492223820 4259365872 flippingBits <<< ORIGINAL s ==>0<== flippingBits <<< BEFORE s ==>00000000000000000000000000000000<== len: 32 flippingBits <<< AFTER s ==>11111111111111111111111111111111<== len: 32 flippingBits <<< ORIGINAL s ==>101111110110001110010010110011<== flippingBits <<< BEFORE s ==>00101111110110001110010010110011<== len: 32 flippingBits <<< AFTER s ==>11010000001001110001101101001100<== len: 32 flippingBits <<< ORIGINAL s ==>10000111110011110000001111<== flippingBits <<< BEFORE s ==>00000010000111110011110000001111<== len: 32 flippingBits <<< AFTER s ==>11111101111000001100001111110000<== len: 32 4294967295 3492223820 4259365872
As you can see we obtain the same results but the code is not clean.
I spent some time experimenting with yet a different implementation. At some point I decided to give up and give it a try with C.
TestFlippingBits <<< result: 2147483648 <== first test TestFlippingBits <<< result: 4294967294 TestFlippingBits <<< result: 4294967295 TestFlippingBits <<< result: 4294967291 <== second test TestFlippingBits <<< result: 4294843839 TestFlippingBits <<< result: 4294967295 <== third test TestFlippingBits <<< result: 3492223820 TestFlippingBits <<< result: 4259365872
The screen capture from the console of Visual Studio 2013 Enterprise Edition (have different versions up to 2019) shows the edited output of the TestFlippingBits() function. Note that the values seem to match the values of previous tests performed on the Java version of the program.
int __stdcall TestFlippingBits (
void
)
// ***************************************************************@@
// - Test the FlippingBits function with a set of specified values.
// *****************************************************************
{
static long values[] = {
2147483647,
1,
0,
4,
123456,
0,
802743475,
35601423
};
int retVal, // value returned by this function
status; // returned by function calls
long result; // returned by function call
// **** initialization ****
retVal = 0; // hope all goes well
result = (long)0L; // for starters
// **** loop calling the FlippingBits function ****
for (int i = 0; i < sizeof(values) / sizeof(long); i++)
{
result = FlippingBits(values[i]);
printf("TestFlippingBits <<< result: %lu\n", result);
}
// **** clean up ****
done:
// **** inform the user what is going on ****
if ((traceExecution != 0) || (retVal != 0))
EventLog(EVENT_INFO,
"TestFlippingBits <<< retVal: %d line: %d\n",
retVal, __LINE__);
// **** inform the caller what went on ****
return retVal;
}
The TestFlippingBits() function declares an array of eight values. You can verify that these values match the ones in the three samples in the challenge by HackerRank.
The test function consists of a loop that calls the FlippingBits() function once per value in the array. The result is displayed.
Please note that there are other variables (i.e., retVal and status) that are not being used. I just wanted to illustrate the template used when developing C code. All functions return an integer value (retVal = 0 implies all is well, any other value comes from a set of error codes associated with a text description that is displayed / logged to a log file). In this case since we do not check errors, the retVal is set to 0.
__declspec(dllexport) long __stdcall FlippingBits (
long n
)
// *************************************************************@@
// Flip all bits in the specified value.
// ***************************************************************
{
int retVal, // value returned by this function
status; // returned by function calls
// **** initialization ****
retVal = 0; // hope all goes well
// **** flip all the bits in the specified value ****
n ^= 0xffffffff;
// **** clean up ****
done :
// **** inform the user what is going on ****
if ((traceExecution != 0) || (retVal != 0))
EventLog(EVENT_INFO,
"FlippingBits <<< retVal: %d line: %d\n",
retVal, __LINE__);
// **** return the result ****
return n;
}
The FlippingBits() function is quite simple. To be honest, flipping bits in C / C++ is so common that the operation seldom is called as a separate function. We just take the value and perform an XOR operation. Of course, it would be a good idea to check if the size of the long value is 32 or 64 bits. That would change the constant (in production it should be a defined or final value) from 0xffffffff to 0xffffffffffffffff.
In this function we do not make use of the retVal. In practice we would have passed the address (reference) of n and not return the result in the returned value. Consistency is very important in software development.
/**
* Complete the flippingBits function below.
*/
static long flippingBits3(long n) {
// **** ****
long nf = 0L;
// ???? ????
System.out.println("flippingBits3 <<< Integer.SIZE: " + Integer.SIZE);
System.out.println("flippingBits3 <<< Long.SIZE: " + Long.SIZE);
// **** XOR ****
nf = n ^ 0x00000000ffffffffL;
// ???? ????
System.out.println("flippingBits3 <<< nf ==>" + Long.toBinaryString(nf) + "<==");
// **** ****
return nf;
}
I decided to show one more attempt. This was the first attempt I did in Java which should mimic the C code version. In my opinion the constant 0x00000000ffffffffL is not intuitive. It works but I decided to go with the BigInteger implementation show earlier in this post.
3 2147483647 1 0 flippingBits3 <<< Integer.SIZE: 32 flippingBits3 <<< Long.SIZE: 64 flippingBits3 <<< nf ==>10000000000000000000000000000000<== flippingBits3 <<< Integer.SIZE: 32 flippingBits3 <<< Long.SIZE: 64 flippingBits3 <<< nf ==>11111111111111111111111111111110<== flippingBits3 <<< Integer.SIZE: 32 flippingBits3 <<< Long.SIZE: 64 flippingBits3 <<< nf ==>11111111111111111111111111111111<== 2147483648 4294967294 4294967295
You can see that the bits have been properly set and the test scaffolding displays the values correctly.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Twitter: @john_canessa