Skip to content

3125. Maximum Number That Makes Result of Bitwise AND Zero 👍

  • Time: $O(\log n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  long long maxNumber(long long n) {
    // assume n = 0b00...11???
    //        x = 0b00...01111
    //  since y = 0b00...10000 is in [x, n]
    //    and x & y = 0
    const int i = 63 - __builtin_clzll(n);
    return (1L << i) - 1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
  public long maxNumber(long n) {
    // assume n = 0b00...11???
    //        x = 0b00...01111
    //  since y = 0b00...10000 is in [x, n]
    //    and x & y = 0
    final int i = 63 - Long.numberOfLeadingZeros(n);
    return (1L << i) - 1;
  }
}

1
2
3
4
5
6
7
class Solution:
  def maxNumber(self, n: int) -> int:
    # assume n = 0b00...11???
    #        x = 0b00...01111
    #  since y = 0b00...10000 is in [x, n]
    #    and x & y = 0
    return (1 << n.bit_length() - 1) - 1