Binary Number with Alternating Bits


  • 0

    Click here to see the full article post


  • 1
    W

    If a number is alternative,we can shift it one bit,mark this new number as m.
    If you check m and n,you will find every bit of m is different from n in the corresponding bit.
    So xor operation come .
    x=n^(n>>1)
    If n is alternative number,x will be like 001111. That's to say ,x ends with several 1s.
    To verify whether x is ends with multi 1s,we can use the following code.
    ans=(x+1)&x
    return ans==0


  • -1
    T

    /* Slow and intuitive solution
    class Solution {
    public:
    bool hasAlternatingBits(int n) {
    vector<int> bits;
    while(n) {
    int r = n % 2;
    n = n / 2;
    bits.push_back(r);
    }

        bool res = true;
        for (int i = 0; i < bits.size() - 1; i++)
            res = res && bits[i] ^ bits[i + 1];
        
        return res;
    }
    

    };
    /*

    /* Smart solution. Using the fact that if n is a alternating number then
    n + (n >> 1) is all 1s, and n + (n >> 1) + 1 should be power of 2. And
    since we know, any number that is a power of two, have an attribute which
    is n & (n - 1) is 0. We just need to check that. */
    class Solution {
    public:
    bool hasAlternatingBits(int n) {
    long po2 = (long) n + (n >> 1) + 1; // the force conversion before n is mandatory, otherwise, it may overflow integer.
    return (po2 & (po2 - 1)) == 0;
    }
    };


  • 1

    You missed the best one!

    function bitSolution(number){
        //      10101010101
        //  +    1010101010    ( number >> 1 )
        //  ---------------
        //  =   11111111111
        //  &  100000000000
        //  ---------------
        //  =             0    ( power of two )
        let tmp = ( number >> 1 ) + number;
        return (tmp & tmp + 1) === 0;
    }
    

  • 0
    Y
    public boolean hasAlternatingBits(int n) {
        int previous = 2;
        while(n != 0){
            if(previous == n%2){
                return false;
            }else{
                previous = n%2;    
                n = n >> 1;
            }
        }
        return true;
    }

  • 0
    M

    My divide by 4 method:

    class Solution(object):
        def hasAlternatingBits(self, n):
            if not n%2: #s.t. 101010 becomes 10101, note 10100 doesn't become 101
                n//=2 #n/=2 for Python 2
            while n: #check for 1010...01 pattern
                if n%4!=1:
                    return False
                n//=4 #n/=4 for Python 2
            return True
    

    Should be a bit faster than the divide by 2 method


  • 0

    @mui That's not faster but infinitely slower. Gets Time Limit Exceeded. (edit: got fixed now)


  • -1
    D

    @tony407 had the exact same sol.

    int m1 = n ^ (n >> 1);

    int m2 = m1 + 1;
    
    if((m1 & m2) == 0)
        return true;
    else
        return false;

  • -1
    M
        boolean isAlternatingBits(int a) {
            return (a & (a >> 1)) == 0;
        }
    

  • -1
    H

    public boolean hasAlternatingBits(int n) {
    String binaryString = Integer.toBinaryString(n);
    if(!binaryString.contains("00") && !binaryString.contains("11")) {
    return true;
    }else {
    return false;
    }
    }


  • -1
    J

    class Solution {
    public:
    bool hasAlternatingBits(int n) {
    long m = n << 1;
    m ^= n;
    return (m & (m+1)) == 0 || (m & (m + 2)) == 0;
    }
    };


  • -1
    J

    private static boolean solution(int key){
    if(((byte)(key % 2)^(byte)((key/2)%2))==0) return false;
    else solution(key/2);
    return true;
    }


  • 0
    J

    C++ solution:

    class Solution {
    public:
        bool hasAlternatingBits(int n) {
            vector<int> vec;
            while(n)
            {
                int nbit = n & 0x01;
                if(vec.size() >= 1)
                {
                    if(nbit ^ vec[vec.size() - 1] == 0)
                        return false;
                }
                vec.push_back(nbit);
                n >>= 1;
            }
            return true;
        }
    };
    

  • -1
    S

    class Solution:
    def hasAlternatingBits(self, n):
    """
    :type n: int
    :rtype: bool
    """
    return True if n^int(n/2) == 2**len(bin(n)[2:]) -1 else False


  • 0
    M

    @ManuelP my bad
    indentation problem (fixed in the original post)


  • 0
    M

    Python in One line:
    return not('0' in bin(n)[2:][::2] or '1' in bin(n)[2:][1::2])


  • 0
    Y

    A RegExp solution:

    return /^0?(10)*1?$/.test(input)
    

  • 0
    V

    public boolean hasAlternatingBits(int n) {
    int decider = (n ^ (n >> 1));

        if((decider & (decider+1)) == 0) {
            return true;
        } else {
            return false;
        }
    }

  • -1
    A

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


Log in to reply
 

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