maybe fewest operations


  • 31
    int findComplement(int num) {
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        return num ^ mask;
    }
    

  • 0
    N
    This post is deleted!

  • 0
    N

    @StefanPochmann impressive


  • 0
    N

    Could you please explain the idea behind this solution?


  • 26
    M

    @NoAnyLove To understand the solution, we need to go backwards. The aim is to xor the given number with a mask. The mask should contain all 1s in its rightmost bits. However, the number of rightmost bits is important. In the case of 5(101), for example, the number of rightmost bits must be 3, since 5 uses 3 rightmost bits. The mask must be 111 for 5(101). When we xor 111 with 101, we will get 010. As another example, the mask will be 111111 for 38(100110)

    So the problem boils down to generating the mask. Let's think about 8-bit numbers. We can later extend the same logic to 32-bit integers. I will count the bits from right to left, starting with 1.

    The largest positive numbers represented by 8 bits will set 7th bit. 64(01000000) is the largest positive number represented by 8 bits, which has the most number of 0s. It is important for our explanation since we must turn all those 0s into 1s.

    The first operation, mask |= mask>>1; will set the 6th bit. So, mask will become (01100000). Now, we know that the 7th and 6th bits are set, we can safely shift the mask to right by not 1 but 2 bits. mask |= mask>>2; will now set the 5th and 4th bits. By the same reason, we can now shift the mask to right by not 1, 2 or 3 but 4 bits. That is the threshold for 8-bit numbers. We do not need to shift more.

    For 32-bit integers, the shift operations should continue until reaching to 16. For 64-bit longs, that will be 32.


  • 0
    N

    @Merter_Sualp Thanks


  • 0
    W

    @Merter_Sualp Wow, your explanation is easy to understand for me. Thanks~


  • 2
    B
    This post is deleted!

  • 1

    @bertkellerman Hmm, I hadn't even thought about that. Well, the "normal" complement operation is still different from the one requested here, so I think it's ok. But I agree that it's better to not use it at all.


  • 0
    V

    When you lookup highestOneBit source code in Integer.java, you will find same method.
    Google keyword "Hacker's Delight"


  • 0
    I

    @NoAnyLove mask |= mask >> 1will set the first left two bits to be 1, mask |= mask >> 2will set the first left four bits to be 1,
    mask |= mask >> 4will set the first left 8 bits to be 1, ... , at last, all the bits will be 1.


  • 0
    J

    Thanks! impressive!


  • 0

    @StefanPochmann

    impressive, but failed when num=0


  • 0

    @Vick.Chen said in maybe fewest operations:

    failed when num=0

    Irrelevant, as that is invalid input.


Log in to reply
 

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