1

This is from a hacker rank practice problem(not a competition) https://www.hackerrank.com/challenges/flipping-bits. Just doing this for practice.
The problem just asks you to take a set number for 32 bit integers and for each one, invert all the bits inside that integer and print out the result Here's my code so far

 static long getComplement(long c) {
    long complement = 0;
    for(int k = 31; k >= 0 ; k --) {
        long evaluateBit = c >> k;
        if(evaluateBit == 1) {
            evaluateBit = 0;
        }  else {
            evaluateBit = 1;
        }
        complement += evaluateBit << k;
     }
    return complement;
}

Here is my high level pseudo code thinking. I will evaluate every bit in the integer. To do this, I have to right shift the bit by its position(something that was at position 31 would have to be right shifted by 31 to get to position 0 so I can evaluate it). That's why my loop started at 31 and ends at 0. And then once i get the bit at that position, I will invert it with a conditional statement and then left shift the result by the same result. I will finally add it to the sum I am keeping (what was 0 * 2 ^ 31 will consist of 1 * 2 ^ 31)

Does anyone see any problems with my pseudo code?

There has to be a problem because when I tried running the code in my IDE, here is what I got when I debugged the code enter image description here

I tried doing a test run with a input of 0. After my first run(k=31), I somehow get a negative number. Does anyone know what the problem is or how I can fix this?

I made sure that I used the right shift operators as well, from How do shift operators work in Java?

Community
  • 1
  • 1
committedandroider
  • 8,711
  • 14
  • 71
  • 126

1 Answers1

2

Your first iteration changes the left most bit from 0 to 1. This is the sign bit, so of course you got a negative number.

EDIT :

change

evaluateBit = (c >> k);

to

evaluateBit = (c >> k) & 1;

In order for evaluateBit to really contain the value of a single bit.

Eran
  • 387,369
  • 54
  • 702
  • 768
  • For input of 0 to this problem, I am supposed to get 4294967295 , not -1. – committedandroider Feb 07 '15 at 19:03
  • @committedandroider That's because the assignment specifically asks to use unsigned integers but you're using signed integers. – JJJ Feb 07 '15 at 19:04
  • yeah but from http://stackoverflow.com/questions/9854166/declaring-an-unsigned-int-in-java, java has no unsigned integers – committedandroider Feb 07 '15 at 19:05
  • @Juhana you guys were right. It was due to the data type. I changed all the data types in that method to long so this will no longer be an issue. But I am still getting the incorrect output for input of 2147483647. The expected is 2147483648 but I am getting 3221225471. Do guys see what the issue is? – committedandroider Feb 07 '15 at 19:10
  • @committedandroider 4294967295 is not within the range of int, so you can't get that output for a 0 input. – Eran Feb 07 '15 at 19:10
  • @Eran Thanks I changed that, but do you know why that code segment is getting the wrong output for input of 2147483647? This would take way too long to debug for me. – committedandroider Feb 07 '15 at 19:11
  • @Eran the issue was if I had something like 100(1).....0 and I were to right shift everything by 28 to evaluate that bit, I would get 0....1001, which I wanted to into this block if(evaluateBit == 1) but it actually went into the else block because 1001 is not 1? – committedandroider Feb 07 '15 at 19:28
  • @committedandroider yes – Eran Feb 07 '15 at 19:30