Java, very simple code and self-evident, explanation


  • 31
    D

    for example:
    100110, its complement is 011001, the sum is 111111. So we only need get the min number large or equal to num, then do substraction

        public int findComplement(int num) 
        {
            int i = 0;
            int j = 0;
            
            while (i < num)
            {
                i += Math.pow(2, j);
                j++;
            }
            
            return i - num;
        }
    

  • 0
    L

    @dong-fantastic dong-dastic!


  • 0
    P

    said in Java, very simple code and self-evident, explanation:

    we only need get the min number large or equal to num

    can you explain "we only need get the min number large or equal to num"


  • 0
    J

    @PruthviUVSS
    actually this method is similiar as find 111 for 101, and then res=111-101。


  • 0
    W

    why I use the same algorithm, they warm me about time limit.


  • 0
    I

    @job_sucks Actually, it dose like that.


  • 9
    Y

    Same idea, but using bit manipulation instead of Math.pow().

    public class Solution {
        public int findComplement(int num) {
            int n = 0;
            while (n < num) {
                n = (n << 1) | 1;
            }
            return n - num;
        }
    }
    

  • 0
    A

    I don't understand, you use the bit 100110 which is 38, which passed into your function returns 25. But you say sum is 111111?
    What is the methodology to get a complement??


  • 1
    L

    @Alkarin Try what I wrote earlier in another thread:

    public int findComplement(int num) {
           //go to a higher number and do -1 from it to get everything as 1.
            int allones = (int)(Math.log10(Integer.highestOneBit(num))/Math.log10(2));
            allones = (1<<(allones+1))-1;
           //xor with the number to flip the bits.
            return num^allones;
        }
    

    So what I do is:

    If a number is say 4, then go to the highest bit , which is '1' in 100, and do a left shift and do a -1 from the number. This trick will get all lower bits for number 4 in 1s. For example for 4 it will do this:
    a. 100-> 1000->111 (so notice that we all have ones here for number
    b. num^ones will revert the bits. So again with example:

    111 ^ 100 => 011.

    Does it make sense?


  • 0
    A

    @labs Thanks for your reply. Your explanation makes sense but I don't understand your code(particularly the Math.log10)

    I am not 100% what you mean by -1? What is the purpose of that? I'll guess below:

    If I'm understanding correctly:
    So say you have 4 (100) and do a left shift, which is now (1000).
    you said do a -1 which I'm assuming gives (0111), removes the leading zero (111)
    which you then compare to the original 4 (100) which checks which digits are different returning 011.

    So is the number you are returning 11 in this case? or 2?


  • 0
    L

    No worries @ALKARIN . Let me explain the code:

    1. Notice that the question is asking you to complement only the part of the bits that has the highest bit set. For example, in the case of 4, it is the 2nd position(MSB; starting from 0).

    2. Considering 1), the idea is to find a complement for 4. The answer should be 3. Because
      (100) -> (011)

    3. The algorithm will go to the highest set bit of the number and then turn all bits on so that we could use it later for keeping our operations limited to the highest set bit only.

    4. Java has a method called highestSetBit(int) that returns the integer value that will be returned with the higest set bit. If you use this method on 5, it will return 4 because the number is (101) and the highest set bit is at the position of number 4. For 4, it will return 4.

    5. Now, get the number that has the highest set bit. It is supposed to be a power of 2 because Java returns the set bit only for that highest position.

    6. Let us say for your example of 4, Java will return 4 for highestbitset. Now, we use log(4)/log2 to calculate log4 with base 2 to figure out the index of the highest set bit. It will return 2 in our example.

    7). Now, my aim is to get 1s at all positions till the highest set bit. So firstly, I will shift 1 left by 2+1 to get only one bit set beyond our highest bit. Doing a minus 1 from this number will take away the highest bit that we set and then spread only 1s for all the bits for our number. Like if it was 4 then what we did was:
    a. got 2 for number of highest bits
    b. 1<<2+1 will get us 8 which is 1000
    c. 8-1 will remove 1 at the leftmost side and spread 1s at all 3 bits: 0111

    1. After all the above, we managed to find a bit set that matches our given number with all 1s.

    2. If you do a XOR at this stage, it will flip all our original bits thus giving us a complement.

    So the complement will be 100 ^ 111 = 011. The decimal value for 011 is 3 and that is our answer.


  • 0
    A

    Good solution


  • 0
    Z
    public int findComplement(int num) {
        long dig=(long)(Math.log(num)/Math.log(2)+1);
        long sum=(long)Math.pow(2,dig)-1;
        return (int)sum-num;
    }

  • 0
    D

    Impressive solution!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.