3 line C++


  • 75
    L
    class Solution {
    public:
        int findComplement(int num) {
            unsigned mask = ~0;
            while (num & mask) mask <<= 1;
            return ~mask & ~num;
        }
    };
    

    For example,

    num          = 00000101
    mask         = 11111000
    ~mask & ~num = 00000010
    

  • 12
    K

    or

    class Solution {
    public:
        int findComplement(int num) {
            unsigned mask = ~0;
            while (num & mask) mask <<= 1;
            return num ^ ~mask;
        }
    };
    

  • 1
    B

    Hi lzl,

    Thank you for sharing your code. Could you please help me with the following quick question regarding your code?

    Seems it is important to define variable "mask" using "unsigned" type, I tried to define it as "int" type but there was Run Time Error. Could you please explain a little why "int" type will case failure here?

    Thank you in advance


  • 0

    @BSKLK I got AC if use int... No idea why you get RTE.

    I think you could use int in this case to save some typing. I used unsigned for masks whenever I'm doing bit manipulation so that I don't need to care the shift direction:

    ((unsigned)~0) >> 1 == 01111111111111111111111111111111
    ~0 >> 1             == 11111111111111111111111111111111
    

  • 2
    M
    while (num & mask) mask <<= 1;
    

    I am confused about this line. Could you explain it in detail? What is the purpose of the while loop and what does <<= 1 accomplish?


  • 1
    Y

    In Python

    class Solution(object):
        def findComplement(self, num):
            
            x = len(bin(num)[2:])
            m = int('1'*x,2)
            return m^num
    

  • 16

    @mawills In English, it's "as long as num and mask has bit 1 at the same place (i.e. overlap), shift mask left by one bit"

    For example

    num          = 00000101
    mask         = 11111111
                        ^ ^ overlap!
    num          = 00000101
    mask         = 11111110
                        ^   overlap!
    num          = 00000101
    mask         = 11111100
                        ^   overlap!
    num          = 00000101
    mask         = 11111000
                              clear!
    

  • 0
    M

    @lzl124631x I think I understand it now, thank you!


  • 1

    very cool, I didn't think of inverting the mask, rather I built up my mask to be set bits up to the point where the most signification bit is covered.

        public int FindComplement(int num) 
        {
            int mask = 1;
            while (mask < num) mask = (mask << 1) | 1;
            return ~num & mask;
        }
    

  • 0
    S

    @jdrogin The last line can be " return num ^ mask; " -- one less operation.


  • 0
    D

    Hi. I have a question about this solution. For the while loop, if I use

    while (num & mask != 0) mask <<= 1;
    

    instead of

    while (num & mask) mask <<= 1;
    

    then I got incorrect answer. So the difference is in that != 0

    I do not understand why. Could you tell me why that would be wrong? Thank you.


  • 0

    @dragonhyq-gmail.com mask << 1 doesn't change mask. mask <<= 1; does.


  • 0
    D

    @lzl124631x Hi. I am very sorry I had a typo in my post, I have edited it. Could you take a look again? I think I understand the entire process of creating the mask, shifting the mask, and flipping the lower bits. But that !=0 thing eludes me...

    Thank you in advance!


  • 0
    V

    Have u considered the input parameters of the function? It needs to be 32-bit signed integer. Please check ur code.


  • 0

    @dragonhyq-gmail.com Be cautious when using bitwise operators. Checkout the C++ operator priorities. & is even of lower priority than !=.

    IMHO, if you are not sure the priority, always enclose bistwise binary operators & | ^ in parentheses, e.g. while((num & mask) != 0).


  • 0

    @veeperbupt does it matter? please check again.


  • 0
    D

    @lzl124631x You are right! It is the priority! Thank you!


  • -1
    H

    I think my solution is easier than you ,but it can't pass the tests , some cases make it Time Limit Exceeded ,I can't find out it, I test some cases in my own IDE,it pass all.,canld you help me?
    class Solution { Time Limit Exceeded
    public:
    int findComplement(int num) {
    int tmp = 1;
    while (tmp <= num) tmp <<= 1;
    return (tmp - num - 1);
    }
    };


  • 0
    F

    @sgsg it should be ~mask ^ num :-)


  • 0
    M

    My code is very similar to yours, but still i get "error: expected unqualified-id before string constant" It seems to run properly in my IDE. any ideas where I am making a mistake ?

            int n = ceil(log2(num));
            int mask = (pow(2,n)-1);
            int answer = ~num & mask;
            //std::cout<< ( bitset<32>(~num) & bitset<32>(pow(2,n)-1) ).to_ulong();
            return answer;
    

Log in to reply
 

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