Skip to content

693. Binary Number with Alternating Bits 👍

  • Time: $O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
 public:
  bool hasAlternatingBits(int n) {
    //            n = (010101)2
    //       n >> 2 = (000101)2
    // n ^ (n >> 2) = (010000)2 = a
    //        a - 1 = (001111)2
    //  a & (a - 1) = 0
    const int a = n ^ (n >> 2);
    return (a & (a - 1)) == 0;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
  public boolean hasAlternatingBits(int n) {
    //            n = (010101)2
    //       n >> 2 = (000101)2
    // n ^ (n >> 2) = (010000)2 = a
    //        a - 1 = (001111)2
    //  a & (a - 1) = 0
    final int a = n ^ (n >> 2);
    return (a & (a - 1)) == 0;
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def hasAlternatingBits(self, n: int) -> bool:
    #            n = (010101)2
    #       n >> 2 = (000101)2
    # n ^ (n >> 2) = (010000)2 = a
    #        a - 1 = (001111)2
    #  a & (a - 1) = 0
    a = n ^ (n >> 2)
    return (a & (a - 1)) == 0