Why diff&[~(diff - 1)] can pick one bit that is one?


  • 1
    Y

    Why diff&[~(diff - 1)] can pick one bit that is one?Could anybody help me with this problem?Thank you very much in advance!


  • 0
    F

    ~(diff -1) negates all of the bit in diff except the first binary bit (low-bit), then diff &(~(diff -1)) can only pick one bit which is the first binary bit in diff.
    For example, a=0011; b=0101; a xor b=0110
    (a xor b)-1=0101; ~(a xor b)=1010;
    (a xor b)&(~(a xor b))=0110^1010=0010 (just pick up one binary bit in diff)


  • 0
    J

    i think you mean "0110&1010", not "0110^1010".


  • 0
    X

    In fact, ~(diff - 1) equals -diff. Here needs some complement-code knowledge.


  • 0
    P

    here it is.

    r = r1|r2, r2 is the right part contain the last bit 1.(eg. if r = 10011000, then r2 = 1000).

    r&~(r-1) = r&~((r1|r2)-1) = r&~(r1|~r2) = r&(~r1|r2) = (r&~r1)|(r&r2) = r2|r2 = r2


Log in to reply
 

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