LeetCode 693. Binary Number with Alternating Bits(交替位的二进制数)
题目描述
Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.
Example 1:
Input: 5
Output: True
Explanation:
The binary representation of 5 is: 101
Example 2:
Input: 7
Output: False
Explanation:
The binary representation of 7 is: 111.
Example 3:
Input: 11
Output: False
Explanation:
The binary representation of 11 is: 1011.
Example 4:
Input: 10
Output: True
Explanation:
The binary representation of 10 is: 1010.
解法一
思路
这题是要检查数字的二进制表示中,0
和1
是不是交错出现的,顺着来一位一位检查就好了。
考虑从低位向高位检查,每次都要求后一位的值和前一位的值不相同,那么中止条件是什么呢?一个很明显的是后一位和前一位的值相同了,而另一个则是已经到了二进制表示的最高位,即再往后就不再有1
了。
为了代码的简洁,我们可以每次检查数字二进制的最低位的值后,将数字向右移位一位,这样每次都只需要检查二进制最低位就好了。当这个检查过程中止后,就只需要检查当前的数字是不是0
(二进制表示不再有1
)就好了。
Python
class Solution:
def hasAlternatingBits(self, n):
"""
:type n: int
:rtype: bool
"""
last = n & 1
while n != 0 and n & 1 == last:
last = 1 - last
n >>= 1
return n == 0
Java
class Solution {
public boolean hasAlternatingBits(int n) {
int last = n & 1;
while (n != 0 && (n & 1) == last) {
last = 1 - last;
n >>= 1;
}
return n == 0;
}
}
C++
class Solution {
public:
bool hasAlternatingBits(int n) {
bool last = n & 1;
while (n != 0 && (n & 1) == last) {
last = 1 - last;
n >>= 1;
}
return n == 0;
}
};