Description
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:
Solutions
Solution 1: Simulation
We cyclically right-shift n until it becomes 0, checking whether the binary bits of n appear alternately. If during the loop we find that 0 and 1 do not appear alternately, we directly return false. Otherwise, when the loop ends, we return true.
The time complexity is O(log n), and the space complexity is O(1).
PythonJavaC++GoTypeScriptRust
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
prev = -1
while n:
curr = n & 1
if prev == curr:
return False
prev = curr
n >>= 1
return True(code-box)
class Solution {
public boolean hasAlternatingBits(int n) {
int prev = -1;
while (n != 0) {
int curr = n & 1;
if (prev == curr) {
return false;
}
prev = curr;
n >>= 1;
}
return true;
}
}(code-box)
class Solution {
public:
bool hasAlternatingBits(int n) {
int prev = -1;
while (n) {
int curr = n & 1;
if (prev == curr) return false;
prev = curr;
n >>= 1;
}
return true;
}
};(code-box)
func hasAlternatingBits(n int) bool {
prev := -1
for n != 0 {
curr := n & 1
if prev == curr {
return false
}
prev = curr
n >>= 1
}
return true
}(code-box)
function hasAlternatingBits(n: number): boolean {
let prev = -1;
while (n !== 0) {
const curr = n & 1;
if (prev === curr) {
return false;
}
prev = curr;
n >>= 1;
}
return true;
}(code-box)
impl Solution {
pub fn has_alternating_bits(mut n: i32) -> bool {
let mut prev: i32 = -1;
while n != 0 {
let curr = n & 1;
if prev == curr {
return false;
}
prev = curr;
n >>= 1;
}
true
}
}(code-box)
Solution 2: Bit Manipulation
Assuming 01 appears alternately, we can convert all trailing bits to 1 through misaligned XOR. Adding 1 gives us a power of 2, which is a number n (where n has only one bit that is 1). Then, using n & (n + 1) can eliminate the last 1 bit.
At this point, check if it equals 0. If so, the assumption holds, and it is an alternating 01 sequence.
The time complexity is O(1), and the space complexity is O(1).
PythonJavaC++GoTypeScriptRust
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
n ^= n >> 1
return (n & (n + 1)) == 0(code-box)
class Solution {
public boolean hasAlternatingBits(int n) {
n ^= (n >> 1);
return (n & (n + 1)) == 0;
}
}(code-box)
class Solution {
public:
bool hasAlternatingBits(int n) {
n ^= (n >> 1);
return (n & ((long) n + 1)) == 0;
}
};(code-box)
func hasAlternatingBits(n int) bool {
n ^= (n >> 1)
return (n & (n + 1)) == 0
}(code-box)
function hasAlternatingBits(n: number): boolean {
n ^= n >> 1;
return (n & (n + 1)) === 0;
}(code-box)
impl Solution {
pub fn has_alternating_bits(n: i32) -> bool {
let mut x = n ^ (n >> 1);
(x & (x + 1)) == 0
}
}(code-box)
