# [Java/C++] Very simple solution - 1 line

• If `n` has alternating bits, then `(n>>1) + n` must be like `111...11`.

Now, let's consider the case when `n` does not have alternating bits, that is, `n` has at least one subsequence with continuous `1` or `0` (we assume `n` has continuous `1` in the after) . We write `n` in its binary format as `xxx011...110xxx`, where `xxx0` and `0xxx` could be empty. Denote `A` as `xxx0`, `B` as `11...11` and `C` as `0xxx`, `n` then can be expressed as `ABC`. We can observe that,

1. If the leftmost bit of `C + C>>1` is `1`, then the leftmost two bits of `C+(1C)>>1` is `10`. E.g., if `C = 011`, then `C + (1C)>>1 = 011 + 101 = 1000`. So `n + (n>>1)` will have a bit with `0`.
2. If the leftmost bit of `C + C>>1` is `0`, then the leftmost two bits of `1C+(11C)>>1` is also `10`. E.g., if C = `010`, then `1C + (11C)>>1 = 1010 + 1101 = 10111`. Note that `B` has a length of at least `2`. So `n + (n>>1)` will also have a bit with `0`.

Similar analysis can be done when `n` has continuous `0`. Therefore, if `n` does not have alternating bits, then `(n>>1) + n` must Not be like `111...11`.

At last, for solving this quesiton, we just need to check if `(n>>1) + n + 1` is power of 2.

Java version:

``````    public boolean hasAlternatingBits(int n) {
return ( ((long)n + (n>>1) + 1) & ( (long)n + (n>>1) )) == 0;
}
``````

C++ version:

``````    bool hasAlternatingBits(int n) {
return ( ( long(n) + (n>>1) + 1) & ( long(n) + (n>>1) ) ) == 0;
}
``````

• This post is deleted!

• If `n` has alternating bits, then `(n>>1) + n` must be like `111...11`.

That's only half of the story. What about the other half? Can you explain why if `n` doesn't have alternating bits, then `(n>>1) + n` must not be like `111...11`? I don't find that so trivial.

• Is my approach any good or is it strictly worse?

``````
static Map<Integer, Integer> alter = new HashMap<>();

static {
int a = 0xaaaa_aaaa;
int index=0;
while(a!=0)
alter.put((a>>>=1), index++);
}
public static boolean hasAlternatingBits(int n) {
return alter.containsKey(n);
}``````

• that's good idea~

• @StefanPochmann Very good question! I have updated the post to explain the second half of the "story".

• This post is deleted!

• Thanks for the added explanation. I found it a bit hard to understand, but I think I now know what you mean and I believe the "continuous 1" case. I think the "continuous 0" case would indeed have to be analyzed explicitly, as 0 and 1 aren't equivalent in `+`. For example two ones create overflow and thus affect another bit, but two zeros don't.

I used xor, I think that's much simpler. That said, I just came up with a very simple proof for yours as well:

The function f(n) = n + (n>>1) is strictly increasing: If m > n, then f(m) > f(n). So no two different inputs have the same output. And since the inputs with alternating bits are occopying all the outputs like 111...11, no other inputs can have those outputs. There, done :-)

• I use xor toggle as well.

``````public boolean hasAlternatingBits(int n) {
int prev = n & (1);
n >>= 1;
while(n > 0) {
if(((n & 1) ^ prev) == 0) return false;
prev = n & 1;
n >>= 1;
}
return true;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.