https://leetcode.com/problems/binary-number-with-alternating-bits/description/
https://leetcode.com/problems/binary-number-with-alternating-bits/discuss/108427/Oneliners-(C%2B%2B-Java-Ruby-Python)
String bits = Integer.toBinaryString(n);
for (int i = 0; i < bits.length() - 1; i++) {
if (bits.charAt(i) == bits.charAt(i+1)) {
return false;
}
}
return true;
}
https://leetcode.com/problems/binary-number-with-alternating-bits/discuss/113933/Java-super-simple-explanation-with-inline-example
Time Complexity: . For arbitrary inputs, we do work, where is the number of bits in
public boolean hasAlternatingBits(int n) {
int cur = n % 2;
n /= 2;
while (n > 0) {
if (cur == n % 2) return false;
cur = n % 2;
n /= 2;
}
return true;
}
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.
Solution 1 - Cancel Bits
bool hasAlternatingBits(int n) {
return !((n ^= n/4) & n-1);
}
Xor the number with itself shifted right twice and check whether everything after the leading 1-bit became/stayed 0. Xor is 0 iff the bits are equal, so we get 0-bits iff the pair of leading 1-bit and the 0-bit in front of it are repeated until the end.
000101010
^ 000001010
= 000100000
Solution 2 - Complete Bits
bool hasAlternatingBits(int n) {
return !((n ^= n/2) & n+1);
}
Xor the number with itself shifted right once and check whether everything after the leading 1-bit became/stayed 1. Xor is 1 iff the bits differ, so we get 1-bits iff starting with the leading 1-bit, the bits alternate between 1 and 0.
000101010
^ 000010101
= 000111111
Solution 3 - Positive RegEx
public boolean hasAlternatingBits(int n) {
return Integer.toBinaryString(n).matches("(10)*1?");
}
It's simple to describe with a regular expression.
Solution 4 - Negative RegEx
def has_alternating_bits(n)
n.to_s(2) !~ /00|11/
end
It's even simpler to describe what we don't want: two zeros or ones in a row.
Solution 5 - Negative String
def hasAlternatingBits(self, n):
return '00' not in bin(n) and '11' not in bin(n)
Same as before, just not using regex.
Solution 6 - Golfed
def has_alternating_bits(n)
(n^=n/2)&n+1<1
end
Solution 7 - Recursion
def has_alternating_bits(n)
n < 3 || n%2 != n/2%2 && has_alternating_bits(n/2)
end
Compare the last two bits and recurse with the last bit shifted out.
Solution 8 - Complete Bits + RegEx
public boolean hasAlternatingBits(int n) {
return Integer.toBinaryString(n ^ n/2).matches("1+");
}
- Time Complexity: . For arbitrary inputs, we do work, where is the number of bits in
n
. However, . - Space complexity: , or alternatively .
String bits = Integer.toBinaryString(n);
for (int i = 0; i < bits.length() - 1; i++) {
if (bits.charAt(i) == bits.charAt(i+1)) {
return false;
}
}
return true;
}
https://leetcode.com/problems/binary-number-with-alternating-bits/discuss/113933/Java-super-simple-explanation-with-inline-example
public boolean hasAlternatingBits(int n) {
int cur = 0, pre = -1;
while(n != 0) {
cur = n & 1;
if(cur == pre) return false;
n >>>= 1;
pre = cur;
}
return true;
}
Approach #2: Divide By Two [Accepted]
We can get the last bit and the rest of the bits via
n % 2
and n // 2
operations. Let's remember cur
, the last bit of n
. If the last bit ever equals the last bit of the remaining, then two adjacent bits have the same value, and the answer is False
. Otherwise, the answer is True
.
Also note that instead of
n % 2
and n // 2
, we could have used operators n & 1
and n >>= 1
instead.n
. However, .public boolean hasAlternatingBits(int n) {
int cur = n % 2;
n /= 2;
while (n > 0) {
if (cur == n % 2) return false;
cur = n % 2;
n /= 2;
}
return true;
}