I'm a beginner programmer working on the problem of determining whether an integer's binary representation has alternating 0s and 1s. I wrote this Java solution, but I'm not sure whether the logic is sound or whether there's a simpler or more conventional approach:
class Solution {
public boolean hasAlternatingBits(int n) {
double i = 1;
while (i < n) {
i *= 2;
if (i % 4 == 0) {
i++;
}
}
return (int) i == n && n != 2147483647;
}
}
3 Answers
Your idea can happen to generate the alternating-bit numbers, but using a double is not appropriate here. This should be done with integer arithmetic, and the special-case check for 2147483647 is a sign that the approach is running into edge-case problems. A clearer solution is to inspect neighboring bits directly. Repeatedly compare the lowest bit with the next bit; if they match, return false, and otherwise shift the number right and continue.
One straightforward bitwise approach is to save the rightmost bit, shift the number right, and compare the new rightmost bit with the saved one. Equal bits mean the pattern is invalid. If they differ, save the new bit and continue until the number becomes zero. This handles numbers ending in either 0 or 1 without needing separate even and odd cases:
int previous = n & 1;
n >>= 1;
while (n > 0) {
int current = n & 1;
if (current == previous) return false;
previous = current;
n >>= 1;
}
return true;
Another option is to compare every pair of neighboring bits after shifting. For example, `(n ^ (n >> 1))` should contain a run of 1s for every valid alternating pattern. You can then check whether that value is all 1s, such as with `x & (x + 1) == 0`, where `x = n ^ (n >> 1)`. The loop-based version is probably easier to understand as a beginner, but both approaches are based on the same idea: adjacent bits must always be different.
When using the XOR approach, make sure the signed integer behavior and the problem’s positive input constraints are understood. The direct loop avoids most of those details and is easier to debug.
The sequence you generate starts at 1, doubles each time, and adds 1 when the result is divisible by 4. That does produce values such as 1, 2, 5, 10, 21, and so on, so the basic observation is understandable. It should still use an int or another integer type, and directly checking adjacent bits is easier to verify.