BinaryNumberWithAlternatingBits [source code]

public class BinaryNumberWithAlternatingBits {
static
/******************************************************************************/
class Solution {
    public boolean hasAlternatingBits(int n) {
        if (n < 0)
            return false;
        int num = n;
        int prev_digit = -1;
        while (num > 0) {
            int digit = num % 2;
            if (digit != 0 && digit != 1 || digit == prev_digit)
                return false;
            prev_digit = digit;
            num /= 2;
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        BinaryNumberWithAlternatingBits.Solution tester = new BinaryNumberWithAlternatingBits.Solution();
        int[] inputs = {
            5, 1,
            7, 0,
            11, 0,
            10, 1,
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int n = inputs[2 * i];
            boolean ans = inputs[2 * i + 1] == 1, output = tester.hasAlternatingBits (n);
            System.out.printf (
                "%s\n%d\t%s\t%b\n",
                Printer.separator (), n, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

这个题目总体来说题目意思还是很简单的, 最简单的方法应该是用regex来写; 但是就算是用手动的方法来写, 其实也是不难的, 只要keep one bit history就行了, O(N)的时间应该能很容易搞定. 这种很简单的题目, 要注意Corner Case;

最后稍微注意一下的就是这里判断的是binary, 所以拆分digit的时候的base应该选择2, 而不是10; 最后轻松AC; 速度是15ms (35%); 不算特别快, 更快的感觉应该是用正则做的;

看了一下submission, 其实大部分都是我这个写法, 速度差别基本都是随机波动导致的; 有一个解法: 

class Solution {  
    public boolean hasAlternatingBits(int n) {  
        int x = (n / 2) ^ n;  
        return (x & (x + 1)) == 0;  
    }  
}

这个其实最后速度并没有优势, 看起来这个算法没有循环, 但是这里这个指数运算的速度问题好像非常明显;

最后这个数学计算 x & (x + 1) == 0 到底是什么意思并不是特别的清楚; 但是可以大概理解一下; 之前463的时候, 我们好像学过一次Binary Increment问题的本质, 基本就是找到第一个0; 比如: 

___11..11  
__100..00

这个就是加法的过程, 然后你这两个数字进行一个&, 那么所有这里被影响到的bit, 都会贡献0. 这个等式不等于0唯一的理由就是在这些bit前面还有剩余的1就行(这些bit是不被increment本身影响的);

能够理解这个bit操作的原理了, 但是上面这个指数运算跟这个怎么结合起来, 还是不太清楚; 这个可能要等在其他地方看看了;

editorial1: 

class Solution {  
    public boolean hasAlternatingBits(int n) {  
        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;  
    }  
}

原理思路是一样的, 但是这个没有用historical stream的思路去做, 单纯直接向前access就行了;

另外值得提到的一点是, editorial后面也给了我这种division disassemble的思路; 但是一个观点是, 他们认为这两个算法的复杂度虽然都依赖于bit的位数, 但是整个算法的复杂度是O(1), 因为最多只可能有32bit;

discussion里面好像有一个类似的解法:

@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.

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

以前是学习过x ^ (x+1)的, 这里用的x & (x + 1), 他这里看来是给出了一个解释, 其实就是: x & (x+1) == 0 iff x does not contain bit 0; 这个也是一个套路; 类似的, 当你知道x是11..11的形式之后, 你也可以用这个来判断x + 1 is a power of 2;

注意他这里>>用小括号包起来了, 因为位操作优先级很低;

这个算法总体上来说还是比较聪明的, 但是最后我提交了一下, 看到速度并不是特别快; 不知道为什么; 按理说这个算法从字面上来看, 基本上是没有任何的赘肉了;

这个人本身的证明是比较难理解的, 这个是我在后面POST的回答:

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

kudos to OP for coming up with such an interesting solution.

My naive proof

if n has alternating bits, then it's not too hard to prove that n + (n>>1) is all bit 1s.

if n does not have alternating bits, then we want to prove that n + (n>>1) has at least one bit 0.

What does it mean for n to be not alternating bits? That means after n's leftmost bit 1: (n == 0 is a trivial corner case with no leftmost 1 at all)

  • n at least has a bigram of 00. This is easy, when you do n + (n>>1), then you have something like this: 
A   B   C   D  
..  0   0   ..  
..  ..  0   0   ..

The bit at C sure will be a bit 0 in the result, because D has a 0 already, thus it will not be able to throw in one 1 to C as a result of the addition.

  • n at least has a bigram of 11. This is not entirely the same as the previous one. Because after addition, we will have a 0 at C, but it is possible D will throw in one 1 to C. This will ruin the C's bit 0. Instead, we claim that n must has a rightmost 11, which is just a trivial corollary of our starting hypothesis. This means that there must be either a 0 to the right of this 11, or nothing at all. Proof for the case of trailng 0: 
A   B   C   D   E  
..  1   1   0   ..  
..  ..  1   1   0   ..

Now it's easy to see that we are guaranteed a 0 at C. For the case of no trailing bits: 

A   B   C  
..  1   1  
..  ..  1

Also ensured a bit 0 at C.
Note that in this case, it is possible the bigram 11 actually includes n's leftmost 1, but I don't think it really matters to the proof: the point is that everything to the left of n's leftmost 1 is ignored.

I hope this proof makes sense. I think it's easier to understand.

感觉比他的好理解一些;

discussion里面给出一个用bit来实现divide digit的一个解法: 

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

这个做法其实我好像是以前见过的, 但是没有想起来; 速度肯定比除法和取模要好; 事实上, 当你看到%2的时候, 你就应该想到用&1来做了, 这个要有一个optimization trigger的自动触发的感觉;

Stefan总结了一个1liner, 懒得看了, 很多其实是强行1liner:

@StefanPochmann said in Oneliners (C++, Java, Ruby, Python):

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

Problem Description

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.

Difficulty:Easy
Total Accepted:12.6K
Total Submissions:22.7K
Contributor:chiragbm
Companies
yahoo
Related Topics
bit manipulation
Similar Questions
Number of 1 Bits

results matching ""

    No results matching ""