leetcode 476. Number Complement | 476. 数字的补数(位运算)

x33g5p2x  于2021-12-27 转载在 其他  
字(1.0k)|赞(0)|评价(0)|浏览(166)

题目

https://leetcode.com/problems/number-complement/

题解

class Solution {
    public int findComplement(int num) {
        int i = Integer.numberOfLeadingZeros(num);
        return ~num << i >> i;
    }
}

也可以参考评论区的答案:

Idea:

  • Flip all bits using negation operator (~) [read more here]
  • Logical AND (&) with a bit a mask of size n whose all bits are set, where n = number of bits in num
    Example:
num = 5
  num binary = 0...0101
 ~num binary = 1...1010

* Now we've flipped all the bits but it also flipped previously insignificant bits (0s), 
so to revert them back to 0s, we need to only keep the significant bits and turn off the insignificant bits. 
* This can be done by using mask of 1s having size equal to number of bits in num. This mask is (1 << nBits) - 1. 
* This is a standard mask in bit manipulation problems..

~num binary & mask = (1...1010) & (0...0111) = 0...0010 [Ans]

T/S: O(1)/O(1)

public int findComplement(int num) {
	var nBits = (int) Math.floor((Math.log(num) / Math.log(2)) + 1);
	var mask = (1 << nBits) - 1;
	return ~num & mask;
}

1 liner variation of above method

public int findComplement(int num) {
	return ~num & (Integer.highestOneBit(num) - 1);
}

相关文章

微信公众号

最新文章

更多