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


  • 9

    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;
        }
    

  • -1
    This post is deleted!

  • 1

    @Vincent-Cai said in [Java/C++] Very simple solution - 1 line:

    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.


  • 0
    J

    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);
    }

  • 0
    M

    that's good idea~


  • 0

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


  • 0
    This post is deleted!

  • 1

    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 :-)


  • 0

    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;
    }

Log in to reply
 

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