693. Binary Number with Alternating Bits

693. Binary Number with Alternating Bits

Easy

945103Add to ListShare

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Example 1:

Input: n = 5
Output: true
Explanation: The binary representation of 5 is: 101

Example 2:

Input: n = 7
Output: false
Explanation: The binary representation of 7 is: 111.

Example 3:

Input: n = 11
Output: false
Explanation: The binary representation of 11 is: 1011.

Constraints:

• 1 <= n <= 231 - 1

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        """
        assert Solution().hasAlternatingBits(5)
        相邻2个二进制位不同

        解题思路：简单的判断当前最后末尾位与之前的末位是否相同，相同的返回False，
        不相同向右移一位接着重复，直到为0
        时间复杂度：O(logn)

        参考别人的解题思路：
        n =         1 0 1 0 1 0 1 0
        n >> 1      0 1 0 1 0 1 0 1
        这里不能直接 n & (n >> 1)  assert not Solution().hasAlternatingBits(4)
        n ^ n>>1    1 1 1 1 1 1 1 1
        n           1 1 1 1 1 1 1 1
        n + 1     1 0 0 0 0 0 0 0 0
        n & (n+1)   0 0 0 0 0 0 0 0
        时间复杂度：O(1)

        """
        # last = n & 1
        # n >>= 1
        # while n != 0:
        #     if last == (n & 1):
        #         return False
        #     last = n & 1
        #     n >>= 1
        # return True

        n = n ^ n >> 1
        return n & (n + 1) == 0